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

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 ⟨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>ID wird die Nachricht weitergeleitet als ⟨i,h+1,f,p⟩
    • falls i<ID wird die Nachricht nicht weitergeleitet
    • falls i=ID
      • wenn h≠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 ∀ID:ID∈[1,...,n]): E≤e(nn−1) (e ist die Eulersche Zahl)

Quellen