Data Structures and Algorithm: Distributed binary tree sum
You are given a binary tree where each node has an integer value, a left, right and parent pointer. Every node is an independent distributed system where a thread is running in each node. You can talk to other node only by one method called "send(node, data)". And a node can call "send" only to its children or parent. How will you design the system so that all the nodes know the total sum of values of all the nodes in the binary tree and report them asynchronously.
The basic technique that we will follow to get the total sum is as follows.
1. Every node will wait for its children to report the sum of nodes of the tree rooted at the child node.
2. The node will add the sum of its left and right children and add its own value and send it to its parent.
3. Then wait for its parent to report back the total sum of the tree.
The root node will be the first to know the complete sum. Then it propagates it back to its children which in turn will propagate down to its children till every node is aware of the total sum.
To implement this, we keep on adding the values coming via the send method and increment a counter to record how many times the send has been called. When the send has been called equal to the number of children, it means all children has reported their sums. So a node will send the sum after adding its own value to its parent (So leaf nodes will immediately send its own value to its parents). Then resets the sum. Then it keeps on waiting for another send call from its parent. When the send method is called again, the sum will be equal to the total sum of the tree. Then it propagates the same value by calling its children and print the value to console. We need to start the process after our tree building is completed. So we maintained a global static flag which signals all threads to start their operations.
1. Every node will wait for its children to report the sum of nodes of the tree rooted at the child node.
2. The node will add the sum of its left and right children and add its own value and send it to its parent.
3. Then wait for its parent to report back the total sum of the tree.
The root node will be the first to know the complete sum. Then it propagates it back to its children which in turn will propagate down to its children till every node is aware of the total sum.
To implement this, we keep on adding the values coming via the send method and increment a counter to record how many times the send has been called. When the send has been called equal to the number of children, it means all children has reported their sums. So a node will send the sum after adding its own value to its parent (So leaf nodes will immediately send its own value to its parents). Then resets the sum. Then it keeps on waiting for another send call from its parent. When the send method is called again, the sum will be equal to the total sum of the tree. Then it propagates the same value by calling its children and print the value to console. We need to start the process after our tree building is completed. So we maintained a global static flag which signals all threads to start their operations.
public class DistributedSystemSum
{
public static volatile boolean startFlag = false;
public static void main(String[] args)
{
Node a = new Node(1);
Node b = new Node(2);
Node c = new Node(3);
Node d = new Node(4);
Node e = new Node(5);
Node f = new Node(6);
Node g = new Node(7);
Node h = new Node(8);
a.left = b;
b.parent = a;
a.right = c;
c.parent = a;
b.left = d;
d.parent = b;
c.left = e;
e.parent = c;
c.right = f;
f.parent = c;
f.left = g;
g.parent = f;
f.right = h;
h.parent = f;
startFlag = true;
}
private static class Node
{
Node parent;
Node left;
Node right;
int value;
int sum = 0;
int receiveCount = 0;
public Node(int value)
{
this.value = value;
NodeRunner nodeRunner = new NodeRunner(this, value);
new Thread(nodeRunner).start();
}
public synchronized void send(Integer data)
{
sum += data;
receiveCount++;
}
public synchronized int getReceivedCount()
{
return receiveCount;
}
}
private static class NodeRunner implements Runnable
{
Node node;
int id;
NodeRunner(Node node, int id)
{
this.node = node;
this.id = id;
}
@Override
public void run()
{
while (!DistributedSystemSum.startFlag)
{
}
int childCount = 0;
if (node.left != null)
childCount++;
if (node.right != null)
childCount++;
while (node.getReceivedCount() != childCount)
{
}
int sum = node.sum + node.value;
node.sum = 0;
if (node.parent != null)
{
node.parent.send(sum);
while (node.getReceivedCount() != childCount + 1)
{
}
} else
{
node.sum = sum;
}
if (node.left != null)
node.left.send(node.sum);
if (node.right != null)
node.right.send(node.sum);
System.out.println("Thread id=" + id + " sum=" + node.sum);
}
}
}
Read full article from Data Structures and Algorithm: Distributed binary tree sum