文档介绍：*第二部分分布式算法 第五次课中国科学技术大学计算机系国家高性能计算中心(合肥)*第三章环上选举算法*本章提纲Leader选举问题匿名环异步环同步环*问题 在一组处理器中选出一个特殊结点作为leader用途简化处理器之间的协作; 有助于达到容错和节省资源。 例如,有了一个leader,就易于实现广播算法代表了一类破对称问题。 例如,当死锁是由于处理器相互环形等待形成时,可使用选举算法,找到一个leader并使之从环上删去,即可打破死锁。*§:问题从具有同一状态的进程配置开始,最终达到一种配置状态。每个处理器最终确定自己是否是一个leader,但只有一个处理器确定自己是leader,而其他处理器确定自己是non-leader。算法的作用:如果要执行一个分布式算法,且没有一个优先的优选人做为算法的初始进程,就要进行进程选举。(例如指定根的DFS树的生成问题)*§:(1)每个处理器具有相同的局部算法;(2)算法是分布式的,处理器的任意非空子集都能开始一次计算;(3)每次计算中,算法达到终止配置。在每一可达的终止配置中,只有一个处理器处于领导人状态,其余均处于失败状态。一个算法解决了leader选举问题需满足(根据形式化模型):终止状态被划分为两类:选中和未选中状态。一旦一个处理器进入选中(或未选中)状态,则该处理器上的转换函数将只会将其变为相同的状态;在每个容许执行里,只有一个处理器进入选中状态,其余处理器进入非选中(non-selected)状态。 本章只讨论系统的拓扑结构是环的情况。(此项有时可以弱化)*§ 对每个i,0≤i≤n-1, Pi到Pi+1的边标号为1,称为左(顺时针) Pi到Pi-1的边标号为2,称为右(逆时针) 这里的标号加减均是modn的环网络之所以吸引了如此多的研究,是因为它们的行为易于描述;且从环网络推导出的下界,可应用于具有任意拓扑结构的网络算法设计*§(anonymous)匿名算法:若环中处理器没有唯一的标识符,则环选举算法是匿名的。更形式化的描述:每个处理器在系统中具有相同的状态机,在这种算法里,msg接收者只能根据信道标号来区别。(一致性的)uniform算法:若算法不知道处理器数目,则算法称之为uniform,因为该算法对每个n值看上去是相同的。non-uniform算法:算法已知处理器数目n形式化描述:在一个匿名、一致性的算法中,所有处理器只有一个状态机;在一个匿名、非一致性的算法中,对每个n值(处理器数目)都有单个状态机,但对不同规模有不同状态机,也就是说n可以在代码中显式表达。*§(anonymous)对于环系统,不存在匿名的选举算法。 为简单起见,我们只证明 非均匀(非一致性)算法:非均匀算法(n已知)的不可能性=>均匀(n未知)算法的不可能性。、一致性的领导者选举算法。 同步算法:同步算法的不可能性=>异步算法的不可能性。(同步是异步的一种特例)。*§,一个算法以轮的形式进行。每轮里所有待发送msg被传递,随后每个处理器进行一步计算。一个处理器的初始状态包括在outbuf里的任何msg。这些消息在第一轮里被传递到某处理器的左和右邻居。 不可能性:①在一个匿名环中,处理器间始终保持对称,若无某种初始的非对称(如,标识符唯一),则不可能打破对称。在匿名环算法里,所有处理器开始于相同状态。②因为他们执行同样的程序(即他们的状态机相同),在每轮里各处理器均发送同样的msg,所以在每一轮里各处理器均接收同样的msg,改变状态亦相同。因此,若选中一个处理器,则其他所有处理器亦被选中。因此,不可能有一个算法在环中选中单个处理器为leader。