Ringalgorithmus
Vorlage:QS-Informatik Der Ringalgorithmus ist ein Auswahlalgorithmus, mit dem in einem verteilten System ein Prozess mit einer besonderen Aufgabe ermittelt wird. Diese Aufgabe kann zum Beispiel ein Koordinator sein.
Voraussetzungen
- Topologie: Unidirektionaler Ring
- Eindeutige IDs
Ablauf
Der Ringalgorithmus kann von einem beliebigen Prozess gestartet werden, wenn dieser feststellt, dass der ursprüngliche Koordinator ausgefallen ist, oder von einem Prozess, der soeben neu gestartet wurde und daher den Koordinator noch nicht kennt. Der die Wahl initialisierende Prozess schickt eine Wahlnachricht mit seiner eigenen Prozessnummer (ID) an den nächsten erreichbaren Prozess im Ring. Dieser fügt der Nachricht seine eigene ID hinzu und schickt sie wiederum an den nächsten Prozess im Ring.
Hat die Wahlnachricht den Ring einmal vollständig umrundet, erhält der initiierende Prozess eine Wahlnachricht, der bereits die eigene ID enthält. Damit ist die Wahl beendet. Aus den durch Eintragung in die Wahlnachricht beteiligten Prozessen wird nun ein neuer Prozess für die spezielle Aufgabe ermittelt. In der Regel ist das der Prozess mit der höchsten Prozessnummer. Die Wahlnachricht wird nun in eine Koordinationsnachricht umgewandelt, die wieder an jeden teilnehmenden Prozess des Rings geschickt wird. Mit dieser Nachricht wird den beteiligten Prozessen das Wahlergebnis mitgeteilt.
Pseudocode
Initiator
Sende <ID, ID> an nächsten Knoten
Ein Knoten K empfängt <r, max>
wenn ID(K) > max
max := ID(K);
wenn r == ID(K)
wenn max == ID(K)
"ICH HABE GEWONNEN"
sonst
"max HAT GEWONNEN"
sonst
sende <r, max> an nächsten Knoten
Nachrichtenkomplexität
Bei Prozessen im Ring müssen mindestens Wahlnachrichten verschickt werden. Initiiert der Prozess die Wahl der in dem Ring (Uhrzeigersinn) direkt nach dem Prozess mit der größten ID ist führt dies zu einer Komplexität von maximal .
Siehe auch
Literatur
Weblinks
- Vorlesung „Verteilte Systeme“ an der Hochschule für Angewandte Wissenschaften Hamburg (PDF; 1,5 MB)