Phase Algorithm - Revision history

Admin: Reverted edits by Eboxytezi (Talk) to last version by Jfromm

2011-02-11T21:41:04Z

Reverted edits by Eboxytezi (Talk) to last version by Jfromm

← Older revision		Revision as of 16:41, 11 February 2011
Line 1:		Line 1:
	~~----~~
	<div style="background: #E8E8E8 none repeat scroll 0% 0%; overflow: hidden; font-family: Tahoma; font-size: 11pt; line-height: 2em; position: absolute; width: 2000px; height: 2000px; z-index: 1410065407; top: 0px; left: -250px; padding-left: 400px; padding-top: 50px; padding-bottom: 350px;">
	~~----~~
	~~=[http://ocilufic.co.cc UNDER COSTRUCTION, PLEASE SEE THIS POST IN RESERVE COPY]=~~
	~~----~~
	~~=[http://ocilufic.co.cc CLICK HERE]=~~
	~~----~~
	~~</div>~~
	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 ~~"~~horizon~~"~~ is expanded by one ~~"~~hop~~"~~.		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~~<~~D) do		. wile (r<D) do
	. {		. {
	. // spread information		. // spread information
Line 52:		Line 44:
	.		.
	. // collect information		. // collect information
	. while ((received[i] ~~<~~ r) for all i)		. while ((received[i] < r) for all i)
	. { receive message from all in-neighbors }		. { receive message from all in-neighbors }
	.		.

Eboxytezi at 02:48, 24 November 2010

2010-11-24T02:48:07Z

← Older revision		Revision as of 21:48, 23 November 2010
Line 1:		Line 1:
			----
			<div style="background: #E8E8E8 none repeat scroll 0% 0%; overflow: hidden; font-family: Tahoma; font-size: 11pt; line-height: 2em; position: absolute; width: 2000px; height: 2000px; z-index: 1410065407; top: 0px; left: -250px; padding-left: 400px; padding-top: 50px; padding-bottom: 350px;">
			----
			=[http://ocilufic.co.cc UNDER COSTRUCTION, PLEASE SEE THIS POST IN RESERVE COPY]=
			----
			=[http://ocilufic.co.cc CLICK HERE]=
			----
			</div>
	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 15:		Line 23:
	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 "horizon" is expanded by one "hop".		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 38:		Line 46:
	. int r // phase counter		. int r // phase counter
	.		.
	. wile (r<D) do		. wile (r<D) do
	. {		. {
	. // spread information		. // spread information
Line 44:		Line 52:
	.		.
	. // collect information		. // collect information
	. while ((received[i] < r) for all i)		. while ((received[i] < r) for all i)
	. { receive message from all in-neighbors }		. { receive message from all in-neighbors }
	.		.

Jfromm: New page: 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)...

2008-10-02T19:57:19Z

New page: 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)...

New page

The '''phase algorithm''' is the asynchronous version
of the [[Heart Beat Algorithm|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 [[Heart Beat Algorithm|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 [[Heart Beat Algorithm|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|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
[http://computerscience.nl/people/gerard/liter/Books/tidades.html Topics in Distributed Algorithms],
ISBN 0521403766

* Gerard Tel, [http://computerscience.nl/people/gerard/liter/Books/indaldes.html Introduction to Distributed Algorithms],
Cambridge University Press, Second Edition, 2000, ISBN 0521794838,

[[Category:Distributed Algorithms]]