Itai-Rodeh-Algorithmus

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

• wenn eine Nachricht ${\displaystyle \langle i,h,f,p\rangle }$ empfangen wird:
  • falls ${\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} }$ wird die Nachricht weitergeleitet als ${\displaystyle \langle i,h+1,f,p\rangle }$
  • falls ${\displaystyle i<\mathrm {ID} }$ wird die Nachricht nicht weitergeleitet
  • falls ${\displaystyle i=\mathrm {ID} }$
    • wenn ${\displaystyle h\neq n}$ wird ${\displaystyle f}$ auf ${\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 }$ weitergeleitet
    • wenn ${\displaystyle h=n}$ und ${\displaystyle f=1}$ hat der Knoten die Auswahl gewonnen (Mitteilung an alle anderen durch eine spezielle Nachricht)
    • wenn ${\displaystyle h=n}$ und ${\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}$. 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}$ wird dabei erhöht.