Ringalgorithmus

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
QS-Informatik

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[Bearbeiten]

Ablauf[Bearbeiten]

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 intialisierende 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[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]

Weblinks[Bearbeiten]

Literatur[Bearbeiten]

  •  Andres S. Tanenbaum, Maarten Van Steen: Distributed Systems. Principles and Paradigms. 2. Auflage. 2006, ISBN 9780132392273, S. 266.