分布式算法设计基础(第七章)

《分布式算法设计基础(第七章)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第7章选举算法在对各种应用程序或分布式系统设计分布式算法时，一些一般性的问题经常可以看成是一种选举问题，选举问题成为分布式计算的基木问题。选举问题：从具有同一地位(状态)的进程的形态开始，系统最后到达一个形态，在这个形态，进程中有一个进程处于leaded领导人)地位(状态)，而其他所有进程则处于be(落选)状态。例如，要启动集中式算法，且没有一个优先的候选人作为算法的初始进程，就需要先进行进程的选举。有大量的分布式计算问题可以归结为选举问题，形成了一套一般化的理论，木章按照下列准则进行选举。(1)同步系统

2、、匿名进程和容错算法在后续章节中讨论，我们这里总是假设进程和通信是可靠的，系统是完全异步的，以唯一标识区别进程。(2)比较不同计算模型的效率，选举问题起着"基准问题”(benchmarkingproblem)的作用。这里只涉及到比较中所需要的一些结果。(3)集中讨论消息复杂度、有改进的时间复杂度的算法。不讨论在时间复杂度和消息复杂度之间权衡、折衷后所得的结果。7.1引言选举问题的概述前面已经介绍，其定义如下。定义7.1选举算法是满足下列性质的算法：(1)每个进程有相同的局部算法；(2)算法是分散式的，即进

3、程的任意非空子集都能开始一次选举计算；(3)在每次计算屮，算法将到达终止形态。在每一个可达的终止形态屮，只有一个进程处于领导人状态，其他进程则处于落选状态。第三个性质有时可以弱化，只有一个进程处于领导人状态，被选出的领导人得知自己已经当选了，而其他进程可能还不知道自己落选了。约定：本章所有的算法屮，进程p有变量statei)9其可能的取值为leader(领导人)和(落选)。有时我们还假设在〃执行算法的任何步骤之前，呦妬的为sleep.如果p已经参与了选举，但还不知道它是否赢得了选举，则设也©的值为3加(候

4、选人)。有的算法还使用主动的或现役的(active)＞被动的(passive)等状态，将在算法中予以说明。1.本章的假设我们假设：木章所讨论的选举问题及其算法，均是在下列假设下进行的：(1)系统是完全异步的假设进程不能访问公共时钟，消息传输时间可以任意延迟，但延迟时间有限。(2)每个进程具有唯一的标识，而且其标识初始时对于进程是可知的我们常以#标识进程〃。这样可以给进程带上某种可比较大小的标识，从而把选举问题转化为求极大/极小值问题。(3)本章中与以比较为基础的算法有关的一些结果本章讨论的算法实际上是以比

5、较为基础的算法，这样，可以利用以前以比较为基础的算法的一些结果。(4)每条消息最多可能包含w位，具有0@)的消息复杂度这样做可以公平地比较不同算法的通信复杂度。2•选举算法与波动算法进程标识可以用来打破进程之间的对称性。可以这样设计算法，使得具有最小标识的进程就是所选举的进程。于是，按照上一节计算下确界的结果，在一次波动计算中，进程可以计算出最小标识。这表明，可以执行最小标识的一次波动来进行选举，执行之后，具有这个最小标识的进程就成为领导人。由于选举算法必须是分散式的，这个原理只能用于分散式的波动算法。(

6、1)基于树算法的选举算法如果网络的拓扑结构是树，或者网络的牛成树可用，就可以使用网络的树算法进行选举。在树选举算法中，要求至少所有的叶子结点是算法的初始进程。为了让所有的叶子进程成为初始进程，我们可以增加一个唤醒阶段。想要启动选举的进程将消息〈wakeup＞扩散到所有进程中，布尔变量咖用于控制每个进程至多发送一次消息，变量⑷厂用于对进程接收的消息〈wakeup＞计数。当进程通过每条通道接收到消息〈wakeup＞^,就开始执行图6-3所示的算法，通过扩充6-3的算法，进行最小标识的计算，并使每个进程判定。当

7、进程进行判定时，就知道了领导人的标识。如果该标识与进程标识相等，它就称为领导人，否则就成为落选进程。算法7-1initfalse;init0;initfalsevarW5P:booleanw/p:integerrec^q]:booleeinforeachqNeigh^vP:Pinitp;state。:{sleep,leader^lost}initsleep;beginifp是初始进程thenbeginwsp:=true;forallqWNeighpdosendtoqend;whi.leh

8、tp<#Neighpdobeginreceive〈wakeup〉;vvrp:=vvrp+l;ifnotW5PthenbeginwsP:=true;forallqNeighpdosendtoqendend;/*现在开始树算法*/whi.le#{qIrec^[q}>1dobeginreceivefromq/*继续收来自邻居q的令牌消息*/reCp[ty]:=true；vp:=min{vp,r}en