Bully-Algorithmus

Der Bully-Algorithmus ist ein Verfahren, in verteilten Rechen zum dynamischen Wahl eines Koordinators durch Prozess-ID-Nummer. Der Prozess mit der höchsten Prozess-ID-Nummer wird als Koordinator gewählt.

Annahmen

  • Das System ist synchron und verwendet Timeout zur Identifizierung von Prozessfehler.
  • Ermöglicht Prozesse während der Ausführung des Algorithmus zum Absturz bringen.
  • Die Nachrichtenübermittlung zwischen Prozessen sollte zuverlässig sein.
  • Vor Informationen über andere Prozess-ID muss bekannt sein.

Wahltyp

  • Election Nachricht: Gesendete schneller Wahlen anzukündigen
  • Antwort Nachricht: an die Wahl Nachricht antworten
  • Koordinator Nachricht: Gesendete, um die Identität des gewählten Prozesses bekannt geben

Vergleichen mit Ring-Algorithmus:

  • Davon aus, dass System ist Synchron
  • Verwendet Timeout auf Prozessfehler / crash erfassen
  • Jeder Prozessor weiß, welcher Prozessor die höhere Kennnummer und kommuniziert mit dem

Wenn ein Prozess P feststellt, dass der aktuelle Koordinator ist nach unten, weil der Nachricht Timeouts oder Misserfolg der Koordinator einen Händedruck zu initiieren, führt es die folgende Sequenz von Aktionen:

  • P sendet eine Wahl Nachricht an alle anderen Prozesse mit höheren Prozess-IDs, erwartet ein "ich lebe" Antwort von ihnen, wenn sie noch am Leben sind.
  • Wenn P hört von keinem Prozess mit einer höheren Prozess-ID, als es, gewinnt er die Wahl und Sendungen Sieg.
  • Wenn P hört aus einem Prozess mit einer höheren ID wartet P eine bestimmte Menge an Zeit für jeden Prozess mit einer höheren ID, sich als Führer übertragen. Wenn es diese Nachricht in der Zeit empfangen, Re-Sendungen es die Wahl-Nachricht.
  • Wenn P erhält eine Wahl Nachricht von einem anderen Prozess mit einer niedrigeren ID es eine Meldung "ich lebe" sendet und startet Neuwahlen.

Beachten Sie, dass, wenn P erhält einen Sieg Nachricht von einem Prozess mit einer niedrigeren ID-Nummer, sofort initiiert er eine Neuwahl. Dies ist, wie der Algorithmus hat seinen Namen - ein Prozess mit einer höheren ID-Nummer wird eine niedrigere ID Prozess aus dem Koordinator Position so schnell zu schikanieren, wie es online geht.

  0   0
Vorherige Artikel 2047
Nächster Artikel Calder Vale

Kommentare - 0

Keine Kommentare

Fügen Sie einen Kommentar

smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile
Zeichen übrig: 3000
captcha