Itai-Rodeh-Algorithmus

Der Itai-Rodeh-Algorithmus ist ein Auswahlalgorithmus der Las-Vegas Klasse für anonyme 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, ID > 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 $\langle i,h,f,p \rangle$ 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 > ID wird die Nachricht weitergeleitet als $\langle i,h+1,f,p \rangle$
  • falls i < ID wird die Nachricht nicht weitergeleitet
  • falls i = ID
    • wenn $h \ne n$ wird f auf 0 gesetzt (der Merker merkt sich, dass die ID mehrfach vergeben ist) und die Nachricht als $\langle i,h+1,0,p \rangle$ 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 $\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.