分布式中的选举算法

很多分布式算法需要有一个进程作为协作者。下面介绍一些常用的选举算法。

传统的选举算法

欺负算法

当任何一个进程发现协作者不再响应请求时，它就发起一次选举。

算法实现如下：

1. P向所有编号比它大的进程发送一个ELECTION消息
2. 如果无人响应，P获胜并成为协作者
3. 如果有编号比它大的进程响应，则有响应者接管选举工作。P的工作完成。
4. 将选举获胜的消息发送给所有进程，通知这些进程自己是新的协作者。
5. 当一个以前崩溃了的进程现在恢复过来时，它将主持一次选举。如果该进程恰好是当前正在运行的进程中进程号最大的进程，它将赢得此次选举，接管协作者的工作。这样，最大的进程总是取胜，故称为“欺负算法”。

环算法

1. 当任何一个进程注意到协作者不工作时，它就构造一个带有它自己的进程号的ELECTION消息，并将该消息发送给它的后继者。
2. 如果后继者崩溃了，发送者沿着此环跳过它的后继者发送给下一个进程，或者再下一个，直到找到一个正在运行的进程。
3. 在每一步中，发送者都将自己的进程号加到该消息列表中，以使自己成为协作者的候选人之一。
4. 最终，消息返回到发起此次选举的进程。当发起者进程接收到一个包含它自己进程号的消息时，它就识别出这个事件。
5. 此时，消息类型变成COORDINATIOR消息，并再一次绕环运行，向所有进程通知谁是协作者（成员列表中进程号最大的那个）以及新环中的成员都有谁。
6. 这个消息在循环一周后被删除，随后每个进程都恢复原来的工作。
7. 如果有多个ELECTION消息，那么循环多周后被删除。