Ringalgorithmus

Der Ringalgorithmus dient dazu, in einem Verteilten Systemen den Knoten mit der höchsten ID auszuwählen.

Anwendung

Maximumsalgorithmus in Verteilten Systemen

Voraussetzungen

• Topologie: Unidirektionaler Ring
• Eindeutige IDs

Idee

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.

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

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.

Weblinks

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