霸道選舉算法
![]() |
霸道選舉算法(Bully algorithm)是一種分布式選舉算法,每次都會選出存活的進程中ID最大的候選者。
霸道選舉算法的假設
算法假設:[1]
- 系統是同步的
- 進程在任何時候都可能失敗,包括算法在執行的過程中
- 進程失敗後停止工作,重啟後重新工作
- 有失敗監控者,它可以發現失敗的進程
- 進程之間的消息傳遞是可靠的
- 每一個進程知道自己和其他每一個進程的ID以及地址
霸道算法的選舉流程
選舉過程中會發送以下三種消息類型:
- Election消息:表示發起一次選舉
- Answer(Alive)消息:對發起選舉消息的應答
- Coordinator(Victory)消息:選舉勝利者向參與者發送選舉成功消息
觸發選舉流程的事件包括:
- 當進程P從錯誤中恢復
- 檢測到Leader失敗
選舉流程:
- 如果P是最大的ID,直接向所有人發送Victory消息,成功新的Leader;否則向所有比他大的ID的進程發送Election消息。
- 如果P再發送Election消息後沒有收到Alive消息,則P向所有人發送Victory消息,成功新的Leader。
- 如果P收到了從比自己ID還要大的進程發來的Alive消息,P停止發送任何消息,等待Victory消息(如果過了一段時間沒有等到Victory消息,重新開始選舉流程)。
- 如果P收到了比自己ID小的進程發來的Election消息,回復一個Alive消息,然後重新開始選舉流程。
- 如果P收到Victory消息,把發送者當做Leader。
參考資料
- ^ Coulouris, George; Dollimore, Jean; Kindberg, Tim. Distributed Systems: Concepts and Design 3rd. Addison Wesley. 2000. ISBN 978-0201619188.