aus Wikipedia, der freien Enzyklopädie

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) bekannt

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

In der ersten Phase wählen alle Knoten eine zufällige Identifikationsnummer, . Dann schickt jeder Knoten eine Nachricht bestehend aus eigener ID , Sprungzähler (hopcount, gibt an, wie oft die Nachricht weitergeleitet wurde), einem Merker (flag) und der aktuellen Phase . Initial gilt .

• wenn eine Nachricht empfangen wird:

Falls es mehrere Gewinner der ersten bzw. vorherigen Phase gibt, dann startet diese Gruppe einen weiteren Durchlauf des Algorithmus mit . 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 wird dabei erhöht.

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

Der Erwartungswert für die Anzahl der Wahlgänge (wenn ): ( 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.