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.

• unidirektionaler Ring
• Ringgröße (Anzahl der Knoten) ${\displaystyle n}${\displaystyle n} bekannt

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

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

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

Falls es mehrere Gewinner der ersten bzw. vorherigen Phase gibt, dann startet diese Gruppe einen weiteren Durchlauf des Algorithmus mit ${\displaystyle p=p+1}${\displaystyle p=p+1}. 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 ${\displaystyle h}${\displaystyle h} wird dabei erhöht.

Für die erste Phase werden ${\displaystyle n}${\displaystyle n} 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 ${\displaystyle n}${\displaystyle n} Nachrichten hinzu.

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

• 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.

• Verteiltes System
• Algorithmus