閱讀筆記（十七）bully algorithm

一. 前言

  在分布式系統中，無論是Paxos等共識算法還是主從複制機制，都需要有一個組織者（coordinator/master），而如何選舉組織者則是一個需要解決的問題。本文介紹上司選擇算法中的bully algorithm算法。

二. 算法主要内容

1. 算法前提

  這裡程序即各個分布式的機器運作的程序，而非本機上的多程序間的操作

• 系統實作同步
• 程序随時可能失敗，包括在算法的運作期間
• 當某個程序出錯則終止，并重新開機傳回正常工作
• 在該系統中存在錯誤檢測機制檢測出錯的程序
• 各程序間消息傳遞是可靠的
• 每個程序知道自己的ID和位址，也知道其他的

  該部分前提屬于分布式系統中比較常見并易于實作的。關于系統同步可以參看這裡，關于錯誤檢測可以參看此文，程序失敗和出錯屬于8個謬論中指明的問題，而可靠通信通常采用TCP或者可靠UDP實作。

1. 消息傳遞

  bully algorithm采取以下幾種消息格式：

• 選舉消息（Election Message）: 發送選舉申明
• 回複消息（Answer (Alive) Message）：回複選舉消息
• 組織者申明消息（Coordinator (Victory) Message）：選舉獲勝者向所有節點發出申明

1. 算法核心内容

（1）如果P有着最大的ID，則發送獲勝消息給所有節點并成為組織者，否則發送選舉消息，選舉消息中使用比自己ID更大的ID

（2）如果P發送選舉消息後未收到任何回複，則廣播獲勝消息并成為組織者

（3）如果P收到一個回複帶有更大的ID，則在該次選舉中不再發送消息并等待來自組織者的申明消息。（若一段時間内未收到申明消息，則重新開機算法）

（4）如果P收到一個來自選舉消息，攜帶比自己低的ID，則回複自身ID，并啟動該選舉程序，發送選舉消息

（5）如果P收到組織者消息，則将該節點/程序标記為組織者

三. 算法分析

  該算法最終會選擇ID最大的程序作為組織者，由于會和所有節點比較，并且保證了傳輸可靠性，是以算法本身是可靠的。而考慮到整個算法過程，最壞情況下由最低節點起先發起，則會有2N的帶寬占用量，之後依次遞減，是以帶寬占用量為O（N^2)。

四. 參考文獻

https://en.wikipedia.org/wiki/Bully_algorithm