Phase Algorithm

The phase algorithm is the asynchronous version of the heartbeat algorithm. Each node or process waits until it has received all messages of phase (or round) i before it sends its own message and takes part in the next round. Like the heartbeat algorithm, it requires that all processes know the diameter D of the network, or at least an upper bound on the network diameter.

Definition

The informal description of the phase algorithm is identical with that of the heartbeat algorithm: each node gives the information it has to his neighbors and asks them for their information. In the first round or phase, every node knows his neighbors. In the second round, every node knows his neighbors and their neighbors. In each round the "horizon" is expanded by one "hop". After D rounds, where D equals the diameter of the network, each node has informations about the whole system.

Unlike the heartbeat algorithm, in the phase algorithm the nodes are not acting synchronously, in other words no global time or timer is available. Each process has to wait until all messages of the previous phase have arrived.

The algorithm works for directed networks, too. In this case one has to distinguish for a current node p between in-neighbors (processes or nodes that can send messages to p), and out-neighbors (processes to which p can send messages).

The pseudo code for a phase algorithm is

. // define and init. local variables and parameters
. const int D;     // network diameter
. int[] Received;  // number of messages received from each in-neighbors
. int r            // phase counter 
.
. wile (r<D) do
. {
.  // spread information 
.  send message to all out-neighbors;
.   
.  // collect information 
.  while ((received[i] < r) for all i)
.  { receive message from all in-neighbors }
.
.  // add new information to existing ones 
.  update local variables; 
.
.  // new phase or round
.  r := r+1
. }

Application

As a total algorithm it can be used to spread and collect information to all nodes in a distributed system.

References

The phase algorithm was described in detail by Gerard Tel in his books

• Gerard Tel, Structure of Distributed Algorithms, PhD thesis, University of Utrecht, 1989;

also published by Cambridge University Press, 1991 as Topics in Distributed Algorithms, ISBN 0521403766

• Gerard Tel, Introduction to Distributed Algorithms,

Cambridge University Press, Second Edition, 2000, ISBN 0521794838,