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 dient dazu, in einem Verteilten Systemen den Knoten mit der höchsten ID auszuwählen.

Maximumsalgorithmus in Verteilten Systemen

• Topologie: Unidirektionaler Ring
• Eindeutige IDs

Jeder Knoten wird irgendwann spontan zum Initiator und schickt eine Nachricht mit seiner Identität ab, die den Ring einmal vollständig umrundet. Wenn die Nachricht einem Knoten begegnet, der eine höhere Identität hat, so fügt dieser der Nachricht seine Identität an. Wenn eine Nachricht wieder bei ihrem Initiator eingetroffen ist, so weiß dieser ob er die größte ID im Ring hat und wenn dies nicht der Fall ist, weiß er welcher Knoten im Ring die größte ID hat.

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

Seien n Knoten im Ring. Da ein Ringdurchlauf n Nachrichten benötigt und der komplette Algorithmus n Nachrichtenumläufe benötigt, sind insgesamt n² Nachrichten notwendig.

• Vorlesung „Verteilte Systeme“ an der Universität Mannheim (PDF)