Phase Algorithm: Difference between revisions
No edit summary |
|||
| Line 1: | Line 1: | ||
The '''phase algorithm''' is the asynchronous version | The '''phase algorithm''' is the asynchronous version | ||
of the [[Heart Beat Algorithm|heartbeat algorithm]]. Each node or process | of the [[Heart Beat Algorithm|heartbeat algorithm]]. Each node or process | ||
| Line 23: | Line 15: | ||
phase, every node knows his neighbors. In the second round, | phase, every node knows his neighbors. In the second round, | ||
every node knows his neighbors and their neighbors. | every node knows his neighbors and their neighbors. | ||
In each round the | In each round the "horizon" is expanded by one "hop". | ||
After D rounds, where D equals the diameter of the | After D rounds, where D equals the diameter of the | ||
network, each node has informations about the whole | network, each node has informations about the whole | ||
| Line 46: | Line 38: | ||
. int r // phase counter | . int r // phase counter | ||
. | . | ||
. wile (r | . wile (r<D) do | ||
. { | . { | ||
. // spread information | . // spread information | ||
| Line 52: | Line 44: | ||
. | . | ||
. // collect information | . // collect information | ||
. while ((received[i] | . while ((received[i] < r) for all i) | ||
. { receive message from all in-neighbors } | . { receive message from all in-neighbors } | ||
. | . | ||
Latest revision as of 16:41, 11 February 2011
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,
