基本介紹
- 中文名：霸道選舉算法
- 外文名：Bully algorithm
- 別名：霸道算法、欺負算法
- 發明人：Garcia-Monila
- 創建時間：1982年
- 類別：分散式選舉算法
簡介,霸道選舉算法的假設,霸道算法的選舉流程,示例,
簡介
Garcia-Monila 在 1982 年的一篇論文中發明了所謂的霸道選舉算法（Bully Algorithm）。其基本思想是：當一個進程P發現協調者不再回響請求時，就判定協調者出現故障，於是它就發起選舉，選出新的協調者，即當前活動進程中進程號最大者。
霸道選舉算法的假設
- 系統是同步的
- 進程在任何時候都可能失敗，包括算法在執行的過程中
- 進程失敗後停止工作，重啟後重新工作
- 有失敗監控者，它可以發現失敗的進程
- 進程之間訊息傳遞是可靠地
- 每一個進程知道自己和其他每一個進程的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
示例
以8個進程為例，由於進程7的崩潰，進程3第1個注意到這一點，因此，由進程3發起新的選舉。
- 進程3向比它大的進程4傳送選舉訊息，如圖(a)。
- 進程4收到這一訊息，向進程3傳送接管訊息OK，如圖(b)。
- 進程4向比它大的進程5傳送選舉訊息。
- 進程5收到這一訊息，向進程4傳送接管訊息OK。
- 進程5向比它大的進程6傳送選舉訊息。
- 進程6收到這一訊息，向進程5傳送接管訊息OK。
- 進程6向比它大的進程7傳送選舉訊息，發現進程7故障，如圖(c)。
- 進程6最終取得了協調權，向所有進程傳送協調者訊息，開始協調工作，如圖(d)。
霸道選舉算法舉例