中国科学技术大学分布式算法研究生课程市公开课一等奖百校联赛获奖课件.pptx

第三章第三章 环上选举算法环上选举算法汪汪 炀炀1第1页上上节节中中两两个个算算法法在在同同时时环环上上最最坏坏msg复复杂杂度度为为O(n)，但但两两算算法法缺点缺点为：为：它们用一个非同寻常方式使用它们用一个非同寻常方式使用id，即，即id决定决定msg延迟多长；延迟多长；在在每每个个允允许许执执行行中中，执执行行轮轮数数依依赖赖于于id，而而id相相对对于于n而而言言可能是巨大。可能是巨大。(更主要更主要)本节将说明：本节将说明：这些性质对于有效这些性质对于有效msgmsg算法而言是固有；算法而言是固有；若若一一个个算算法法中中标标识识符符仅仅用用于于比比较较，则则它它需需要要(nlgn)个个msgs；若若一一个个算算法法中中，限限制制轮轮数数上上界界，但但独独立立于于id，则则它它msg复复杂度亦为杂度亦为(nlgn)。3.4.2 有限制算法下界有限制算法下界(nlgn)(nlgn)时间复杂度会表现很差时间复杂度会表现很差2第2页n同时下界不可能从异步下界导出同时下界不可能从异步下界导出因为上节中算法表明：同时模型中附加假定是必不因为上节中算法表明：同时模型中附加假定是必不可少。可少。n同时下界对于非均匀和均匀算法均成立，但异步下界同时下界对于非均匀和均匀算法均成立，但异步下界只对均匀算法成立。只对均匀算法成立。n不过从同时导出异步结果是正确，而且提供了一个非不过从同时导出异步结果是正确，而且提供了一个非均匀算法异步下界。均匀算法异步下界。3.4.2 有限制算法下界有限制算法下界(nlgn)(nlgn)异步通信模型中领导者选举问题异步通信模型中领导者选举问题所需消息数下界为所需消息数下界为(nlgn)且且算法不依赖于比较或者限时算法不依赖于比较或者限时3第3页1.基于比较算法概念和定义基于比较算法概念和定义 为了得到下界，假定全部处理器在为了得到下界，假定全部处理器在同一轮开始执行同一轮开始执行 一一个个环环是是由由结结点点表表按按顺顺时时针针方方向向指指定定，结结点点表表开开始始于于最最小小标标识符。识符。在在同同时时模模型型里里，算算法法允允许许执执行行完完全全由由初初始始配配置置定定义义，这这是是因为因为msg延迟及节点步骤相对次序均无选择可能。延迟及节点步骤相对次序均无选择可能。系系统统初初始始配配置置完完全全由由环环决决定定，即即由由节节点点标标识识符符列列表表按按上上述述规规则则来来决决定定。当当算算法法选选择择能能够够从从上上下下文文判判断断清清楚楚时时，则则将将由由环环R确定允许执行表示为确定允许执行表示为exec(R).v匹匹配配：若若环环R1上上结结点点pi和和R2上上pj在在各各自自环环里里含含有有相相同同位位置置，则则称称pi和和pj是是匹匹配配，即即：匹匹配配结结点点在在各各自自环环上上距距其其最最小小id结结点距离相同。点距离相同。3.4.2 有限制算法下界有限制算法下界(nlgn)(nlgn)4第4页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)9第9页 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)10第10页3.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进进行行归纳。归纳。11第11页3.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有有一一样样转换函数，故它有一样状态转换转换函数，故它有一样状态转换)。12第12页3.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均不在环上，则该环称为有空隙。均不在环上，则该环称为有空隙。13第13页3.4.2 有限制算法下界有限制算法下界(nlgn)引引理理3.16定定义义在在两两环环上上(Pi和和Pjk-邻邻居居相相同同)，引引理理3.17是定义在同一个环上是定义在同一个环上(Pi和和Pjk-邻居序等价邻居序等价)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有：有：14第14页3.4.2 有限制算法下界有限制算法下界(nlgn)R RPi1-邻居邻居60，90，75 Pj1-邻居邻居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距离为距离为115第15页3.4.2 有限制算法下界有限制算法下界(nlgn)(1)R上上Pi和和R上上Pj前前k个主动轮行为相同个主动轮行为相同 因因为为R上上Pi和和R上上Pjk-邻邻居居相相同同，由由引引理理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)16第16页3.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，设设Piid为为rev(i)，这这里里rev(i)是是i二二进进制制表表示逆序列。示逆序列。17第17页3.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序等价序等价18第18页3.4.2 有限制算法下界有限制算法下界(nlgn)从从 结结构构Sn 将将 上上每每个个id乘乘以以(n+1)再再加加上上n所所取取得得Sn是是有有空空隙隙环环。但但这这种改种改变变不改不改变变片断序等价性。片断序等价性。(2)Sn上上发发送送msg总总数（分数（分3步）步）求求Sn中中序等价序等价邻邻居集数目居集数目（引理（引理3.19）由由证实证实算法里算法里主主动轮动轮数目下界数目下界（引理（引理3.20）由由求求每个主每个主动轮动轮里里发发送送msg数目数目标标下界下界(引理引理3.21)由由和和组组合即可取得算法合即可取得算法msg复复杂杂性下界。性下界。19第19页3.4.2 有限制算法下界有限制算法下界(nlgn)Lemma3.19 对对全全部部kn/8以以及及每每个个Snk-邻邻居居集集N，在在Sn中中与与N序等价序等价k-邻居集个数邻居集个数(包含包含N本身本身)大于大于 Pf：N由由2k+1个个id组组成成，设设j是是大大于于2k+12最最小小方方幂幂。将将Sn划划分分为为n/j个连续片断，使某一片段包含个连续片断，使某一片段包含N。由由Sn结结构构可可知知，上上述述划划分分所所得得全全部部片片段段均均是是序序等等价价。所所以，以，最少最少有有n/j个邻居集和个邻居集和N是序等价。是序等价。设设j=2i，2i-12k+12i，j20第20页3.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复复杂杂性。性。30第30页3.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方方幂幂)连连续续片片段段，则则全全部部这这些片段是次序等价。些片段是次序等价。31第31页