Tracers in distributed computing.
When there are many peers participating in a task, sometimes the only way to determine the actions done by each is to send a tracer through the system. This is also the same functionality that is so niftily used in networking to find the participating hosts in a route. I'm referring to the traceroute tool. This tool lists the hosts in the order that the IP packet travels and each host adds an entry with its ipaddress. When we are interested only in source destination reachability, we use the ping tool. The ping tool sends multiple echo requests to the destination server and calculates the packet loss. If the other side is responding properly, we can collect the responses. The traceroute tool on the other hand is a way to find what path is taken to reach the destination and is for a single packet only. There are no multiple packets sent. This comes in useful for say DNS path resolution.
In distributed computing however, we use tracers as markers to see how the diffusion propagates through the system. In gossip for example, we can use a dummy message to see the participants involved in sending the message.
The gossip propagates by selecting peers at random. Each peer when selected and received a task, can update it The goal in gossip is to spread the information as quickly as possible. This can happen even over unreliable network.
Gossip protocols can also be one that aggregates. To compute the aggregates, the values from the nodes are combined to arrive at a system wide value. The key idea in aggregation is that the aggregate must be computed as fixed size pairwise exchanges. The exchanges terminated after a few rounds and usually by the end of all to all information flow. The gossip algorithms can arrange the node in a tree and computes aggregates such as sum or count by gossiping in a pattern that matches the tree.
Typically what we stamp in the information dissemination such as a gossip protocol is node id, timestamp and the actual message pertaining to the information. In our cases the information is a reserved message that mentions to the nodes to add their stamp to the information and forwards it on.
The node ids could be a sorted list and each node adds its entry to the list provided. When a node sees two sorted lists, it merges them.
When there are many peers participating in a task, sometimes the only way to determine the actions done by each is to send a tracer through the system. This is also the same functionality that is so niftily used in networking to find the participating hosts in a route. I'm referring to the traceroute tool. This tool lists the hosts in the order that the IP packet travels and each host adds an entry with its ipaddress. When we are interested only in source destination reachability, we use the ping tool. The ping tool sends multiple echo requests to the destination server and calculates the packet loss. If the other side is responding properly, we can collect the responses. The traceroute tool on the other hand is a way to find what path is taken to reach the destination and is for a single packet only. There are no multiple packets sent. This comes in useful for say DNS path resolution.
In distributed computing however, we use tracers as markers to see how the diffusion propagates through the system. In gossip for example, we can use a dummy message to see the participants involved in sending the message.
The gossip propagates by selecting peers at random. Each peer when selected and received a task, can update it The goal in gossip is to spread the information as quickly as possible. This can happen even over unreliable network.
Gossip protocols can also be one that aggregates. To compute the aggregates, the values from the nodes are combined to arrive at a system wide value. The key idea in aggregation is that the aggregate must be computed as fixed size pairwise exchanges. The exchanges terminated after a few rounds and usually by the end of all to all information flow. The gossip algorithms can arrange the node in a tree and computes aggregates such as sum or count by gossiping in a pattern that matches the tree.
Typically what we stamp in the information dissemination such as a gossip protocol is node id, timestamp and the actual message pertaining to the information. In our cases the information is a reserved message that mentions to the nodes to add their stamp to the information and forwards it on.
The node ids could be a sorted list and each node adds its entry to the list provided. When a node sees two sorted lists, it merges them.
No comments:
Post a Comment