Distributed GCD Algorithm

The distributed GCD algorithm belongs to a special class of distributed algorithms for mathematical operations. At each node in the distributed system, one or more values are stored, the nodes can communicate with each other, and are allowed to perform certain mathematical operations. The distributed algorithm now has to determine the exact sequence of operations that each node has to follow in order to achieve a global goal (for instance find the max, min, gcd or average value for all nodes).

The distributed GCD algorithm is a very simple distributed algorithm to determine the Greatest Common Divisor (GCD) of n numbers. Because it is so simple and elegant, it is often used as an introductory example for distributed algorithms, for explanatory purposes and to illustrate the workings of distributed algorithms in general (for instance the problem of termination detection). The algorithm for a ring topology with as many nodes as numbers works as follows: each process begins with a number z, and the algorithm is finished if all nodes have the same number.

On receiving a message from a neighbor:

Receive (int e)
{ 
   if (e < z) 
   {
     z = ((z-1)%e)+1);
     Send()
   }
}

Sending messages:

Send()
{
  SendMsg (z, left Neighbor)
  SendMsg (z, right Neighbor) 
}