In my last post Intelligent Network Part II– Centralized and Distributed Network, I left out a question for the readers to come up with a solution that can achieve O (lg N) time efficiency on propagating a message through the entire network.
The scenario: given a set of communication stations, how do we send messages from station to station in a way that eventually every station would receive the same message.
We talked about in a centralized network setup, it would take O ( N ) linear time to propagate the message. It’s similar to how satellite transmit messages to ground receivers (below figure) except in our scenario that only one message can be sent to a single station at a time (unlike the satellite broadcasting method, but you get the idea…)
If you haven’t read my last post, I think it’s a good time to go back and read Intelligent Network Part II– Centralized and Distributed Network now. We’ll tweak the question scenario a little to make it more complicated in a distributed network environment, I’ll also introduce couple Global Aggregation Methods.
This time, please allow me to put you in the shoes of Earth federation defense commander, suppose we still have the same set of communication stations spread out and covers a continent, the continent is very big and each station can only talk to those stations within 100 miles radius (and is only aware of existence of those stations). One day an exterrestrial alien space ship visited earth and sent out thousands of probe drones across the continent. Each communication station is capable of detecting total number of alien drones in its own jurisdiction, for simplicity sake let’s assume that no station jurisdiction overlap with each other. The only way for human-being to initiate diplomatic contact with the alien visitor is to prove we are intelligent by summing the total number of probe drones and display the same number from all stations. If you were the defense commander. How would you solve the problem?
Let’s first try to figure out what type of network this is. Obviously it’s a decentralized/distributed network. There does not exist a single station powerful enough to talk to all other stations, so we have to calculate aggregation and then propagate the result through network. The network looks a lot like the following graph where vertices represent stations, and edges represent communication links.
I’ll show you two ways to get this done with their corresponding benefits and drawbacks.
Global Aggregation Method 1 – Tree(Heap) aggregation
Time efficiency O(lg N)
Space efficiency O(1)
Let’s re-arrange the stations in a slightly different way as below graph. Now we have a binary tree, and most binary tree operations are O (lg N) so we’ll be able to exploit this.
Our goal is to have the aggregated sums calculated and then propagate to all the nodes in the graph. I’ll show you exactly how this is done.
We first start out on the leaf nodes, in our example we’ll sum up values from (16, 17), (18, 19), (20,21)…(24,25) pairs and send the sum up (bottom up) to their parents, we’ll keep doing this until we reach the root node. Now the root node has the sum of all other nodes! To propagate the sum to the rest of the network, we simply just need to reverse the direction and send the sum top-down. Since messages can be sent in parallel, total time needed is 2 (lg N) where N is the total number of nodes in the tree.
- Very efficient, earth can be saved in no time!
- Very scalable. Image we have billions of stations on the continent, we’ll still be able to use this method to calculate the aggregates pretty efficiently.
- Not fault tolerant, if some stations malfunctioned, the aggregation will never complete.
Global Aggregation Method 2 – Symmetric Push Sum Protocol (Gossip Protocol)
Time efficiency: Non deterministic
Space efficiency O(N) – 1 extra variable per network node
Since method 1 has its devastating drawback being not fault tolerant, let’s consider a different approach. This time we’ll use something called Gossip Protocol, similar to gossips in human social behaviors, (interesting) rumors can travel at incredible speed to incredible distance. Have you ever thought how that actually works? It works in a way similar to the tree method we described above, except we add in a few probabilistic random variable to prevent messages stop at faulty nodes.
SPSP (Symmetric Push Sum Protocol) works by keeping track of a weight and its actual value at each node. In our case, the value would be the number of detected probe drones in the area. The weight serves as a heuristic percentage value to indicate propagation progress.
An example here would be perfect for explaining this algorithm. Let’s assume we have a two-node network for now, node A has a value of 10, node B ha a value of 35. So total expected sum is 45. Let’s see how it’s done.
- Initialization: we preset the weight to be 0 on all the nodes and then we’ll pick a random node (in our case node A) and set its weight to be 1.
- Run SPSP algorithm, showing in below graphs.
- Node A start out chopping both weight (w1) and value (v1) into half and send w1’ and v1’ to node B.
- Node B upon receiving the push message with w1’ and v1’, calculate w2’ and v2’ then push back to node A.
- Once node A receives a symmetric push from B, it will simply add the w2’ and v2’ to its own.
- Finally node B will add w1’ and v1’ to its own values.
- Maintain a connected node cache using some random heuristics, keep doing above steps for all the nodes in the cache. In our case it ends here since we only have two nodes. I strongly recommend readers to try this out on a 4-5 node network to get a feel on how it works.
- Ending condition: when the value on each nodes reaches convergence, we know the sum is properly calculated and eventually it will propagate through the entire network.
- Sum = value / weight;
- Fault tolerant. Aggregation can be done on massive dynamic expanding networks such as P2P network.
- Scalable and fast propagation.
- Not as efficient as the tree aggregation method, but it’s a good tradeoff in some specific scenarios.
To help you understand, I am also attaching the code to simulate SSPS. It’s written in C#. Enjoy.