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) $n$ 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, $\mathrm{I}\mathrm{D}>0$. Dann schickt jeder Knoten eine Nachricht bestehend aus eigener ID $i$, Sprungzähler $h$ (hopcount, gibt an, wie oft die Nachricht weitergeleitet wurde), einem Merker $f$ (flag) und der aktuellen Phase $p$. Initial gilt $h=1,f=1,p=1$.

• wenn eine Nachricht $⟨i,h,f,p⟩$ empfangen wird:
  • falls $p$ kleiner ist als die aktuelle Phase beim Empfänger, wird die Nachricht nicht weitergeleitet („verschluckt“ nach Chang und Roberts)
  • falls $i>\mathrm{I}\mathrm{D}$ wird die Nachricht weitergeleitet als $⟨i,h+1,f,p⟩$
  • falls $i<\mathrm{I}\mathrm{D}$ wird die Nachricht nicht weitergeleitet
  • falls $i=\mathrm{I}\mathrm{D}$
    • wenn $h\ne n$ wird $f$ auf $0$ gesetzt (der Merker merkt sich, dass die ID mehrfach vergeben ist) und die Nachricht als $⟨i,h+1,0,p⟩$ weitergeleitet
    • wenn $h=n$ und $f=1$ hat der Knoten die Auswahl gewonnen (Mitteilung an alle anderen durch eine spezielle Nachricht)
    • wenn $h=n$ und $f=0$ 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 $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 $h$ wird dabei erhöht.

Nachrichtenkomplexität

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

Der Erwartungswert $E$ für die Anzahl der Wahlgänge (wenn $\mathrm{\forall }ID:ID\in [1,...,n]$): $E\le e\left(\frac{n}{n-1}\right)$ ($e$ 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.