《雲數據管理：挑戰與機遇》2.1.4　領導者選舉

本節書摘來自華章出版社《雲數據管理》一書中的第2章，第1節，作者迪衛艾肯特·阿格拉沃爾，更多章節內容可以訪問雲棲社區“華章計算機”公眾號查看

領導者選舉

很多分布式算法都需要一個進程來充當協調者，然而，實際當中選擇哪個進程作為協調者通常並不重要。該問題通常被稱為領導者選舉（leader election），其關鍵在於要確保一個唯一的協調者被選中。該協議非常簡單，通常要求每個進程有一個進程編號，所有的進程編號都是唯一並且完全排序的。我們使用具有代表性的Bully算法（Bully Algorithm [Garcia-Molina, 1982]）來對該協議進行舉例，該算法假設通信是可靠的。其核心思想是努力選擇具有最大進程編號的進程。任何一個進程，如果該進程剛從故障中恢複，或者該進程懷疑當前的協調者失效了，都可以發起新的選舉。有三類消息可以使用：election、ok和I won。

進程可以同時發起選舉。發起進程p向所有擁有較高ID的進程發送一個election消息，並等待ok消息。如果沒有收到任何ok消息，則p成為協調者，並向所有擁有較低ID的進程發送I won消息。如果該進程收到ok消息，則退出並等待I won消息。如果一個進程收到了election消息，可以返回。一個ok消息，並發起一個新的選舉。如果進程收到了一個I won消息，則發送者就是協調者。很容易證明Bully算法的正確性。選舉協議也可以利用邏輯通信結構或者覆蓋網絡（如環）來實現。Chang and Roberts [1979]設計了這種協議，該協議把所有的節點組織成一個邏輯環，其中每一個進程都知道它的近鄰，目的也是選擇具有最大ID的進程作為協調者。一個進程如果剛剛恢複或者檢測到協調者失效，可以發起新的選舉。該進程按順序對後繼節點進行詢問，直到發現活動節點，就把election消息發送給下遊最近的活動節點。每一個接收到election消息的進程把自己的ID添加到該消息中並順著環繼續傳遞。一旦消息返回到發起者，就選擇具有最大ID的節點作為領導者並順著環發布一個特殊的coordinator消息。注意，多個選舉可以並發執行。