霸道选举算法
霸道选举算法(Bully algorithm)是一种分布式选举算法,每次都会选出存活的进程中ID最大的候选者。
霸道选举算法的假设
算法假设:[1]
- 系统是同步的
- 进程在任何时候都可能失败,包括算法在执行的过程中
- 进程失败后停止工作,重启后重新工作
- 有失败监控者,它可以发现失败的进程
- 进程之间的消息传递是可靠的
- 每一个进程知道自己和其他每一个进程的ID以及地址
霸道算法的选举流程
选举过程中会发送以下三种消息类型:
- Election消息:表示发起一次选举
- Answer(Alive)消息:对发起选举消息的应答
- Coordinator(Victory)消息:选举胜利者向参与者发送选举成功消息
触发选举流程的事件包括:
- 当进程P从错误中恢复
- 检测到Leader失败
选举流程:
- 如果P是最大的ID,直接向所有人发送Victory消息,成功新的Leader;否则向所有比他大的ID的进程发送Election消息。
- 如果P再发送Election消息后没有收到Alive消息,则P向所有人发送Victory消息,成功新的Leader。
- 如果P收到了从比自己ID还要大的进程发来的Alive消息,P停止发送任何消息,等待Victory消息(如果过了一段时间没有等到Victory消息,重新开始选举流程)。
- 如果P收到了比自己ID小的进程发来的Election消息,回复一个Alive消息,然后重新开始选举流程。
- 如果P收到Victory消息,把发送者当做Leader。
参考资料
- ^ Coulouris, George; Dollimore, Jean; Kindberg, Tim. Distributed Systems: Concepts and Design 3rd. Addison Wesley. 2000. ISBN 978-0201619188.