Ringalgorithmus

Dieser Artikel wurde wegen inhaltlicher Mängel auf der Qualitätssicherungsseite der Redaktion Informatik eingetragen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Informatik auf ein akzeptables Niveau zu bringen. Hilf mit, die inhaltlichen Mängel dieses Artikels zu beseitigen, und beteilige dich an der Diskussion! (+) Begründung: Eher unverständlich, quellenlos (Weblink 404), unterschiedliche Meinungen zur Nachrichtenkomplexität (siehe Vorgängerbearbeitung) --Howwi 16:50, 2. Aug. 2009 (CEST)

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 $n$ Prozessen im Ring müssen maximal $n-1$ Wahlnachrichten verschickt werden. Da der die Wahl abhaltende Prozess nach Ende der Wahl weiß, welche Prozesse aktiv sind, wird nur an diese eine Koordinationsnachricht verschickt. Dies führt zu einer Komplexität von maximal $2(n-1)$ bzw. ${\mathcal {O}}(n)$.

Siehe auch

• Bullyalgorithmus

Literatur

• Andrew S. Tanenbaum, Maarten Van Steen: Distributed Systems. Principles and Paradigms. 2. Auflage. 2006, ISBN 978-0-13-239227-3, S. 266. 

Weblinks

• Vorlesung „Verteilte Systeme“ an der Hochschule für Angewandte Wissenschaften Hamburg (PDF; 1,5 MB)