Bullyalgorithmus

Der Bullyalgorithmus ist ein rekursiver, verteilter Algorithmus der in einem verteilten System verwendet wird, wenn ein neuer Koordinatorprozess ermittelt werden muss, weil der ursprüngliche abgestürzt ist. Letzteres kann beispielsweise durch einen Timeout festgestellt werden.

Ablauf

Ein Prozess p, welcher den Ausfall des Koordinators bemerkt hat, sendet Anfragen an alle Prozesse, die eine höhere ID haben als er selbst. Diese Prozesse schicken eine Bestätigung zurück, wenn sie nicht selbst abgestürzt sind. Falls der Prozess p von Prozessen mit höherer ID Antworten bekommt, sendet er keine weiteren Nachrichten mehr. Falls Prozess p keine Antwort bekommt wird er selbst zum Koordinator.

Jeder Prozess (mit höherer ID), der p geantwortet hat, verschickt seinerseits wiederum Anfragen an alle Prozesse, die eine höhere ID haben als er, um herauszufinden ob diese noch existieren, was diese dann ebenso wiederholen (Rekursion). Der letzte Prozess hat keinen Prozess mehr, den er fragen kann, da er selbst die höchste ID hat, denn der Koordinatorprozess mit der höchsten ID ist ja ausgefallen und kann nicht mehr antworten. Er tritt selbst an die Stelle des neuen Koordinators und sendet per Broadcast die Nachricht, dass er der neue Koordinator sei.

Annahmen

Damit der Bullyalgorithmus beweisbar funktioniert, müssen in dem verteilten System folgende Annahmen gelten:

• Alle Prozesse kooperieren und verwenden exakt denselben Wahlalgorithmus.
• Es gibt keine Fehler in der Implementierung und alle Prozesse bieten auch ständig die Möglichkeit an, empfangene Nachrichten abzuarbeiten.
• Wenn ein Prozess P1 die Nachricht M von Prozess P2 erhält, dann ist sichergestellt, dass die Nachricht zu einem früheren Zeitpunkt gesendet worden ist. Es gibt also keine spontan generierten Nachrichten im System.
• Alle Prozesse besitzen so genannte "Storage Cells", in denen die Daten gespeichert werden, an denen sie arbeiten. Das bedeutet, dass selbst bei einem Fehler oder Ausfall des Prozesses die Daten gespeichert bleiben. Datenzugriff in "Storage Cells" sollte auf Transaktionen basieren – entweder die neuen Daten werden in die Storage Cell geschrieben oder sie werden verworfen, die alten bleiben aber erhalten und weiterhin konsistent.
• Wenn ein Prozess ausfällt, hört er sofort mit der Bearbeitung seiner Daten auf. Wird er wieder aktiviert, fängt er mit der Bearbeitung wieder an (dort, wo er aufgehört hat).
• Es gibt keine Übertragungsfehler im System. Das bedeutet, dass alle Nachrichten korrekt übertragen werden.
• Alle Nachrichten werden in der Reihenfolge ihrer Ankunft abgearbeitet. Sendet Prozess 1 also die Nachrichten M1 und M2 in dieser Reihenfolge, so wird ein zweiter Prozess diese Nachrichten auch in der Reihenfolge M1, M2 abarbeiten.
• Es gibt keine Ausfälle in der Kommunikation und das System bietet eine zeitliche Obergrenze T an, zu der die Nachricht auf jeden Fall abgearbeitet werden sollte. Wenn ein Prozess also nach T Zeiteinheiten noch immer keine Antwort von einem anderen erhalten hat, so kann er davon ausgehen, dass der Empfängerprozess abgestürzt ist.
• Ein Prozess hört niemals auf, auf Nachrichten zu antworten und tut dies auch ohne Verzögerung.
• Das Netzwerk des Systems arbeitet synchron.

Pseudocode

P bemerkt, dass der Koordinator nicht mehr antwortet:

function hold_election()
   for each (Process Q) {
     if (Id(Q) > Id(P))
       send(Q, ELECTION);
     end if
   }

  if $\exists$ Q: (receive(Q, ANSWER)) //timeout T for $\exists$
  then
    do_something_else();
  else
    for each (Process Q) {
      if (Id(Q) < Id(P))
        send(Q, COORDINATOR);
      endif
    }
  endif

P empfängt ELECTION, gesendet von Prozess pred:

function continue_election()
  send(pred, ANSWER);
  hold_election();

Vorteile

• Es ist problemlos möglich einen ausfallenden Koordinator zu ersetzen, da jeder Prozess die Ermittlung eines neuen Koordinatorprozesses anstoßen kann.

Nachteile

• Alle Prozesse müssen jedem Prozess bekannt sein und es muss eine absolute Ordnung auf den Prozessen bestehen. Ansonsten kann kein Prozess ermitteln, welche Nachrichten er verschicken muss.
• Reagiert ein Prozess sehr langsam, entsteht hierdurch eine Verzögerung, die den gesamten Ablauf verlangsamt.

Literatur

• Emmett Witchel: Distributed Coordination. 2005, PPT-Datei, abgerufen am 3. August 2013.
• Hector Garcia-Molina: Elections in a Distributed Computing System. In: IEEE. Transactions on Computers. Bd. C-31, No. 1, Januar 1982, ISSN 0018-9340, S. 48–59, doi:10.1109/TC.1982.1675885.

Weblinks

• Vorlesung „Verteilte Systeme“ an der Hochschule für Angewandte Wissenschaften Hamburg