跳至內容

霸道選舉算法

維基百科,自由的百科全書

霸道選舉算法(Bully algorithm)是一種分佈式選舉算法,每次都會選出存活的進程中ID最大的候選者

霸道選舉算法的假設

[編輯]

算法假設:[1]

  1. 系統是同步的
  2. 進程在任何時候都可能失敗,包括算法在執行的過程中
  3. 進程失敗後停止工作,重啟後重新工作
  4. 有失敗監控者,它可以發現失敗的進程
  5. 進程之間的消息傳遞是可靠的
  6. 每一個進程知道自己和其他每一個進程的ID以及地址

霸道算法的選舉流程

[編輯]

選舉過程中會發送以下三種消息類型:

  1. Election消息:表示發起一次選舉
  2. Answer(Alive)消息:對發起選舉消息的應答
  3. Coordinator(Victory)消息:選舉勝利者向參與者發送選舉成功消息

觸發選舉流程的事件包括:

  1. 當進程P從錯誤中恢復
  2. 檢測到Leader失敗

選舉流程:

  1. 如果P是最大的ID,直接向所有人發送Victory消息,成功新的Leader;否則向所有比他大的ID的進程發送Election消息。
  2. 如果P再發送Election消息後沒有收到Alive消息,則P向所有人發送Victory消息,成功新的Leader。
  3. 如果P收到了從比自己ID還要大的進程發來的Alive消息,P停止發送任何消息,等待Victory消息(如果過了一段時間沒有等到Victory消息,重新開始選舉流程)。
  4. 如果P收到了比自己ID小的進程發來的Election消息,回復一個Alive消息,然後重新開始選舉流程。
  5. 如果P收到Victory消息,把發送者當做Leader。

參考資料

[編輯]
  1. ^ Coulouris, George; Dollimore, Jean; Kindberg, Tim. Distributed Systems: Concepts and Design 3rd. Addison Wesley. 2000. ISBN 978-0201619188.