Itai-Rodeh-Algorithmus

Der Itai-Rodeh-Algorithmus ist ein Algorithmus der Las-Vegas Klasse zur Auswahl anonymer unidirektionale Ringe und baut auf dem Chang- und Roberts-Algorithmus auf.

Voraussetzungen

unidirektionaler Ring
Ringgröße (Anzahl der Knoten) <math>n</math> bekannt

Ablauf

Der Algorithmus läuft in Phasen (Wahlgängen) ab.

Erste Phase

In der ersten Phase wählen alle Knoten eine zufällige Identifikationsnummer, <math>\mathrm{ID} > 0</math>. Dann schickt jeder Knoten eine Nachricht bestehend aus eigener ID <math>i</math>, Sprungzähler <math>h</math> (hopcount, gibt an, wie oft die Nachricht weitergeleitet wurde), einem Merker <math>f</math> (flag) und der aktuellen Phase <math>p</math>. Initial gilt <math>h = 1, f = 1, p = 1</math>.

wenn eine Nachricht <math>\langle i,h,f,p \rangle</math> empfangen wird:
- falls <math>p</math> kleiner ist als die aktuelle Phase beim Empfänger, wird die Nachricht nicht weitergeleitet („verschluckt“ nach Chang und Roberts)
- falls <math>i > \mathrm{ID}</math> wird die Nachricht weitergeleitet als <math>\langle i,h+1,f,p \rangle</math>
- falls <math>i < \mathrm{ID}</math> wird die Nachricht nicht weitergeleitet
- falls <math>i = \mathrm{ID}</math>
  - wenn <math>h \ne n</math> wird <math>f</math> auf <math>0</math> gesetzt (der Merker merkt sich, dass die ID mehrfach vergeben ist) und die Nachricht als <math>\langle i,h+1,0,p \rangle</math> weitergeleitet
  - wenn <math>h = n</math> und <math>f = 1</math> hat der Knoten die Auswahl gewonnen (Mitteilung an alle anderen durch eine spezielle Nachricht)
  - wenn <math>h = n</math> und <math>f = 0</math> gibt es mehrere Gewinner.

Weitere Phasen

Falls es mehrere Gewinner der ersten bzw. vorherigen Phase gibt, dann startet diese Gruppe einen weiteren Durchlauf des Algorithmus mit <math>p = p + 1</math>. Der Ablauf ist genau wie in der ersten Phase, jedoch mit verringerter Anzahl der Teilnehmer. Passive Knoten leiten Nachrichten lediglich weiter; lediglich der Sprungzähler <math>h</math> wird dabei erhöht.

Nachrichtenkomplexität

Für die erste Phase werden <math>n</math> Nachrichten benötigt. Da die Anzahl der Phasen theoretisch unbegrenzt ist, geht die Nachrichtenkomplexität gegen unendlich. Praktisch ist dieser Fall aber sehr unwahrscheinlich. So kommen für jede weitere Phase weniger als <math>n</math> Nachrichten hinzu.

Der Erwartungswert <math>E</math> für die Anzahl der Wahlgänge (wenn <math>\forall ID: ID \in [1, ..., n]</math>): <math>E \le e \left( \frac{n}{n - 1} \right)</math> (<math>e</math> ist die Eulersche Zahl)

Quellen

Vorlesung Verteilte Systeme an der TU-Berlin
A. Itai and M. Rodeh. Symmetry breaking in distributed networks, In Proceedings of the 22nd IEEE Symposium on Science, pages 150-158. IEEE Press, 1981.