霸道选举算法

霸道选举算法(Bully algorithm)是一种分布式选举算法,每次都会选出存活的进程中ID最大的候选者

霸道选举算法的假设

算法假设:[1]

  1. 系统是同步的
  2. 进程在任何时候都可能失败,包括算法在执行的过程中
  3. 进程失败后停止工作,重启后重新工作
  4. 有失败监控者,它可以发现失败的进程
  5. 进程之间的消息传递是可靠的
  6. 每一个进程知道自己和其他每一个进程的ID以及地址

霸道算法的选举流程

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

  1. Election消息:表示发起一次选举
  2. Answer(Alive)消息:对发起选举消息的应答
  3. Coordinator(Victory)消息:选举胜利者向参与者发送选举成功消息

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

  1. 当进程P从错误中恢复
  2. 检测到Leader失败

选举流程:

  1. 如果P是最大的ID,直接向所有人发送Victory消息,成功新的Leader;否则向所有比他大的ID的进程发送Election消息。
  2. 如果P再发送Election消息后没有收到Alive消息,则P向所有人发送Victory消息,成功新的Leader。
  3. 如果P收到了从比自己ID还要大的进程发来的Alive消息,P停止发送任何消息,等待Victory消息(如果过了一段时间没有等到Victory消息,重新开始选举流程)。
  4. 如果P收到了比自己ID小的进程发来的Election消息,回复一个Alive消息,然后重新开始选举流程。
  5. 如果P收到Victory消息,把发送者当做Leader。

参考资料

  1. ^ Coulouris, George; Dollimore, Jean; Kindberg, Tim. Distributed Systems: Concepts and Design 3rd. Addison Wesley. 2000. ISBN 978-0201619188.