Echo-Algorithmus

Anwendung

Der Echo-Algorithmus ist für folgende Anwendungen in einem Verteilten System geeignet:

Informationsverteilung mit Terminierungserkennung
Erzeugung eines Spannbaumes
Auswählen eines Knotens

Voraussetzungen

Der Echo-Algorithmus ist auf jeder zusammenhängenden Topologie möglich.

Idee

Es gibt zwei Nachrichtentypen: Explorernachrichten, die die Knoten rot färben und Echo-Nachrichten, die die Knoten grün färben. Vor der Ausführung des Algorithmus sind alle Knoten weiß.

Ein Initiator wird rot und schickt an alle seine Nachbarn einen Explorer.
Ein weißer Knoten, der einen Explorer erhält wird rot
Ein Knoten, der über all seine Kanten einen Explorer oder ein Echo erhalten hat, wird grün
Ein Nicht-Initiator Knoten, der über all seine Kanten einen Explorer oder ein Echo erhalten hat, sendet einen Echo über die Kante, über die er den ersten Explorer erhalten hatte
Der Algorithmus terminiert, wenn der Initiator grün wird

Die Kanten über die die Echo-Nachrichten gelaufen sind ergeben einen Spannbaum.

Pseudocode

Anm: Alle Knoten sind am Anfang weiß, Anzahl ist 0 und ErsterNachbar ist leer

Initiator

sende <explorer> an alle Nachbarn;

Ein Knoten K empfängt <nachricht> von einem Nachbarn 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

Nachrichtenkomplexität

Über jede Kante e läuft entweder ein Explorer und ein Echo oder zwei Explorer. Demnach ist die Nachrichtenkomplexität 2*e.

Verbesserungen

Verbesserung der Nachrichtenkomplexität

Wenn in einer Topologie eindeutige IDs vergeben sind und jeder Knoten die Identität seiner Nachbarn kennt, so ist es möglich mit dem Explorer seinem Nachbarn mitzuteilen welchen Knoten er außerdem noch einen Explorer gesendet hat. So können in manchen Fällen Explorer eingespart werden. Der Nachteil dabei ist allerdings, dass die Nachrichtenlänge dabei auf O(n) ansteigt.

Der Echo-Algorithmus als Auswahlalgorithmus

Um den Echo-Algorithmus als Auswahlalgorithmus benutzen zu können, muss jeder Knoten eine eigene ID haben.

Jeder Knoten startet irgendwann einen Echo-Algorithmus, wobei sowohl die Echos, als auch die Explorer die ID ihres Initiators mitführen. Knoten ignorieren alle Nachrichten, deren Initiator eine kleinere ID hat als sie selbst. Wenn ein Initiator von allen seinen Nachbarn ein Echo mit seiner eigenen ID erhält, weiß er, dass er gewonnen hat. Alle anderen Knoten wissen, dass sie verloren haben, wenn sie einen Explorer mit einer höheren ID als sie selbst empfangen haben.

Weblinks

Vorlesung "Verteilte Systeme" (Memento vom 15. September 2007 im Internet Archive) an der Universität Mannheim