Echo algorithm
application
The echo algorithm is suitable for the following applications in a distributed system :
- Information distribution with termination recognition
- Generation of a spanning tree
- Select a node
requirements
The echo algorithm is possible on any contiguous topology.
idea
There are two types of messages: Explorer messages, which color the nodes red, and Echo messages, which color the nodes green. Before the algorithm is executed, all nodes are white.
- An initiator turns red and sends an explorer to all of his neighbors.
- A white node that receives an Explorer turns red
- A node that has received an explorer or an echo over all of its edges turns green
- A non-initiator node that has received an explorer or an echo over all of its edges sends an echo over the edge over which it received the first explorer
- The algorithm terminates when the initiator turns green
The edges over which the echo messages ran result in a spanning tree.
Pseudocode
Note: All nodes are white at the beginning, the number is 0 and the first neighbor is empty
initiator
sende <explorer> an alle Nachbarn;
A node K receives <message> from a neighbor N
Anzahl += 1;
wenn K weiß ist K wird rot; sende <explorer> an alle Nachbarn außer N; ErsterNachbar := N; wenn Anzahl == AnzahlNachbarn K wird grün; wenn K der Initiator ist EXIT; sonst sende <echo> an ErsterNachbar
Message complexity
Either an explorer and an echo or two explorers run over each edge e. Thus the message complexity is 2 * e.
Improvements
Improvement of the message complexity
If unique IDs are assigned in a topology and every node knows the identity of its neighbors, it is possible to use the Explorer to inform its neighbor which node it has also sent an Explorer. In some cases Explorer can be saved. The disadvantage here, however, is that the message length increases to O (n).
The echo algorithm as a selection algorithm
In order to be able to use the echo algorithm as a selection algorithm, each node must have its own ID.
Every node starts an echo algorithm at some point, whereby both the echoes and the explorer carry the ID of their initiator. Nodes ignore all messages whose initiator has a smaller ID than they do. If an initiator receives an echo from all of his neighbors with his own ID, he knows that he has won. All other nodes know that they have lost if they have received an Explorer with a higher ID than themselves.
Web links
- Lecture "Distributed Systems" ( Memento from September 15, 2007 in the Internet Archive ) at the University of Mannheim