Calculate number of nodes in a linear network using message passing
Problem
In a connected network consisting of N nodes, each node is connected to either one or two neighbors, forming a line topology. The task is to develop a program that runs on each node, calculating the total number of nodes in the network. Each node is aware of its neighboring nodes and can exchange messages with them. It is important to note that nodes do not share memory; the only means of information exchange between two neighbors is through sending and receiving messages. For the sake of simplicity, assume the network is reliable and that message delivery is instantaneous. Below is a starting code snippet.
1type Node struct {
2 Left *Node
3 Right *Node
4}
5
6func (*Node) GetNetworkSize() int {}
7
8func (*Node) sendLeft(msg any) {}
9func (*Node) sendRight(msg any) {}
10func (*Node) receiveLeft(msg any) {}
11func (*Node) receiveRight(msg any) {}
Solution
This problem is not a typical "Algorithm and Data Structure" problem where the program has global view and only one instance of the program runs at any time. Instead, the problem runs N independent copies of the program as peers, communicating through messages. The challenge is to determine what messages to send and how to respond to them.
On any node A, the total number of nodes is the sum of nodes on A's left,
A's right, and A itself. This can be represented as N = nodesLeft(A) + nodesRight(A) + 1.
Initially, the leftmost node knows its nodesLeft. To propagate this information
to other nodes, we pass the nodesLeft from the leftmost node to the right,
incrementing by one at each intermediate node.
Consider the messages exchanged between three nodes: L -> A -> R, where L and R
are A's left and right neighbors, respectively. Following the flow of nodesLeft
from left to right, L provides its nodesLeft to A and requests A's nodesRight.
Are two different types of messages necessary, one for providing and one for request?
No, a message of a single integer suffices. If the integer is greater than 0,
L informs A of the number of nodes on A's left. Otherwise, L requests the number
of nodes on its right. This logic also applies to passing nodesRight from right to left. The following code snippet provides the implementation. Refer to the complete code and test.
1type Node struct {
2 Left *Node
3 Right *Node
4
5 // nodes on the left side and right side.
6 nodesLeft int
7 nodesRight int
8}
9
10func (node *Node) sendLeft(m int) {
11 if node.Left != nil {
12 node.Left.receiveRight(m)
13 }
14}
15
16func (node *Node) sendRight(m int) {
17 if node.Right != nil {
18 node.Right.receiveLeft(m)
19 }
20}
21
22// L -> A. node A receives information from node L.
23// if m > 0: L tells A that there are n nodes on A's left side, including L.
24// otherwise: L asks A for how many nodes are on L's right side, including A.
25func (node *Node) receiveLeft(m int) {
26 if m > 0 {
27 node.nodesLeft = m
28 node.sendRight(node.nodesLeft + 1)
29 return
30 }
31
32 if node.Right == nil {
33 node.sendLeft(1)
34 } else if node.nodesRight > 0 {
35 node.sendLeft(node.nodesRight + 1)
36 } else {
37 node.sendRight(0)
38 }
39}
40
41// A <- R. node A receives information from node R.
42// if m > 0: R tells A that there are n nodes on A's right side, including R.
43// otherwise: R asks A for how many nodes are on R's left side, including A.
44func (node *Node) receiveRight(m int) {
45 if m > 0 {
46 node.nodesRight = m
47 node.sendLeft(node.nodesRight + 1)
48 return
49 }
50
51 if node.Left == nil {
52 node.sendRight(1)
53 } else if node.nodesLeft > 0 {
54 node.sendRight(node.nodesLeft + 1)
55 } else {
56 node.sendLeft(0)
57 }
58}
59
60func (node *Node) GetNetworkSize() int {
61 if node.Left == nil && node.Right == nil {
62 return 1
63 }
64
65 if node.Left == nil {
66 node.sendRight(1)
67 node.sendRight(0)
68 }
69 if node.Right == nil {
70 node.sendLeft(1)
71 node.sendLeft(0)
72 }
73 if node.Left != nil && node.Right != nil {
74 node.sendLeft(0)
75 node.sendRight(0)
76 }
77
78 return node.nodesLeft + node.nodesRight + 1
79}