Bullyalgorithmus

aus Wikipedia, der freien Enzyklopädie

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

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. Jeder Prozess (mit höherer ID), der p geantwortet hat, verschickt seinerseits wiederum Anfragen an alle Prozesse, die eine hörere 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.