8. Many nodes

Goal

Ask every peer of a five-node cluster, count the answers, and move on when a majority has answered.

New in this chapter

{} form empty spec/04 §4.4
set item k of … to … form set-item spec/04 §4.4
each p in … form each spec/04 §4.4
each k, v in … form each-pair spec/04 §4.4
item 0 of nodes form item spec/04 §4.4
k is in … form is-in spec/04 §4.4
k is not in … form is-not-in spec/04 §4.4
map of node to number type map spec/04 §4.2
[v: value] type value spec/04 §4.2
lists.Append package std/lists std/README.md § std/lists
maps.Size package std/maps std/README.md § std/maps
math.Floor package std/math std/README.md § std/math

Steps

Two nodes are a conversation; five are a system. A node now needs to remember many peers, and to count. For that Synod has lists (ordered values, {a, b, c}, which you met in chapter 2) and maps (a value for each key). The empty one is written {}: one spelling for an empty list and an empty map. Which of the two it is, and of what, the compiler works out from how you use it.

Step 1 turns the single Peer into a list Peers, starting as {}. The new phrase Connect has a hole [ns: list of Node]: the type of a list says what it holds, always, in a hole too. each n in ns runs its block once for each item, with n naming the item. lists.Without n from ns is a copy of the list without n: each node's peers are everybody else. The demo builds a cluster with sim.Cluster of 5 running pingpong, which spawns five nodes and gives back the list. item 0 of nodes is the first. Start makes the first node ping each of its peers with each p in n.Peers:

Step 1

# package main
use example.com/tutorial/pingpong
use std/net
use std/sim

define main
  set nodes to (sim.Cluster of 5 running pingpong)
  pingpong.Connect nodes
  net.Latency between 50ms and 150ms
  deliver (message pingpong.Start with Round 1) to (item 0 of nodes)

# package pingpong
use std/lists
use std/net
use std/sim

Start has
  set Round to 0

Ping has
  set round to 0

Pong has
  set round to 0

Node has
  set Peers to {}
  set Rounds to 0
  set Done to false

# Ten rounds are played
define Limit
  result 10

# Every node in the list learns all the others
define Connect [ns: list of Node]
  each n in ns
    set n.Peers to (lists.Without n from ns)

# Send a message to another node
define [n: Node] Reply [m: msg] to [p: node]
  net.Send m from n to p

# The first node serves every peer
when [n: Node] (sim.Delivered Start)
  each p in n.Peers
    net.Send (message Ping with round Start.Round) from n to p

# Whoever is pinged answers
when [n: Node] (net.Received Ping from sender)
  set n.Rounds to (n.Rounds plus 1)
  n.Reply (message Pong with round Ping.round) to sender
  if (Ping.round at least Limit)
    set n.Done to true

# Whoever hears the answer pings again, until round ten
when [n: Node] (net.Received Pong from sender)
  set n.Rounds to (n.Rounds plus 1)
  if (Pong.round less than Limit)
    n.Reply (message Ping with round (Pong.round plus 1)) to sender
  else
    set n.Done to true

Everyone now plays against the first. But nobody counts who answered. Step 2 changes the rule of the game: a round ends when a majority has answered, and then the next one starts.

The asking node keeps a map Heard, from node to the last round that node answered. Writing into a map is set item sender of n.Heard to Pong.round; the key is the sender, the value the round. item k of m would read it. Answerers is a value phrase with a hole of type map of node to number: it goes through the map with each k, v in heard, key and value, and keeps the keys whose value is the round asked about. lists.Append k to who adds one item. sender is in n.Peers checks membership.

Majority of shows that phrase heads can be followed by more words: Majority of 5 is 3. It divides by two and rounds down with math.Floor, then adds one. lists.Size counts the items of a list. The asking node counts itself, which is why there are plus 1s:

Step 2

# package pingpong
use std/lists
use std/math
use std/net
use std/sim

Start has
  set Round to 0

Ping has
  set round to 0

Pong has
  set round to 0

Node has
  set Peers to {}
  set Heard to {}
  set Round to 0
  set Done to false

# Ten rounds are played
define Limit
  result 10

# More than half of n
define Majority of [n: number]
  result ((math.Floor (n divided by 2)) plus 1)

# Every node in the list learns all the others
define Connect [ns: list of Node]
  each n in ns
    set n.Peers to (lists.Without n from ns)

# The peers that answered round r
define Answerers [heard: map of node to number] in round [r: number]
  set who to {}
  each k, v in heard
    if (v is r)
      set who to (lists.Append k to who)
  result who

# Send a message to another node
define [n: Node] Reply [m: msg] to [p: node]
  net.Send m from n to p

# Ping every peer with the current round
define [n: Node] Ask
  each p in n.Peers
    n.Reply (message Ping with round n.Round) to p

# The first node asks round one
when [n: Node] (sim.Delivered Start)
  set n.Round to Start.Round
  n.Ask

# Whoever is pinged answers
when [n: Node] (net.Received Ping from sender)
  n.Reply (message Pong with round Ping.round) to sender

