现在的位置: 首页 > 综合 > 正文

选举算法

2014年08月26日 ⁄ 综合 ⁄ 共 1570字 ⁄ 字号 评论关闭


霸道算法

性质:

1、假定系统同步,并允许在选举期间进程崩溃,利用超时来检查进程故障,所有进程知道其它进程的标识符(优先符),并和所有这些进程通信。

2、构造一个可靠的故障检测器,最大消息传输延迟为Ttrans,最大消息处理延迟为Tprocess。因此,我们可以计算时间T=2Ttrans+Tprocess,如果在T内没有收到应答,本地故障检测器可以报告请求的预期接收者已经出现故障。

3、

1)知道自己有最大标识符的进程可通过发送协调者消息给所有具有较小标识符的进程,选择自己为协调者。

2)同时,有较小标识符的进程通过发送选举消息给那些有较大标识符的进程开始选举,并等回答消息。

A)如果在时间T内没有回复消息到达,该进程便认为自己是协调者,然后发送协调者消息来宣布这一结果。

B)如果在时间T内收到了选择消息,则进程再等待时间T'以接收从新的协调者发来的消息。如果没有消息到达,说明,此次选举失败,重新启动一次选举。


假设 P 是召集选举的进程,每个召集选举的过程如下:

  1. P 向所有比自己编号大的进程发送一条 ELECTION(选举)消息。
  2. 如果 P 得不到任何回复,则 P 赢得选举,P 向所有进程发送 COORDINATOR(协调者)消息,宣布自己的胜利。
  3. 如果 P 得到任何一个回复,回复一定来自于比自己编号大的进程。P 的召集选举的工作结束,因为 P 此时已经不可能赢得选举。

其他进程或正在召集选举,或可能接收到比自己编号小的进程的 ELECTION 消息。当它收到一个 ELECTION 后,它回复一个 OK 消息给发送消息的进程;如果这时它还不是召集选举的进程,它也将开始一个召集选举的过程,即执行 1 到 3 的操作。
拥有最大编号的进程不召集选举,它直接发送 COORDINATOR 消息宣布胜利,霸道算法的名字由此得来。



环选举算法

每个进程Pi有一个到下一进程P(i+1) mod N 的通信通道, 所有消息顺时针沿着环发送。算法目标是选举一叫做协调者的进程,它具有最大标识符的进程。

1)最初,每个进程被标记为选择中的一个非参与者。任何进程可以开始一个选举,它把自己标记为一个参与者,然后把自己的标志符放到一个选举消息里,并把消息顺时针发送给它的邻居。标记,


2)当一个进程收到一个选举消息时,它比较消息里的标识符和它自己的标识符。到达的标识符大于自己的标识符,它把消息转发给它的邻居。如果到达的标识符小于自己的, 

       i)且接收进程不是一个参与者,它就把消息里的标识符替换为自己的,并转发消息;

       ii)如果已是一个参与者,它就不转发消息。

3)如果收到的标识符是接收者自己的,这个进程的标识符一定最大,该进程就成为协调者。协调者再次把自己标记为非参加者并向它的邻居发送一个当选消息,宣布它当选并将它的身份放入消息中。

4) 当进程Pi收到一个当选消息时,它把自己标记为非参与者,置变量electedi 为消息里的标志符, 并且把消息转发给它的邻居,除非它是新的协调者。


缺点: 虽然基于环选举算法有助于理解一般的选举算法,但它不容错的事实限制了它的实用价值。然而,可以通过可靠的故障检测器,在一个进程崩溃时重构环原则上是可能的。




霸道选举算法和环选举算法都依赖一系列苛刻的假设:

  1. 假设了可靠的通道通信,更进一步的假设是系统中任何两个进程之间都可以通信。
  2. 每个进程都知道其他进程的编号,也就是说算法依赖一个全局的数据。
  3. 在多个并发召集选举的过程中,进程组的正常进程数量保持稳定,而且在环选举算法中,环结构也必须稳定。
  4. 假设进程能够明确地判断出一个正常运行的进程和一个已经崩溃的进程。

有很多放宽假设条件下如何改进算法的讨论,但就算法的应用来说,召集选举的过程不应该是很频繁的,参与选举的进程数量和结构应该是相对稳定的。我们看不到频繁故障下的频繁选举的应用价值。因此,虽然算法的适用条件比较苛刻,但它们基本能够满足应用的需求。


抱歉!评论已关闭.