《云数据管理：挑战与机遇》2.1.4　领导者选举

领导者选举

很多分布式算法都需要一个进程来充当协调者，然而，实际当中选择哪个进程作为协调者通常并不重要。该问题通常被称为领导者选举（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消息。注意，多个选举可以并发执行。