Distributed GCD Algorithm

2010-03-12T08:37:56Z

Jamesbruk:

The '''distributed GCD algorithm''' belongs to a special class of
[[Distributed Algorithm|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 [http://www.research-service.com/custom-research-paper.html research paper]
find the max, min, gcd or average value for all nodes).

The distributed GCD algorithm is a very simple [[Distributed_Algorithm|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_Algorithm|distributed algorithms]], for
explanatory purposes and to illustrate the workings of
[[Distributed_Algorithm|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)
}

[[Category:Distributed Algorithms]]

CasGroup - User contributions [en]

Distributed GCD Algorithm