简介

Garcia-Monila 在 1982 年的一篇论文中发明了所谓的霸道选举算法（Bully Algorithm）。其基本思想是：当一个进程P发现协调者不再响应请求时，就判定协调者出现故障，于是它就发起选举，选出新的协调者，即当前活动进程中进程号最大者1。

霸道选举算法的假设

1. 1.

   系统是同步的

2. 2.

   进程在任何时候都可能失败，包括算法在执行的过程中

3. 3.

   进程失败后停止工作，重启后重新工作

4. 4.

   有失败监控者，它可以发现失败的进程

5. 5.

   进程之间消息传递是可靠地

6. 6.

   每一个进程知道自己和其他每一个进程的id以及地址

霸道算法的选举流程

选举过程中会发送以下三种消息类型：

1. 1.

   Election消息：表示发起一次选举

2. 2.

   Answer(Alive)消息：对发起选举消息的应答

3. 3.

   Coordinator(Victory)消息：选举胜利者向参与者发送选举成功消息

触发选举流程的事件包括：

1. 1.

   当进程P从错误中恢复

2. 2.

   检测到Leader失败

选举流程：

1. 1.

   如果P是最大的ID，直接向所有人发送Victory消息，成功新的Leader；否则向所有比他大的ID的进程发送Election消息

2. 2.

   如果P再发送Election消息后没有收到Alive消息，则P向所有人发送Victory消息，成功新的Leader

3. 3.

   如果P收到了从比自己ID还要大的进程发来的Alive消息，P停止发送任何消息，等待Victory消息（如果过了一段时间没有等到Victory消息，重新开始选举流程）

4. 4.

   如果P收到了比自己ID小的进程发来的Election消息，回复一个Alive消息，然后重新开始选举流程

5. 5.

   如果P收到Victory消息，把发送者当做Leader

示例

以8个进程为例，由于进程7的崩溃，进程3第1个注意到这一点，因此，由进程3发起新的选举。

• 进程3向比它大的进程4发送选举消息，如图(a)。

• 进程4收到这一消息，向进程3发送接管消息OK，如图(b)。

• 进程4向比它大的进程5发送选举消息。

• 进程5收到这一消息，向进程4发送接管消息OK。

• 进程5向比它大的进程6发送选举消息。

• 进程6收到这一消息，向进程5发送接管消息OK。

• 进程6向比它大的进程7发送选举消息，发现进程7故障，如图(c)。

• 进程6最终取得了协调权，向所有进程发送协调者消息，开始协调工作，如图(d)。

霸道选举算法举例

参考资料