www.wikidata.de-de.nina.az

Itai Rodeh Algorithmus Der ist ein Algorithmus der Las Vegas Klasse zur Auswahl anonymer unidirektionale Ringe und baut

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 Bearbeiten

  • unidirektionaler Ring
  • Ringgröße (Anzahl der Knoten) bekannt

Ablauf Bearbeiten

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

Erste Phase Bearbeiten

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.

Weitere Phasen Bearbeiten

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

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)

Quellen Bearbeiten

  • 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.
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
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 Inhaltsverzeichnis 1 Voraussetzungen 2 Ablauf 2 1 Erste Phase 2 2 Weitere Phasen 3 Nachrichtenkomplexitat 4 QuellenVoraussetzungen Bearbeitenunidirektionaler Ring Ringgrosse Anzahl der Knoten n displaystyle n nbsp bekanntAblauf BearbeitenDer Algorithmus lauft in Phasen Wahlgangen ab Erste Phase Bearbeiten In der ersten Phase wahlen alle Knoten eine zufallige Identifikationsnummer I D gt 0 displaystyle mathrm ID gt 0 nbsp Dann schickt jeder Knoten eine Nachricht bestehend aus eigener ID i displaystyle i nbsp Sprungzahler h displaystyle h nbsp hopcount gibt an wie oft die Nachricht weitergeleitet wurde einem Merker f displaystyle f nbsp flag und der aktuellen Phase p displaystyle p nbsp Initial gilt h 1 f 1 p 1 displaystyle h 1 f 1 p 1 nbsp wenn eine Nachricht i h f p displaystyle langle i h f p rangle nbsp empfangen wird falls p displaystyle p nbsp kleiner ist als die aktuelle Phase beim Empfanger wird die Nachricht nicht weitergeleitet verschluckt nach Chang und Roberts falls i gt I D displaystyle i gt mathrm ID nbsp wird die Nachricht weitergeleitet als i h 1 f p displaystyle langle i h 1 f p rangle nbsp falls i lt I D displaystyle i lt mathrm ID nbsp wird die Nachricht nicht weitergeleitet falls i I D displaystyle i mathrm ID nbsp wenn h n displaystyle h neq n nbsp wird f displaystyle f nbsp auf 0 displaystyle 0 nbsp gesetzt der Merker merkt sich dass die ID mehrfach vergeben ist und die Nachricht als i h 1 0 p displaystyle langle i h 1 0 p rangle nbsp weitergeleitet wenn h n displaystyle h n nbsp und f 1 displaystyle f 1 nbsp hat der Knoten die Auswahl gewonnen Mitteilung an alle anderen durch eine spezielle Nachricht wenn h n displaystyle h n nbsp und f 0 displaystyle f 0 nbsp gibt es mehrere Gewinner Weitere Phasen Bearbeiten Falls es mehrere Gewinner der ersten bzw vorherigen Phase gibt dann startet diese Gruppe einen weiteren Durchlauf des Algorithmus mit p p 1 displaystyle p p 1 nbsp Der Ablauf ist genau wie in der ersten Phase jedoch mit verringerter Anzahl der Teilnehmer Passive Knoten leiten Nachrichten lediglich weiter lediglich der Sprungzahler h displaystyle h nbsp wird dabei erhoht Nachrichtenkomplexitat BearbeitenFur die erste Phase werden n displaystyle n nbsp Nachrichten benotigt Da die Anzahl der Phasen theoretisch unbegrenzt ist geht die Nachrichtenkomplexitat gegen unendlich Praktisch ist dieser Fall aber sehr unwahrscheinlich So kommen fur jede weitere Phase weniger als n displaystyle n nbsp Nachrichten hinzu Der Erwartungswert E displaystyle E nbsp fur die Anzahl der Wahlgange wenn I D I D 1 n displaystyle forall ID ID in 1 n nbsp E e n n 1 displaystyle E leq e left frac n n 1 right nbsp e displaystyle e nbsp ist die Eulersche Zahl Quellen BearbeitenVorlesung 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 Abgerufen von https de wikipedia org w index php title Itai Rodeh Algorithmus amp oldid 228518837