Echo Algorithm - Revision history

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

2011-02-11T21:40:37Z

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

← Older revision		Revision as of 16:40, 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://isiqilujev.co.cc Page Is Unavailable Due To Site Maintenance, Please Visit Reserve Copy Page]=~~
	~~----~~
	~~=[http://isiqilujev.co.cc CLICK HERE]=~~
	~~----~~
	~~</div>~~
	A typical example for a [[Total Algorithm\|total algorithm]] is the echo algorithm, which has been discovered by Ernest J.H. Chang in 1982.		A typical example for a [[Total Algorithm\|total algorithm]] is the echo algorithm, which has been discovered by Ernest J.H. Chang in 1982.

Line 16:		Line 8:
	travels from the border of system back to the initiator and can be used to collect information from the system.		travels from the border of system back to the initiator and can be used to collect information from the system.
	During the propagation of the first explorer wave, a spanning tree is constructed which consists of all the predecessor		During the propagation of the first explorer wave, a spanning tree is constructed which consists of all the predecessor
	nodes stored in the parameter ~~"~~pred~~"~~ at each node. The echo wave travels back along this spanning tree to the initiator.		nodes stored in the parameter "pred" at each node. The echo wave travels back along this spanning tree to the initiator.
	If it reaches the initiator, the algorithm is terminated.		If it reaches the initiator, the algorithm is terminated.

Line 25:		Line 17:
	N = 0;		N = 0;

	The parameter ~~"~~Engaged~~"~~ shows if the explorer wave has already visited the node,		The parameter "Engaged" shows if the explorer wave has already visited the node,
	and the echo counter N contains the number of echos the node has received.		and the echo counter N contains the number of echos the node has received.
	The initiator starts like this		The initiator starts like this
Line 33:		Line 25:
	Send Explorer-Msg to all Neighbors;		Send Explorer-Msg to all Neighbors;

	If a process receives a Message from process p it reacts like the following piece of code: each node which is visited for the first time by an explorer message will propagate itself explorer messages to all its neighbors and waits for responses (~~"~~echos~~"~~) from the neightbors. If all neighbors have responded, the node sends itself an echo-message to its predecessor.		If a process receives a Message from process p it reacts like the following piece of code: each node which is visited for the first time by an explorer message will propagate itself explorer messages to all its neighbors and waits for responses ("echos") from the neightbors. If all neighbors have responded, the node sends itself an echo-message to its predecessor.

	IF NOT Engaged THEN		IF NOT Engaged THEN
Line 47:		Line 39:
	ELSE finished;		ELSE finished;

	The '''message extinction principle''' says that if two explorer messages hit each other on a single link, then both extinguish each other. They are received, but have no effect, because both sender nodes are already marked as ~~"~~engaged~~"~~.		The '''message extinction principle''' says that if two explorer messages hit each other on a single link, then both extinguish each other. They are received, but have no effect, because both sender nodes are already marked as "engaged".

	== Articles ==		== Articles ==

Eboxytezi at 02:48, 24 November 2010

2010-11-24T02:48:38Z

← 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://isiqilujev.co.cc Page Is Unavailable Due To Site Maintenance, Please Visit Reserve Copy Page]=
			----
			=[http://isiqilujev.co.cc CLICK HERE]=
			----
			</div>
	A typical example for a [[Total Algorithm\|total algorithm]] is the echo algorithm, which has been discovered by Ernest J.H. Chang in 1982.		A typical example for a [[Total Algorithm\|total algorithm]] is the echo algorithm, which has been discovered by Ernest J.H. Chang in 1982.

Line 8:		Line 16:
	travels from the border of system back to the initiator and can be used to collect information from the system.		travels from the border of system back to the initiator and can be used to collect information from the system.
	During the propagation of the first explorer wave, a spanning tree is constructed which consists of all the predecessor		During the propagation of the first explorer wave, a spanning tree is constructed which consists of all the predecessor
	nodes stored in the parameter "pred" at each node. The echo wave travels back along this spanning tree to the initiator.		nodes stored in the parameter "pred" at each node. The echo wave travels back along this spanning tree to the initiator.
	If it reaches the initiator, the algorithm is terminated.		If it reaches the initiator, the algorithm is terminated.

Line 17:		Line 25:
	N = 0;		N = 0;

	The parameter "Engaged" shows if the explorer wave has already visited the node,		The parameter "Engaged" shows if the explorer wave has already visited the node,
	and the echo counter N contains the number of echos the node has received.		and the echo counter N contains the number of echos the node has received.
	The initiator starts like this		The initiator starts like this
Line 25:		Line 33:
	Send Explorer-Msg to all Neighbors;		Send Explorer-Msg to all Neighbors;

	If a process receives a Message from process p it reacts like the following piece of code: each node which is visited for the first time by an explorer message will propagate itself explorer messages to all its neighbors and waits for responses ("echos") from the neightbors. If all neighbors have responded, the node sends itself an echo-message to its predecessor.		If a process receives a Message from process p it reacts like the following piece of code: each node which is visited for the first time by an explorer message will propagate itself explorer messages to all its neighbors and waits for responses ("echos") from the neightbors. If all neighbors have responded, the node sends itself an echo-message to its predecessor.

	IF NOT Engaged THEN		IF NOT Engaged THEN
Line 39:		Line 47:
	ELSE finished;		ELSE finished;

	The '''message extinction principle''' says that if two explorer messages hit each other on a single link, then both extinguish each other. They are received, but have no effect, because both sender nodes are already marked as "engaged".		The '''message extinction principle''' says that if two explorer messages hit each other on a single link, then both extinguish each other. They are received, but have no effect, because both sender nodes are already marked as "engaged".

	== Articles ==		== Articles ==

Jfromm: New page: A typical example for a total algorithm is the echo algorithm, which has been discovered by Ernest J.H. Chang in 1982. == Echo Algorithm == The echo algorithms consis...

2008-10-02T19:56:35Z

New page: A typical example for a total algorithm is the echo algorithm, which has been discovered by Ernest J.H. Chang in 1982. == Echo Algorithm == The echo algorithms consis...

New page

A typical example for a [[Total Algorithm|total algorithm]] is the echo algorithm, which has been discovered by Ernest J.H. Chang in 1982.

== Echo Algorithm ==

The echo algorithms consists of two phases or waves: a forward wave of explorer messages which spread through a net, and a
backward wave of echo messsages which is created if the explorer wave front hits the border of the net. The explorer wave
travels from the initiator to the border of the distributed system and can be used to disseminate information, the echo wave
travels from the border of system back to the initiator and can be used to collect information from the system.
During the propagation of the first explorer wave, a spanning tree is constructed which consists of all the predecessor
nodes stored in the parameter "pred" at each node. The echo wave travels back along this spanning tree to the initiator.
If it reaches the initiator, the algorithm is terminated.

All nodes or processes are initiated with

Initiator = false;
Engaged = false;
N = 0;

The parameter "Engaged" shows if the explorer wave has already visited the node,
and the echo counter N contains the number of echos the node has received.
The initiator starts like this

Initiator = true;
Engaged = true;
Send Explorer-Msg to all Neighbors;

If a process receives a Message from process p it reacts like the following piece of code: each node which is visited for the first time by an explorer message will propagate itself explorer messages to all its neighbors and waits for responses ("echos") from the neightbors. If all neighbors have responded, the node sends itself an echo-message to its predecessor.

IF NOT Engaged THEN
Engaged = TRUE;
N = 0;
Pred = p;
Send Explorer-Msg to all Neighbors except p;
N = N + 1;
IF N == #Neighbors THEN
Engaged = FALSE;
IF NOT Initiator
THEN Send Echo-Msg to Pred
ELSE finished;

The '''message extinction principle''' says that if two explorer messages hit each other on a single link, then both extinguish each other. They are received, but have no effect, because both sender nodes are already marked as "engaged".

== Articles ==

Ernest J.H. Chang, ''Echo Algorithms: Depth Parallel Operations on General Graphs'', IEEE Transactions on Software Engineering, Vol. 8, No. 4, July 1982

[[Category:Distributed Algorithms]]