imported>Georg Hügler am 3. Dezember 2022 um 07:41 Uhr

2022-12-03T07:41:36Z

Neue Seite

Der '''Itai-Rodeh-Algorithmus''' ist ein [[Algorithmus]] der [[Las-Vegas-Algorithmus|Las-Vegas Klasse]] zur Auswahl anonymer [[unidirektional]]e [[Topologie (Rechnernetz)|Ringe]] und baut auf dem [[Nachrichtenauslöschung nach Chang und Roberts|Chang- und Roberts-Algorithmus]] auf.

== Voraussetzungen ==
* unidirektionaler Ring
* Ringgröße (Anzahl der [[Netzwerkknoten|Knoten]]) <math>n</math> bekannt

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

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

* wenn eine Nachricht <math>\langle i,h,f,p \rangle</math> empfangen wird:
** falls <math>p</math> kleiner ist als die aktuelle Phase beim Empfänger, wird die Nachricht nicht weitergeleitet („verschluckt“ nach [[Nachrichtenauslöschung nach Chang und Roberts|Chang und Roberts]])
** falls <math>i > \mathrm{ID}</math> wird die Nachricht weitergeleitet als <math>\langle i,h+1,f,p \rangle</math>
** falls <math>i < \mathrm{ID}</math> wird die Nachricht nicht weitergeleitet
** falls <math>i = \mathrm{ID}</math>
*** wenn <math>h \ne n</math> wird <math>f</math> auf <math>0</math> gesetzt (der Merker merkt sich, dass die ID mehrfach vergeben ist) und die Nachricht als <math>\langle i,h+1,0,p \rangle</math> weitergeleitet
*** wenn <math>h = n</math> und <math>f = 1</math> hat der Knoten die Auswahl gewonnen (Mitteilung an alle anderen durch eine spezielle Nachricht)
*** wenn <math>h = n</math> und <math>f = 0</math> 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 <math>p = p + 1</math>. 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 <math>h</math> wird dabei erhöht.

==Nachrichtenkomplexität==
Für die erste Phase werden <math>n</math> 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 <math>n</math> Nachrichten hinzu.

Der [[Erwartungswert]] <math>E</math> für die Anzahl der Wahlgänge (wenn <math>\forall ID: ID \in [1, ..., n]</math>): <math>E \le e \left( \frac{n}{n - 1} \right)</math> (<math>e</math> ist die [[Eulersche Zahl]])

==Quellen==
* 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.

[[Kategorie:Verteiltes System]]
[[Kategorie:Algorithmus]]

Itai-Rodeh-Algorithmus - Versionsgeschichte

imported>Georg Hügler am 3. Dezember 2022 um 07:41 Uhr