选举算法

霸道算法

Garcia-Monila 在 1982 年的一篇论文中发明了所谓的霸道选举算法（Bully Algorithm）。当一个进程 P 发现协调者进程不再响应时，这个进程就召集选举。由于进程的独立性，在同一个时刻，系统中可能有多个召集选举的过程。假设 P 是召集选举的进程，每个召集选举的过程如下：

1. P 向所有比自己编号大的进程发送一条 ELECTION（选举）消息。
   如果 P 得不到任何回复，则 P 赢得选举，P 向所有进程发送 COORDINATOR（协调者）消息，宣布自己的胜利。
2. 如果 P 得到任何一个回复，回复一定来自于比自己编号大的进程。P 的召集选举的工作结束，因为 P 此时已经不可能赢得选举。
3. 其他进程或正在召集选举，或可能接收到比自己编号小的进程的 ELECTION 消息。当它收到一个 ELECTION 后，它回复一个 OK 消息给发送消息的进程；如果这时它还不是召集选举的进程，它也将开始一个召集选举的过程，即执行 1 到 3 的操作。
   拥有最大编号的进程不召集选举，它直接发送 COORDINATOR 消息宣布胜利，霸道算法的名字由此得来。

环选举算法

关于选举的另一个著名算法是基于进程环的机制设计的。与一般的环算法不同的是，环选举算法并不使用令牌。在这个算法中，我们假设所有进程能够在物理上或逻辑上组成一个环结构，每个进程都保留一个按进程编号逻辑排序的一个表，因此知道自己的所有后继进程。

算法的过程非常简单。当一个进程 P 注意到协调者进程不再工作时，它将启动一个召集选举的过程：

1. 进程 P 构造一个包含自己进程编号的 ELECTION 给后继进程，如果直接后继进程没有响应，进程 P 就将消息发送给环上的下一个进程，直到找到一个正常运行的进程。

2. 接收到 ELECTION 消息的进程将自己的编号增加到 ELECTION 消息中，然后按照同样的方式将消息发送给后继进程。

3. 这样，消息在环上的传递将构造一个包含所有正常运行的进程的编号表。

4. 当 ELECTION 消息最后回到召集选举的进程时，消息中最大编号的进程即成为选举的胜利者。

5. 召集选举的进程将消息类型改为 COORDINATOR，然后将消息沿着环重新发送一次，将选举结果通知所有的进程。

6. 当 COORDINATOR 消息重新回到召集选举的进程时，算法终止。
   同样，在环选举算法中，也可能同时存在多个召集选举的过程。当在这个时刻环结构不变时，最后的结果也是一致的，只是消息数量多一些，并无大碍。

关于选举算法的讨论

霸道选举算法和环选举算法都依赖一系列苛刻的假设：

假设了可靠的通道通信，更进一步的假设是系统中任何两个进程之间都可以通信。
每个进程都知道其他进程的编号，也就是说算法依赖一个全局的数据。
在多个并发召集选举的过程中，进程组的正常进程数量保持稳定，而且在环选举算法中，环结构也必须稳定。
假设进程能够明确地判断出一个正常运行的进程和一个已经崩溃的进程。
有很多放宽假设条件下如何改进算法的讨论，但就算法的应用来说，召集选举的过程不应该是很频繁的，参与选举的进程数量和结构应该是相对稳定的。我们看不到频繁故障下的频繁选举的应用价值。因此，虽然算法的适用条件比较苛刻，但它们基本能够满足应用的需求。