一致性的领导者选举算法同步算法.ppt

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