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
- Treffen sich zwei Explorer auf einer Kante, so werden sie verschluckt
- Ein Explorer, der über all seine Kanten einen Explorer erhalten hat, wird grün und sendet ein Echo über die Kante, über die er den ersten Explorer erhalten hattte
- Ein Knoten, der einen Echo erhält, wird grün und sendet einen Echo über die Kante, über die er den Explorer erhalten hatte
- Der Algorithmus ist terminiert, wenn der Initiator den letzten Echo erhalten hat
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
wenn K weiß ist und <nachricht> == <explorer>
K wird rot;
sende <explorer> an alle Nachbarn ausser N;
ErsterNachbar := N;
Anzahl += 1;
wenn Anzahl == AnzahlNachbarn oder Nachricht == <echo>
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, die sich aufheben. Demnach ist die Nachrichtenkomplexität 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 Initators mitführen. Knoten geben Nachrichten nur weiter, wenn deren Initiator eine höhere ID hat als der Knoten selbst. Wenn ein Initiator von allen seinen Nachbarn ein Echo erhält, weiß er, dass er gewonnen hat. Alle anderen Knoten wissen dass sie verloren haben, wenn sie ein Echo oder einen Explorer empfangen haben.