# The asking node notes each answer and moves on when a majority has answered
when [n: Node] (net.Received Pong from sender)
  if ((sender is in n.Peers) and (Pong.round is n.Round))
    set item sender of n.Heard to Pong.round
    set answered to ((lists.Size (Answerers n.Heard in round n.Round)) plus 1)
    if (answered is (Majority of ((lists.Size n.Peers) plus 1)))
      if (n.Round less than Limit)
        set n.Round to (n.Round plus 1)
        n.Ask
      else
        set n.Done to true

The run is deterministic: round by round the asking node moves on only when three of five have answered. Late answers to old rounds are ignored by Pong.round is n.Round.

Step 3 changes how the group is formed. Only the first node is told about the others, as two small groups joined with lists.Extend near with far. Everybody else learns who is asking, when a Ping arrives: sender is not in n.Peers is the opposite of is in. At the end of the demo the caption reads out what the first node heard. maps.Size is the number of keys; maps.Keys the keys in ascending order, a list:

Step 3

# package main
use example.com/tutorial/pingpong
use std/lesson
use std/lists
use std/maps
use std/net
use std/sim
use std/text

define main
  set caller to (sim.Spawn pingpong)
  set near to (sim.Cluster of 2 running pingpong)
  set far to (sim.Cluster of 2 running pingpong)
  set caller.pingpong.Peers to (lists.Extend near with far)
  net.Latency between 50ms and 150ms
  deliver (message pingpong.Start with Round 1) to caller
  after 5s
    set heard to caller.pingpong.Heard
    lesson.Note (text.Join {"Heard from ", (text.From (maps.Size heard)), " peers, the first was ", (text.From (item 0 of (maps.Keys heard)))})

# package pingpong
use std/lists
use std/math
use std/net
use std/sim

Start has
  set Round to 0

Ping has
  set round to 0

Pong has
  set round to 0

Node has
  set Peers to {}
  set Heard to {}
  set Round to 0
  set Done to false

# Ten rounds are played
define Limit
  result 10

# More than half of n
define Majority of [n: number]
  result ((math.Floor (n divided by 2)) plus 1)

# The peers that answered round r
define Answerers [heard: map of node to number] in round [r: number]
  set who to {}
  each k, v in heard
    if (v is r)
      set who to (lists.Append k to who)
  result who

# Send a message to another node
define [n: Node] Reply [m: msg] to [p: node]
  net.Send m from n to p

# Ping every peer with the current round
define [n: Node] Ask
  each p in n.Peers
    n.Reply (message Ping with round n.Round) to p

# The first node asks round one
when [n: Node] (sim.Delivered Start)
  set n.Round to Start.Round
  n.Ask

# Whoever is pinged answers, and remembers who asked
when [n: Node] (net.Received Ping from sender)
  if (sender is not in n.Peers)
    set n.Peers to (lists.Append sender to n.Peers)
  n.Reply (message Pong with round Ping.round) to sender

# The asking node notes each answer and moves on when a majority has answered
when [n: Node] (net.Received Pong from sender)
  if ((sender is in n.Peers) and (Pong.round is n.Round))
    set item sender of n.Heard to Pong.round
    set answered to ((lists.Size (Answerers n.Heard in round n.Round)) plus 1)
    if (answered is (Majority of ((lists.Size n.Peers) plus 1)))
      if (n.Round less than Limit)
        set n.Round to (n.Round plus 1)
        n.Ask
      else
        set n.Done to true

There is one type the table of types shows and you will not write: value, "any type". It appears only in the standard library's own patterns, such as lists.Size [l: list of value], so that one phrase serves every kind of list.

What to watch

The first card sends four messages to its neighbours, and the answers come back at different times. The round moves on after the third answer, before the slowest one has arrived. In the final state the first node says Heard with every peer's last round, and the others each know one peer, the first.

Why it looks like this

An empty {} alone says nothing about its type. Here a local holds {} and then only goes through text.From, which takes any value:

pingpong/demo.synod:15:17: error[ambiguous-empty]: cannot tell the type of {}
   |
15 |   set nobody to {}
   |                 ^^
   |
   = help: use it with std/lists or std/maps, or assign it where the type is known

Error ambiguous-empty

synod check says error[ambiguous-empty] with a hint: use the empty value with std/lists or std/maps, or assign it where the type is known. A field like Peers is fine, because the program appends nodes to it somewhere.

Exercises

Make the cluster 7 nodes in step 2. How many answers does a round need?

Expected

Majority of 7 is 4: the asking node and three others. Rounds take about as long as the third-fastest answer.

In step 2, add after 1ms and crash two of the other nodes inside it, with sim.Crash (item 1 of nodes) and so on. Does the game finish?

Expected

Yes: three nodes still make a majority of five. Crash a third and the round never completes, and the game stops with Done false.

In step 3, print how many peers the third node knows at the end.

Expected

One: the first node, learnt from its Ping. Set third to (item 0 of near) and read third.pingpong.Peers in the caption, through lists.Size.