环上选举算法教学课件

环上选举算法26、机遇对于有准备的头脑有特别的亲和力。27、自信是人格的核心。28、目标的坚定是性格中最必要的力量泉源之一，也是成功的利器之一。没有它，天才也会在矛盾无定的迷径中，徒劳无功。-查士德斐尔爵士。29、困难就是机遇。-温斯顿丘吉尔。30、我奋斗，所以我快乐。-格林斯潘。n基于比较的算法基于比较的算法 直观上，若一个算法在两个相对次序相同的环上直观上，若一个算法在两个相对次序相同的环上具有相具有相同的行为同的行为，则该算法是基于比较的，形式定义：，则该算法是基于比较的，形式定义：1）序相同（）序相同（order equivalent）两个环两个环x0,x1,xn-1和和y0,y1,yn-1是是(次次)序等价的，若序等价的，若对每个对每个i和和j，xixj,当且仅当当且仅当yi0)，则则它它在在前前n轮轮里里就就没没有有任任何何msg存存在在。但同样认为前但同样认为前n轮对每个结点是有用的。轮对每个结点是有用的。因因此此，若若某某一一轮轮在在任任何何次次序序等等价价的的环环上上均均无无msg发发送送，则该轮是则该轮是无用无用的，而有用的轮被称为是的，而有用的轮被称为是主动的主动的(active)。3.4.2 有限制算法的下界有限制算法的下界(nlgn)(nlgn)10 Def 3.3 在在一一个个环R上上的的一一个个执行行里里，某某轮r称称为是是active的的，若若该执行行的的第第r轮里里，某某一一个个结点点发送送一一个个msg。当当R是是从从上上下下文文已已知知时，用，用rk表示第表示第k个个active轮。Note：一旦一旦环R确定，整个容确定，整个容许执行就确定行就确定(因因为系系统同步同步)由于一个基于比由于一个基于比较的算法在等价的算法在等价环上的行上的行为相似，因此：相似，因此：对于于序序等等价价的的环R1和和R2，一一轮在在exec(R1)里里是是主主动的的当当且且仅当它在当它在exec(R2)里也是主里也是主动的。的。因因为消消息息中中的的信信息息在在k个个轮里里只只能能在在环上上通通过k个个结点点，所所以以一个一个结点在点在k轮之后的状之后的状态只依只依赖于它的于它的k-邻居。居。然然而而一一个个更更强强的的性性质是是：一一个个结点点在在第第k个个主主动轮之之后后的的状状态只只依依赖于于它它的的k-邻居居。这实际上上告告诉我我们：信信息息只只有有在在主主动轮里才能里才能获得。得。这一点在下面的引理中一点在下面的引理中给出形式出形式证明。明。3.4.2 有限制算法的下界有限制算法的下界(nlgn)(nlgn)113.4.2 有限制算法的下界有限制算法的下界(nlgn)Note：该该引引理理无无需需结结点点匹匹配配(否否则则立立即即从从定定义义3.2中中可可得得结结论论)，但但要要求求它它们们的的邻邻居居是是相相同同的的(identical)。该该引引理理要要求求假假设设两两个个环环是是次次序序等等价价的的，原原因因是是要要确确保保考考虑虑中中的的两两个执行有相同的主动轮集合，因此个执行有相同的主动轮集合，因此rk是良定义的。是良定义的。Lemma3.16 设设R1和和R2是是次次序序等等价价的的两两个个环环，设设Pi和和Pj分分别别是是R1和和R2上上具具有有相相同同k-邻邻居居的的两两个个节节点点，那那么么在在exec(R1)的的第第1至至第第rk轮轮里里Pi所所经经历历的的转转换换序序列列和和在在exec(R2)的第的第1至第至第rk轮里轮里Pj所经历的转换序列相同。所经历的转换序列相同。/该引理蕴含：在该引理蕴含：在k个主动轮结束时，个主动轮结束时，Pi和和Pj的状态相同的状态相同 Pf：非非形形式式地地，该该证证明明说说明明在在k个个主主动动轮轮之之后后，一一个个结结点点可可能能只只知知道道距距离离自自己己至至多多为为k的的那那些些结结点点。形形式式证证明明对对k进进行归纳。行归纳。123.4.2 有限制算法的下界有限制算法的下界(nlgn)归纳基础归纳基础：k=0，因为两个具有相同，因为两个具有相同0-邻居的结点有同样的邻居的结点有同样的id，故它们的状态相同；，故它们的状态相同；归归纳纳假假设设：假假定定每每两两个个具具有有相相同同(k-1)-邻邻居居的的结结点点在在(k-1)个个主动轮之后有相同的状态；主动轮之后有相同的状态；归归纳纳步步骤骤：因因为为Pi和和Pj有有相相同同的的k-邻邻居居，故故它它们们亦亦有有相相同同的的(k-1)-邻邻居居。因因此此由由归归纳纳假假设设知知，Pi和和Pj在在第第(k-1)个个主主动动轮轮之之后后处处在在相相同同的的状状态态。又又因因Pi和和Pj各各自自的的邻邻居居有有同同样样的的(k-1)-邻邻居居，故故由由归归纳纳假假设设知知，它它们们各各自自的的邻邻居居在在第第(k-1)个个主主动轮之后也处在相同的状态。动轮之后也处在相同的状态。两个主动轮之间可能有非主动轮。两个主动轮之间可能有非主动轮。因因为为在在第第(k-1)主主动动轮轮和和第第k主主动动轮轮之之间间的的轮轮(若若有有的的话话)里里，没没有有结结点点接接收收任任何何msg，故故Pi和和Pj及及各各自自的的邻邻居居均均处处在在相相同同的的状状态态(Note:Pi在在非非主主动动轮轮里里可可能能改改变变它它的的状状态，但因为态，但因为Pj有同样的转换函数，故它有同样的状态转换有同样的转换函数，故它有同样的状态转换)。133.4.2 有限制算法的下界有限制算法的下界(nlgn)在第在第k个主动轮里：个主动轮里：i)若若Pi和和Pj均不接收均不接收msg，则它们在该轮结束时有相同的状态；，则它们在该轮结束时有相同的状态；ii)因因为为Pi 和和Pj的的邻邻居居状状态态相相同同，若若Pi接接收收右右(左左)邻邻的的一一个个msg，则则Pj也也接接收收右右(左左)邻邻同同样样的的msg。因因此此，在在第第k个个主主动动轮轮结结束之后，束之后，Pi和和Pj均处于相同的状态。均处于相同的状态。下下一一引引理理将将上上述述论论断断从从具具有有相相同同k-邻邻居居的的结结点点扩扩展展至至具具有有次序等价的次序等价的k-邻居的结点。这依赖于事实：邻居的结点。这依赖于事实：A是基于比较的。是基于比较的。更更进进一一步步要要求求环环R是是有有空空隙隙的的，即即环环R中中，每每两两个个id之之间间均均有有n个个未未使使用用的的标标识识符符。形形式式地地，在在大大小小为为n的的环环上上，若若对对于于每每一一个个标标识识符符x，标标识识符符x-1到到x-n均均不不在在环环上上，则则该该环环称称为为有有空隙的。空隙的。143.4.2 有限制算法的下界有限制算法的下界(nlgn)引引理理3.16定定义义在在两两环环上上(Pi和和Pj的的k-邻邻居居相相同同)，引引理理3.17是定义在同一个环上是定义在同一个环上(Pi和和Pj的的k-邻居序等价邻居序等价)Lemma3.17 设设R是是有有空空隙隙环环，Pi和和Pj是是R上上具具有有序序等等价价k-邻邻居居的的两两个个结结点点。则则Pi和和Pj在在exec(R)的的第第1到到第第rk轮轮里里有相似的行为。有相似的行为。Pf：我们构造满足下述条件的另一个环我们构造满足下述条件的另一个环R：R中的中的Pj和和R中中Pi的有相同的的有相同的k-邻居；邻居；R中的标识符唯一中的标识符唯一R和和R序等价，序等价，R中的中的Pj匹配于匹配于R中的中的Pj。因因为为R是是有有空空隙隙环环，故故我我们们能能够够构构造造R。例例如如，对对于于k=1和和n=8有：有：153.4.2 有限制算法的下界有限制算法的下界(nlgn)R RPi的的1-邻居邻居60，90，75 Pj的的1-邻居邻居60，90，75R中中id唯一唯一R次序：次序：R次序：次序：10,30,20,40,60,90,75,100 60,90,75,91,92,94,93,95Pj与与10距离为距离为1，Pj与与60距离为距离为1163.4.2 有限制算法的下界有限制算法的下界(nlgn)(1)R上的上的Pi和和R上的上的Pj的前的前k个主动轮行为相似个主动轮行为相似(2)因因为为R上上Pi和和R上上Pj的的k-邻邻居居相相同同，由由引引理理3.16知知，Pi和和Pj在在各各自自的的exec(R)和和exec(R)的的1到到rk轮轮里里所所经经历历的的转转换换序序列列相相同同，所所以以Pi和和Pj在在各各自自的的执执行行exec(R)和和exec(R)的的1至至rk轮轮里里的的行行为为相似。相似。Pi(R)Pj(R)(2)R上的上的Pj和和R上的上的Pj的前的前k个主动轮行为相似个主动轮行为相似 因因为为算算法法是是基基于于比比较较的的，由由定定义义3.2在在两两个个序序等等价价的的环环中中，每每对对匹匹配配的的结结点点在在各各自自执执行行中中有有相相似似的的行行为为。而而R里里的的Pj和和R里里的的Pj是是匹匹配配的的，故故R里里的的Pj在在exec(R)的的1至至rk轮轮里里的的行行为为相相似似于于R里里的的Pj在在exec(R)的第的第1至至rk轮里的行为。轮里的行为。Pj(R)Pj(R)(3)R上两节点的上两节点的k-邻居序等价，则其行为在前邻居序等价，则其行为在前k个主动轮里相似个主动轮里相似 由由(1)和和(2)得得：R里里的的Pi和和Pj在在exec(R)的的1至至rk轮轮里里的的行行为为相相似似。Pi(R)Pj(R)173.4.2 有限制算法的下界有限制算法的下界(nlgn)Th3.18 对对于于每每个个n8(n是是2的的幂幂)，存存在在一一个个大大小小为为n的的环环Sn，使使得得对对每每个个基基于于比比较较的的同同步步leader选选举举算算法法A，在在Sn上上A的的容容许执行里发送许执行里发送msg的数目为的数目为(nlgn)Pf：固定算法固定算法A。证明分明分2步：步：(1)构造构造1个高度个高度对称称(很多很多结点有很多序等价的点有很多序等价的邻居居)的的环Sn；(2)Sn上上发送的送的msg总数。数。（1）构造）构造Sn（分（分2步构造）步构造）定定义大小大小为n的的环 ：对i0，n-1，设Pi的的id为rev(i)，这里里rev(i)是是i的的二二进制表示的逆序列。制表示的逆序列。183.4.2 有限制算法的下界有限制算法的下界(nlgn)例如，当例如，当n=8时有：有：若若将将环 划划分分为长度度为j(j是是2的的方方幂)的的连续片片断断，则所所有有这些些片片断断是是序序等等价价的的(Ex3.9)。片断数片断数：n/j.例如，例如，4,2,6,1和和5,3,7,0序等价序等价 2,6,1,5和和3,7,0,4序等价序等价193.4.2 有限制算法的下界有限制算法的下界(nlgn)从从 构造构造Sn 将将 上上每每个个id乘乘以以(n+1)再再加加上上n所所获得得的的Sn是是有有空空隙隙环。但。但这种种变化不改化不改变片断的序等价性。片断的序等价性。(2)Sn上上发送的送的msg总数（分数（分3步）步）求求Sn中中序等价的序等价的邻居集数目居集数目（引理（引理3.19）由由证明算法里明算法里主主动轮数目下界数目下界（引理（引理3.20）由由求求每个主每个主动轮里里发送送msg数目的下界数目的下界(引理引理3.21)由由和和的的组合即可合即可获得算法的得算法的msg复复杂性下界。性下界。203.4.2 有限制算法的下界有限制算法的下界(nlgn)Lemma3.19 对对所所有有kn/8以以及及每每个个Sn的的k-邻邻居居集集N，在在Sn中中与与N序等价的序等价的k-邻居集的个数邻居集的个数(包括包括N本身本身)大于大于 Pf：N由由2k+1个个id构构成成，设设j是是大大于于2k+1的的2的的最最小小方方幂幂。将将Sn划分为划分为n/j个连续片断，使某一片段包含个连续片断，使某一片段包含N。由由Sn的的构构造造可可知知，上上述述划划分分所所得得的的所所有有片片段段均均是是序序等等价价的。因此，的。因此，至少至少有有n/j个邻居集和个邻居集和N是序等价的。是序等价的。设设j=2i，2i-12k+12i，j213.4.2 有限制算法的下界有限制算法的下界(nlgn)Lemma3.20 在在exec(Sn)里，主动轮的数目至少为里，主动轮的数目至少为n/8。Pf：设主动轮数目设主动轮数目T8，n为2的的方方幂，存存在在一一个个大大小小为n的的环R，使得，使得A在在R上的容上的容许执行里行里发送送(nlgn)个个msgs。Pf：设A是是运运行行时间为r(n)且且满足足定定理理假假设的的算算法法。固固定定 n，设 Cn是是 满 足足 引引 理理 3.22的的 标 识 符符 集集 合合，c0,c1,cn2+2n-1是是Cn中按中按递增序排列的元素。增序排列的元素。下下面面构构造造算算法法A是是基基于于比比较的的，它它所所执行行的的环大大小小为n，标识符符集集为0,1,n2+2n-1，它它和和A有有同同样的的时间和和msg复复杂性。性。313.4.2 有限制算法的下界有限制算法的下界(nlgn)在在算算法法A中中，一一个个标识符符为i的的结点点执行行算算法法就就好好像像A在在标识符符Ci上上执行行一一样。因因为A在在Cn上上是是基基于于r(n)-比比较的的且且A在在r(n)轮里里终止止，所所以以A在在大大小小为n的的环上上是是基基于于比比较的，且的，且环上上标识符来自于集合符来自于集合0,1,n2+2n-1。由由定定理理3.18，存存在在一一个个标识符符来来自自于于0,1,n2+2n-1，大小，大小为n的的环，算法，算法A在在该环上上发送的送的msg为(nlgn)。由由A的的构构造造方方法法知知，在在大大小小为n、标识符符来来自自于于Cn的的环上上，存存在在A的的一一次次执行行，它它发送送的的msg个个数数与与A相相同同。故定理得故定理得证。Ex3.9 若若将将环 划划分分为长度度为j(j是是2的的方方幂)的的连续片片段段，则所有所有这些片段是次序等价的。些片段是次序等价的。3251、天下之事常成于困约，而败于奢靡。、天下之事常成于困约，而败于奢靡。陆游陆游52、生命不等于是呼吸，生命是活动。、生命不等于是呼吸，生命是活动。卢梭卢梭53、伟大的事业，需要决心，能力，组织和责任感。、伟大的事业，需要决心，能力，组织和责任感。易卜生易卜生54、唯书籍不朽。、唯书籍不朽。乔特乔特55、为中华之崛起而读书。、为中华之崛起而读书。周恩来周恩来谢谢！