选举算法 Election algorithm
选择一个唯一的进程来扮演特定的角色的算法成为选举算法。
举例”中央服务器”互斥算法一个变种，从临界区的进程中选择一个进程作为”服务器”。这就需要选举算法来选举一个进程。基本要求是所有进程都同意，当进程不再相担任这个角色，需要重新选举。
.名词解释
[width=”100%”,options=”header,footer”]
|====================
| 中文 | 英文 |
| 召集选举 | call the election | 如果一个进程启动一次选举算法的一次运行。原则上N个进程可以并发召集N次选举 。
| 参与者 | participant | 它参加选举算法的某次运行
| 非参与者 | non-participant | 当前没有参加任何选举
| 协调者 | coordinator | 具有最大标识符号
| 回转时间 | turnaround time | 从启动算法到终止算法的串行消息传输的次数
| 先验知识 | priori knowledge | 每个进程只知道如何与邻居通信，且没有进程知道哪些进程有更大的标识符号。
|====================
- 对当选进程的选择必须唯一，即使若干个进程并发地召集选举。
- 我们要求选择具有最大标识的进程为当选进程。
- “标识符”可以是任何有用的值，只要标识符唯一且可按全序排序即可。
例如，通过<1/load,i>作为进程的标识符，load > 0 且 进程索引i用于负载相同的标识符排序，可以选举出最低计算负载的进程。
每个进程p~i~都有一个变量elected~i~，用于包含当选进程的标识符。
当进程第一次成为一次选举的参与者时，设elected = ⊥，标示该值还没有定义。
在算法任何一次运行期间，满足：
-
E1：安全性，参与进程p~i~有elected~i~ = ⊥，或elected~i~ = P，其中P是在运行结束时具有最大标识符号的非崩溃进程。
-
E2：活性，所有进程p~i~都参与并且最终要么设置elected~i~ ≠ ⊥，要么进程p~i~崩溃。
[WARNING] 可能有还不是参与者的进程p~j~，它在elected~i~中记录着上次当选进程的标识符。
性能：
- 使用的总的网络带宽（与发送消息的总数成比例）
- 算法的回转时间来衡量一个选举算法的性能
=== 基于环的选举算法 （A ring-based election algorithm）
The algorithm of Chang and Roberts [1979] ，这个算法舍和按照逻辑环排列的一组进程。每个进程p~i~有一个到下一个进程P~(i+1)ModN~的通信通道，所有消息顺时针传递。
假设
- 没有故障
- 系统是异步的
目标：
选举一个叫做协调者的进程，它是具有最大标识符的进程。
过程：
- 每个进程都标记为选举中的一个非参与者。任何进程都可以开始一次选举。它把自己标记为一个参与者，然后把自己的标识放到一个选举消息里，然后发给下一位。
- 当一个进程收到一个选举消息时，他比较信息里面的标识符和自己的标识符。 a. 如果消息里面的标识符大，发送给下一位。 a. 如果消息里面的标识符小，且接收进程不是一个参与者，就把消息里面的标识符替换为自己的，并转发消息；如果它已经是一个参与者，就不转发消息。 a. 任何情况下，当转发一个选举消息时，进程把自己标记为一个参与者。
- 如果收到消息是自己的，这个进程的标识符一定是最大，该进程就成为协调者。 a. 协调者再次把自己标记为非参与者并向它的邻居发送一个当选的消息，宣布它当选并将它的身份放入消息中。
- 当进程p~i~收到一个当选消息时，他把自己标记为非参与者，设置elected~i~ = 消息里的标识符，并发送给下一位，除非它是新的协调者。
满足E1，E2
[WARNING] 非参与者与参与者状态的使用方式，这种使用方式使另外一个进程同时开始进行的一次选举所引发的消息被尽可能地压制，并且总在”获胜的”选举结果宣布之前进行。
最坏情况：
如果只有一次进程启动一次选举，最坏的情况是它的上一个邻居具有最大的标识符。 then 到达这个邻居需要N-1个消息，且还需要N个消息再完成一个回路，才能宣布它的当选。 接着当选消息被发送N次，总共 3N-1个消息，回转时间也是3N-1，因为都是按照顺序发送的。
[TIP] 基于环的算法有助于理解一般选举算法的性质，但是它不容错的事实限制了它的实用价值。通过利用可靠的故障检测器，在一个进程崩溃时重构环原则上是可能的。
=== 恶霸算法（The bully algorithm） [Garcia-Molina 1982] 此进程允许选举期间进程崩溃。
与基于环算法不同：
- 这个算法假定系统是同步的：使用超时来检测崩溃。
- 基于环的算法假定进程互相之间具有最小先验知识。而此算法假定每个进程知道哪些进程有更大的标识符，并且可以和所有这些进程通信。
消息类型：
- 选举消息：宣布选举
- 应答消息：回复选举消息
- 协调者消息：宣布当选进程的身份——新的额”协调者”。
一个进程通过超时发现协调者已经出现故障，并开始一次选举。几个进程可能同时观察到此现象。
因为系统是同步的，所以可以构造一个可靠的故障检测器：
- 最大消息传输延迟为T~trans~,最大消息处理延迟为T~process~。
- 因此，我们可以计算时间 T = 2T~trans~ + T~process~,它从发送一个消息给另一个进程到收到回复的总时间的上限。
- 如果在T时间内没有收到应答，本地故障检测器可以报告请求的预期接收者已经出现故障。
算法过程：
- 知道自己有最大标识符的进程可以通过发送协调者消息给所有具有最小标识符的进程，来选举自己为协调者。
- 有较小标识符的进程通过发送选举消息给那些有较大标识符的进程来开始一次选举，并等待应答消息。 a. 如果在时间T内没有消息到达，该进程便认为自己是协调者，并发送协调者消息给所有有较小标识符的进程来宣布这一结果。 a. 否则，该进程再等待的时间T’以接收从新的协调者发送来的消息。 a. 如果消息没有到达，它开始另一次选举。
- 如果进程p~i~收到一个协调者消息，它把它的变量elected~i~设为消息中包含的协调者的标识符，并把这个进程作为协调者。
- 如果一个进程收到一个选举消息，它会送一个应答消息并开始另一次选举——除非他已经开始了一次选举。
- 当启动一个进程来替换一个崩溃进程时，他开始一次选举。如果它有最大的进程标识符，他会决定自己是协调者，并向其他进程宣布。因此即使当前协调者正在起作用，它也会成为协调者。
性能：
- 如果崩溃的进程被替换为具有相同标识符的进程，那么该算法不能保证满足安全性条件E1。
最好情况：具有第二大的标识符的进程发现了协调者的故障。它可以立即选举自己并发送N-2个协调者消息。回转时间是一个消息。
最坏情况：最小标识的进程发现了协调者的故障，然后N-1个进程一起开始选举。卖给进程都发送消息到有较大标识符的进程。需要O（N^2^）个消息。