Itai-Rodeh-Algorithmus

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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

[Bearbeiten | Quelltext bearbeiten]
  • 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 kleiner ist als die aktuelle Phase beim Empfänger, wird die Nachricht nicht weitergeleitet („verschluckt“ nach Chang und Roberts)
    • falls wird die Nachricht weitergeleitet als
    • falls wird die Nachricht nicht weitergeleitet
    • falls
      • wenn wird auf gesetzt (der Merker merkt sich, dass die ID mehrfach vergeben ist) und die Nachricht als weitergeleitet
      • wenn und hat der Knoten die Auswahl gewonnen (Mitteilung an alle anderen durch eine spezielle Nachricht)
      • wenn und gibt es mehrere Gewinner.

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.

Nachrichtenkomplexität

[Bearbeiten | Quelltext bearbeiten]

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.