Echo algorithm

from Wikipedia, the free encyclopedia
Echo algorithm

application

The echo algorithm is suitable for the following applications in a distributed system :

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