阅读笔记（十七）bully algorithm

一. 前言

  在分布式系统中，无论是Paxos等共识算法还是主从复制机制，都需要有一个组织者（coordinator/master），而如何选举组织者则是一个需要解决的问题。本文介绍领导选择算法中的bully algorithm算法。

二. 算法主要内容

1. 算法前提

  这里进程即各个分布式的机器运行的进程，而非本机上的多进程间的操作

• 系统实现同步
• 进程随时可能失败，包括在算法的运行期间
• 当某个进程出错则终止，并重启返回正常工作
• 在该系统中存在错误检测机制检测出错的进程
• 各进程间消息传递是可靠的
• 每个进程知道自己的ID和地址，也知道其他的

  该部分前提属于分布式系统中比较常见并易于实现的。关于系统同步可以参看这里，关于错误检测可以参看此文，进程失败和出错属于8个谬论中指明的问题，而可靠通信通常采用TCP或者可靠UDP实现。

1. 消息传递

  bully algorithm采取以下几种消息格式：

• 选举消息（Election Message）: 发送选举申明
• 回复消息（Answer (Alive) Message）：回复选举消息
• 组织者申明消息（Coordinator (Victory) Message）：选举获胜者向所有节点发出申明

1. 算法核心内容

（1）如果P有着最大的ID，则发送获胜消息给所有节点并成为组织者，否则发送选举消息，选举消息中使用比自己ID更大的ID

（2）如果P发送选举消息后未收到任何回复，则广播获胜消息并成为组织者

（3）如果P收到一个回复带有更大的ID，则在该次选举中不再发送消息并等待来自组织者的申明消息。（若一段时间内未收到申明消息，则重启算法）

（4）如果P收到一个来自选举消息，携带比自己低的ID，则回复自身ID，并启动该选举进程，发送选举消息

（5）如果P收到组织者消息，则将该节点/进程标记为组织者

三. 算法分析

  该算法最终会选择ID最大的进程作为组织者，由于会和所有节点比较，并且保证了传输可靠性，因此算法本身是可靠的。而考虑到整个算法过程，最坏情况下由最低节点起先发起，则会有2N的带宽占用量，之后依次递减，所以带宽占用量为O（N^2)。

四. 参考文献

https://en.wikipedia.org/wiki/Bully_algorithm