分布式算法-同步環(huán)

1、1第二部分 分布式算法第六次課中國(guó)科學(xué)技術(shù)大學(xué)計(jì)算機(jī)系 國(guó)家高性能計(jì)算中心（合肥）22 3.4 同步環(huán)研究同步環(huán)上leader選舉問(wèn)題的上、下界。上界： 提出兩個(gè)msg復(fù)雜性為O(n)的算法，顯然，這樣的算法的msg復(fù)雜性是最優(yōu)的。但運(yùn)行時(shí)間并非只與環(huán)大小n有關(guān)，還與算法使用的非普通的id相關(guān)。(與id值相關(guān))下界： 討論 1）只基于標(biāo)識(shí)符之間比較的算法2）時(shí)間受限（即若干輪內(nèi)終止，輪數(shù)只依賴(lài)于環(huán)大小,不依賴(lài)于id值）的算法當(dāng)算法受限于上述兩個(gè)條件時(shí)，至少需要(nlgn)個(gè)msgs.33 3.4.1 上界 O(n)上節(jié)已證明在異步環(huán)上leader選舉問(wèn)題的msg復(fù)雜度下界為(nlgn) ，其算

2、法的關(guān)鍵是msg延遲是任意長(zhǎng)的。因?yàn)橥江h(huán)上 1) msg延遲是確定的，故同步模型是否有較好的結(jié)果呢?2) 獲取info不僅來(lái)自于接收msg,在某輪里的內(nèi)附件也能獲取info本節(jié)提出兩個(gè)算法，msg復(fù)雜性上界為O(n),針對(duì)單向環(huán)，但是用于雙向環(huán)1) 非均勻的：要求環(huán)中所有的結(jié)點(diǎn)開(kāi)始于同一輪，標(biāo)準(zhǔn)的同步模型 (需知道n)2) 均勻的： 結(jié)點(diǎn)可開(kāi)始于不同輪，弱同步模型 (無(wú)需知道n)4Non-uniform Alg基本特征選擇環(huán)中最小id（各id互不相同）的結(jié)點(diǎn)作為leader，按Phase運(yùn)行，每個(gè)階段由n個(gè)輪組成。在Phase i (i 0)，若存在一個(gè)id為i的結(jié)點(diǎn)，則該結(jié)點(diǎn)為leader

3、，并終止算法，因此，最小id的結(jié)點(diǎn)被選為leader顯然，Phase數(shù)目取決于n個(gè)節(jié)點(diǎn)的標(biāo)志符的取值。具體實(shí)現(xiàn)Phase i包括輪：ni+1, ni+2, , ni+n 在第i階段開(kāi)始，若一個(gè)結(jié)點(diǎn)的id是i，且它尚未終止，則該節(jié)點(diǎn)繞環(huán)發(fā)送一個(gè)msg后作為一個(gè)leader終止；若一結(jié)點(diǎn)的id不是i，且它收到一個(gè)msg，則它轉(zhuǎn)發(fā)此msg后作為non-leader終止。3.4.1 上界O(n)5分析正確性：顯然，只有最小的標(biāo)志符被選中作為leaderMsg復(fù)雜性：恰有n個(gè)msg被發(fā)送，故復(fù)雜性為O(n)。注意這n個(gè)msg均是在找到leader的那個(gè)Phase里發(fā)送的。時(shí)間復(fù)雜性依賴(lài)于環(huán)大小和環(huán)上最小

4、標(biāo)志符，不妨設(shè)環(huán)大小為n，最小標(biāo)識(shí)符為i，則算法執(zhí)行輪數(shù)為：n(i+1)，不妨設(shè)i0 /運(yùn)行時(shí)間與環(huán)大小及標(biāo)識(shí)符取值相關(guān)缺點(diǎn)必須知道環(huán)大小n和同步開(kāi)始，下面算法克服了這些限制為什么id為i的結(jié)點(diǎn)要在phase i發(fā)msg各結(jié)點(diǎn)互不知道彼此的id值只能在第i phase，結(jié)點(diǎn)(id=i)發(fā)自己的id為什么每個(gè)phase要n輪3.4.1 上界O(n)6Uniform Alg特點(diǎn)：無(wú)須知道環(huán)大小，弱同步模型一個(gè)處理器可以在任意輪里自發(fā)地喚醒自己，也可以是收到另一個(gè)處理器的msg后被喚醒基本思想 源于不同節(jié)點(diǎn)的msg以不同的速度轉(zhuǎn)發(fā) 源于id為i的節(jié)點(diǎn)的msg，在每一個(gè)接收該msg的節(jié)點(diǎn)沿順時(shí)針轉(zhuǎn)發(fā)到

5、下一個(gè)處理器之前，被延遲2i-1輪 為克服非同時(shí)啟動(dòng)，須加一個(gè)基本的喚醒階段，其中每個(gè)自發(fā)喚醒的結(jié)點(diǎn)繞環(huán)發(fā)送一個(gè)喚醒msg，該msg轉(zhuǎn)發(fā)時(shí)無(wú)延遲 若一個(gè)結(jié)點(diǎn)在算法啟動(dòng)前收到一個(gè)喚醒msg，則該結(jié)點(diǎn)不參與算法，只是扮演一個(gè)relay(轉(zhuǎn)發(fā))角色：即轉(zhuǎn)發(fā)或沒(méi)收msg3.4.1 上界O(n)7要點(diǎn)：在基本階段之后，選舉leader是在參與結(jié)點(diǎn)集中進(jìn)行的，即只有自發(fā)喚醒的結(jié)點(diǎn)才有可能當(dāng)選為leader。具體實(shí)現(xiàn) 喚醒：由一個(gè)結(jié)點(diǎn)發(fā)出的喚醒msg包含該結(jié)點(diǎn)的id，該msg以每輪一邊的正常速率周游，那些接收到喚醒msg之前未啟動(dòng)的結(jié)點(diǎn)均被刪除(不參與選舉) 延遲：當(dāng)來(lái)自一個(gè)id為i的節(jié)點(diǎn)的msg到達(dá)一個(gè)醒

6、著的節(jié)點(diǎn)時(shí)，該msg以2i速率周游，即每個(gè)收到該msg的節(jié)點(diǎn)將其延遲2i-1輪后再轉(zhuǎn)發(fā)。Note： 一個(gè)msg到達(dá)一個(gè)醒著的節(jié)點(diǎn)之后，它要到達(dá)的所有節(jié)點(diǎn)均是醒著的。一個(gè)msg在被一個(gè)醒著的節(jié)點(diǎn)接收之前是處在1st階段 (喚醒msg，非延遲) ，在到達(dá)一個(gè)醒著的節(jié)點(diǎn)之后，它就處于2nd階段，并以2i速率轉(zhuǎn)發(fā)(非喚醒msg，延遲)3.4.1 上界O(n)8 沒(méi)收規(guī)則a) 一個(gè)參與的節(jié)點(diǎn)收到一個(gè)msg時(shí)，若該msg里的id大于當(dāng)前已看到的最小(包括自己)的id，則沒(méi)收該msg；b) 一個(gè)轉(zhuǎn)發(fā)的節(jié)點(diǎn)收到一個(gè)msg時(shí)，若該msg里的id大于當(dāng)前已看到的最小(不包括自己)的id，則沒(méi)收該msg。3.4.1

7、 上界O(n)9算法 Alg3.2 同步leader選舉var waiting : init ; asleep : init true; /加上relay更好 ？ : init false;1: 設(shè)R是計(jì)算事件中接收msg的集合2: s:= ;/ the msg to be sent3: if asleep then 4: asleep:=false;5: if R = then / pi未收到過(guò)msg，屬于自發(fā)喚醒6: min:=id; /參與選舉7: s:=s+; / 準(zhǔn)備發(fā)送 else /已收到過(guò)msg，但此前未啟動(dòng)，被喚醒故Pi不參與8: min:=; /選舉，置min為 ，使其變?yōu)閞

8、elay結(jié)點(diǎn) / relay:=true; ？ 3.4.1 上界O(n)109: for each in R do / 處理完收到的m后相當(dāng)于從R中刪去10: if m min then / 收到的id較小時(shí)通過(guò)11: become not elected; / Pi未被選中 /可用relay控制使轉(zhuǎn)發(fā)節(jié)點(diǎn)不延遲？12: 將加入waiting且記住m何時(shí)加入; /m加入延遲轉(zhuǎn)發(fā)13: min:=m; / if m min then it is swallowed14: if m=id then become elected; / Pi被選中 /endfor15: for each in wai

9、ting do16: if 是在2m-1輪之前接收的 then17: 將從waiting中刪去并加入S18: send S to left; 3.4.1 上界O(n)11分析 下面證明，在第1個(gè)結(jié)點(diǎn)被喚醒之后的n輪，只剩下第二階段的msg，只有參與的結(jié)點(diǎn)才有可能被選中。 (1) 正確性 對(duì)i0,n-1，設(shè)idi是結(jié)點(diǎn)pi的標(biāo)識(shí)符，是源于pi的msgLemma 3.9 在參與的節(jié)點(diǎn)中，只有最小id的節(jié)點(diǎn)才能收回自己的id。pf：選中：設(shè)pi是參與者中具有最小id的結(jié)點(diǎn)(Note：至少有1個(gè)結(jié)點(diǎn)須參與算法)，顯然沒(méi)有節(jié)點(diǎn)(無(wú)論是否參與)能沒(méi)收；另一方面，因?yàn)樵诿總€(gè)節(jié)點(diǎn)上至多延遲2idi輪，故pi最

10、終收回自己的id；唯一：除pi外，沒(méi)有別的節(jié)點(diǎn)pj ( ji ) 也收回自己的。 若pj收回自己的 ，則已通過(guò)pi及其它所有結(jié)點(diǎn)，但idi idj，因?yàn)閜i是一個(gè)參與者，它將不會(huì)轉(zhuǎn)發(fā)idj，矛盾！ 該引理蘊(yùn)含著：恰有一個(gè)結(jié)點(diǎn)收回自己的msg，故它是唯一聲明自己是leader的結(jié)點(diǎn)，即算法正確。3.4.1 上界O(n)12 (2) msg復(fù)雜性在算法的一次容許執(zhí)行里，發(fā)送的msg可分為三個(gè)類(lèi)型：第一類(lèi)：第一階段的msg(喚醒msg)第二類(lèi)：最終leader的msg進(jìn)入自己的第二階段之前發(fā)送的 第二階段msg(其它結(jié)點(diǎn)發(fā)出的)第三類(lèi)：最終leader的msg進(jìn)入自己的第二階段之后發(fā)送的 第二階段m

11、sg(包括leader發(fā)出的)Note：一個(gè)msg發(fā)送時(shí)，一開(kāi)始是作為喚醒msg(非延遲)，當(dāng)它到達(dá)的結(jié)點(diǎn)已喚醒時(shí)，msg就變?yōu)榉菃拘裮sg(第二階段，延遲msg)3.4.1 上界O(n)13 第一類(lèi)msg總數(shù)(第一階段的msg)Lemma 3.10 第一類(lèi)msg總數(shù)至多為npf：只要說(shuō)明每個(gè)節(jié)點(diǎn)在第一階段至多轉(zhuǎn)發(fā)一個(gè)msg即可。反證：假設(shè)某結(jié)點(diǎn)pi在其第一階段轉(zhuǎn)發(fā)兩個(gè)msgs：一個(gè)來(lái)自pj的，一個(gè)來(lái)自pk的。不失一般性，pj比pk更靠近pi(沿順時(shí)針?lè)较?。因此，到達(dá)pi之前先到達(dá)pj。 若是在pj自發(fā)喚醒及發(fā)送之后到達(dá)pj，則以2idk速度作為第二階段msg繼續(xù)前進(jìn)；否則，pj不是參與結(jié)點(diǎn)

12、，不會(huì)發(fā)送。 因此，或者是作為第二階段msg到達(dá)pi，或者未被發(fā)送，即：pi最多收到一個(gè)第一階段msg，矛盾！3.4.1 上界O(n)14 第二類(lèi)msg總數(shù) (最終leader發(fā)出的msg進(jìn)入自己的第二階段之前發(fā)送的第二階段msg) 為了求得第二類(lèi)msg總數(shù)，首先說(shuō)明第一個(gè)開(kāi)始執(zhí)行算法的結(jié)點(diǎn)啟動(dòng)之后的n輪，所有的msg均在自己的第二階段中。 設(shè)pi是最早開(kāi)始執(zhí)行算法的結(jié)點(diǎn)中的某一個(gè)，其啟動(dòng)輪數(shù)為r。 Lemma 3.11 若pj距離pi為k(順時(shí)針)，則pj 接收的第一階段的msg不遲于第r+k輪。3.4.1 上界O(n)153.4.1 上界O(n)pf：對(duì)距離k歸納基礎(chǔ)：k=1，因?yàn)閜i的

13、左鄰居在第r+1輪接收到 pi的msg，故引理成立。假設(shè)：設(shè)距離pi為k-1 的結(jié)點(diǎn)接收第一階段 的msg不遲于r+k-1輪。步驟 若距離pi為k-1的結(jié)點(diǎn)pt(順時(shí)針)接收第一階段msg時(shí)已被喚醒，則pt已發(fā)送了第一階段msg給鄰居pj； 否則，pt至遲在第r+k輪轉(zhuǎn)發(fā)第一階段msg到pj。16 Lemma 3.12 第二類(lèi)msg總數(shù)至多為npf：由引理3.10可知，在每邊上至多只發(fā)送1個(gè)第一階段的msg，又因?yàn)榈降趓+n輪，每邊上已發(fā)送了一個(gè)第一階段msg，故到第r+n輪之后，已無(wú)第一階段的msg被發(fā)送。 Note：第一階段msg是喚醒msg，即若在pi(第一個(gè)啟動(dòng)結(jié)點(diǎn))發(fā)出喚醒msg繞環(huán)

14、一周回到pi之前已有某結(jié)點(diǎn)啟動(dòng)，則該啟動(dòng)結(jié)點(diǎn)的msg在未收到pi的msg之前已將自己的喚醒msg向前轉(zhuǎn)發(fā)。 3.4.1 上界O(n)17i) 第二類(lèi)msg經(jīng)歷的總輪數(shù)：由引理3.11知，最終的leader(不一定是首個(gè)啟動(dòng)者)的msg進(jìn)入自己的第二階段的時(shí)刻是：算法的第1個(gè)msg被發(fā)送之后至多n輪(前n輪)，故第二類(lèi)被發(fā)送的msg必是在首個(gè)啟動(dòng)結(jié)點(diǎn)的n輪之中。ii) 在這n輪中，第二類(lèi)msg數(shù)目。即第二類(lèi)msg是算法啟動(dòng)的前n輪中非喚醒msg的總數(shù)： 3.4.1 上界O(n)18 因?yàn)閙sg在其第二階段中，轉(zhuǎn)發(fā)前須延遲2i-1輪，所以若是第二類(lèi)msg，則它至多被發(fā)送n/2i次。 因?yàn)檩^小id被

15、轉(zhuǎn)發(fā)的次數(shù)較多，故可這樣構(gòu)造以使msg數(shù)目最大： 所有結(jié)點(diǎn)均參與選舉，標(biāo)識(shí)符均盡可能小：0, 1, , n-1（順時(shí)針排列）。顯然，因?yàn)閕d=0是leader，第二類(lèi)msg中不包括leader的msg，故第二類(lèi)msg總數(shù)至多是：3.4.1 上界O(n)19第三類(lèi)msg總數(shù) (即：leader進(jìn)入自己的第二階段之后，所有非喚醒msg) Lemma 3.13 在返回pi之后，沒(méi)有msg被轉(zhuǎn)發(fā) pf： 設(shè)pi是具有最小id的結(jié)點(diǎn)，當(dāng)一結(jié)點(diǎn)轉(zhuǎn)發(fā)之后，該結(jié)點(diǎn)將不再會(huì)轉(zhuǎn)發(fā)其它msg。 若返回pi，則所有結(jié)點(diǎn)均已轉(zhuǎn)發(fā)過(guò), 故再也沒(méi)有其它msg被轉(zhuǎn)發(fā)。3.4.1 上界O(n)20Lemma 3.14 第三類(lèi)m

16、sg總數(shù)至多為2npf：設(shè)pi是最終的leader，pj是某個(gè)參與的結(jié)點(diǎn)，由引理3.9知，idiidj，由引理3.13知，在pi收回自己的idi之后，環(huán)上不再有msg在傳輸。i) 第三類(lèi)msg經(jīng)歷的總輪數(shù)：因?yàn)樵诿總€(gè)結(jié)點(diǎn)上，至多延遲2idi輪(在喚醒結(jié)點(diǎn)上不延遲，故為至多)，所以返回pi至多經(jīng)過(guò)n 2idi輪。ii) 在這n 2idi輪中，第三類(lèi)msg數(shù)目：第三類(lèi)msg是在這n 2idi輪中發(fā)送的所有第二階段msg(非喚醒msg)。在這n 2idi輪中，一個(gè)非喚醒的msg被轉(zhuǎn)發(fā)的次數(shù)至多為：3.4.1 上界O(n)21 故有：第三類(lèi)msg總數(shù)至多為(包括leader)基于引理3.12的同樣理由

17、，當(dāng)所有結(jié)點(diǎn)參與選舉，及標(biāo)識(shí)符為0, 1, , n-1時(shí)有： 這里，idi0，n-1Th3.15 存在一個(gè)同步的leader選舉算法，其msg復(fù)雜度至多為4npf：由引理3.10，3.12及3.14立即可得。3.4.1 上界O(n)22(3) 時(shí)間復(fù)雜度由引理3.13知，當(dāng)leader接收到自己的id時(shí)，計(jì)算終止。這發(fā)生在第一個(gè)啟動(dòng)算法的節(jié)點(diǎn)之后的O(n 2i)輪，其中i是leader的標(biāo)識(shí)符。 / 當(dāng)i=0時(shí)，為O(n)輪/運(yùn)行時(shí)間與環(huán)大小及標(biāo)識(shí)符取值相關(guān)(4) 思考為何非喚醒msg要延遲2i -1輪？如何修改算法3.2來(lái)改善時(shí)間復(fù)雜性？3.4.1 上界O(n)23上節(jié)中的兩個(gè)算法在同步環(huán)上

18、最壞的msg復(fù)雜度為O(n)，但兩算法的缺陷為： 它們用一種非同尋常的方式使用id，即id決定msg延遲多長(zhǎng)； 在每個(gè)容許的執(zhí)行中，執(zhí)行輪數(shù)依賴(lài)于id，而id相對(duì)于n而言可能是巨大的。(更主要的)本節(jié)將說(shuō)明： 這些性質(zhì)對(duì)于基于消息的有效算法而言是固有的； 若一個(gè)算法中的標(biāo)識(shí)符僅用于比較，則它需要(nlgn)個(gè)msgs； 若一個(gè)算法中，限制輪數(shù)的上界，但獨(dú)立于id，則它的msg復(fù)雜度亦為(nlgn)。3.4.2 有限制算法的下界(nlgn)時(shí)間復(fù)雜度會(huì)表現(xiàn)很差24同步的下界不可能從異步的下界導(dǎo)出因?yàn)樯瞎?jié)中的算法表明：同步模型中的附加假定是必不可少的。同步的下界對(duì)于非均勻和均勻算法均成立，但異步的

19、下界只對(duì)均勻算法成立。但是從同步導(dǎo)出的異步結(jié)果是正確的，并且提供了一個(gè)非均勻算法的異步下界。3.4.2 有限制算法的下界(nlgn)異步通信模型中領(lǐng)導(dǎo)者選舉問(wèn)題所需的消息數(shù)下界為(nlgn)且算法不依賴(lài)于比較的或者限時(shí)的25基于比較的算法的概念和定義 為了得到下界，假定所有處理器在同一輪開(kāi)始執(zhí)行 一個(gè)環(huán)是由結(jié)點(diǎn)表按順時(shí)針?lè)较蛑付ǖ?，結(jié)點(diǎn)表開(kāi)始于最小標(biāo)識(shí)符。 在同步模型里，算法的容許執(zhí)行完全由初始配置定義，這是因?yàn)閙sg延遲及節(jié)點(diǎn)步驟的相對(duì)次序均無(wú)選擇的可能。 系統(tǒng)的初始配置完全由環(huán)決定，即由節(jié)點(diǎn)標(biāo)識(shí)符列表按上述規(guī)則來(lái)決定。當(dāng)算法的選擇可以從上下文判斷清楚時(shí)，則將由環(huán)R確定的容許執(zhí)行表示為exe

20、c(R).匹配：若環(huán)R1上的結(jié)點(diǎn)pi和R2上的pj在各自的環(huán)里具有相同的位置，則稱(chēng)pi和pj是匹配的，即：匹配的結(jié)點(diǎn)在各自環(huán)上距其最小id的結(jié)點(diǎn)的距離相同。3.4.2 有限制算法的下界(nlgn)26基于比較的算法 直觀(guān)上，若一個(gè)算法在兩個(gè)相對(duì)次序相同的環(huán)上具有相同的行為，則該算法是基于比較的，形式定義：1）序相同（order equivalent） 兩個(gè)環(huán)x0, x1, xn-1和y0, y1,yn-1是(次)序等價(jià)的，若對(duì)每個(gè)i和j，xixj, 當(dāng)且僅當(dāng)yi0)，則它在前n輪里就沒(méi)有任何msg存在。但同樣認(rèn)為前n輪對(duì)每個(gè)結(jié)點(diǎn)是有用的。 因此，若某一輪在任何次序等價(jià)的環(huán)上均無(wú)msg發(fā)送，則該

21、輪是無(wú)用的，而有用的輪被稱(chēng)為是主動(dòng)的(active)。3.4.2 有限制算法的下界(nlgn)31 Def 3.3 在一個(gè)環(huán)R上的一個(gè)執(zhí)行里，某輪r稱(chēng)為是active的，若該執(zhí)行的第r輪里，某一個(gè)結(jié)點(diǎn)發(fā)送一個(gè)msg。當(dāng)R是從上下文已知時(shí)，用rk表示第k個(gè)active輪。 Note： 一旦環(huán)R確定，整個(gè)容許執(zhí)行就確定(因?yàn)橄到y(tǒng)同步) 由于一個(gè)基于比較的算法在等價(jià)環(huán)上的行為相似，因此： 對(duì)于序等價(jià)的環(huán)R1和R2，一輪在exec(R1)里是主動(dòng)的當(dāng)且僅當(dāng)它在exec(R2)里也是主動(dòng)的。 因?yàn)橄⒅械男畔⒃趉個(gè)輪里只能在環(huán)上通過(guò)k個(gè)結(jié)點(diǎn)，所以一個(gè)結(jié)點(diǎn)在k輪之后的狀態(tài)只依賴(lài)于它的k-鄰居。 然而一個(gè)更

22、強(qiáng)的性質(zhì)是：一個(gè)結(jié)點(diǎn)在第k個(gè)主動(dòng)輪之后的狀態(tài)只依賴(lài)于它的k-鄰居。這實(shí)際上告訴我們：信息只有在主動(dòng)輪里才能獲得。這一點(diǎn)在下面的引理中給出形式證明。3.4.2 有限制算法的下界(nlgn)323.4.2 有限制算法的下界(nlgn) Note：該引理無(wú)需結(jié)點(diǎn)匹配(否則立即從定義3.2中可得結(jié)論)，但要求它們的鄰居是相同的(identical)。該引理要求假設(shè)兩個(gè)環(huán)是次序等價(jià)的，原因是要確?？紤]中的兩個(gè)執(zhí)行有相同的主動(dòng)輪集合，因此rk是良定義的。 Lemma3.16 設(shè)R1和R2是次序等價(jià)的兩個(gè)環(huán)，設(shè)Pi和Pj分別是R1和R2上具有相同k-鄰居的兩個(gè)節(jié)點(diǎn)，那么在exec(R1)的第1至第rk輪里P

23、i所經(jīng)歷的轉(zhuǎn)換序列和在exec(R2)的第1至第rk輪里Pj所經(jīng)歷的轉(zhuǎn)換序列相同。/該引理蘊(yùn)含：在k個(gè)主動(dòng)輪結(jié)束時(shí)，Pi和Pj的狀態(tài)相同 Pf：非形式地，該證明說(shuō)明在k個(gè)主動(dòng)輪之后，一個(gè)結(jié)點(diǎn)可能只知道距離自己至多為k的那些結(jié)點(diǎn)。形式證明對(duì)k進(jìn)行歸納。333.4.2 有限制算法的下界(nlgn)歸納基礎(chǔ)：k=0，因?yàn)閮蓚€(gè)具有相同0-鄰居的結(jié)點(diǎn)有同樣的id，故它們的狀態(tài)相同；歸納假設(shè)：假定每?jī)蓚€(gè)具有相同(k-1)-鄰居的結(jié)點(diǎn)在(k-1)個(gè)主動(dòng)輪之后有相同的狀態(tài)；歸納步驟：因?yàn)镻i和Pj有相同的k-鄰居，故它們亦有相同的(k-1)-鄰居。因此由歸納假設(shè)知，Pi和Pj在第(k-1)個(gè)主動(dòng)輪之后處在相同

24、的狀態(tài)。又因Pi和Pj各自的鄰居有同樣的(k-1)-鄰居，故由歸納假設(shè)知，它們各自的鄰居在第(k-1)個(gè)主動(dòng)輪之后也處在相同的狀態(tài)。兩個(gè)主動(dòng)輪之間可能有非主動(dòng)輪。因?yàn)樵诘?k-1)主動(dòng)輪和第k主動(dòng)輪之間的輪(若有的話(huà))里，沒(méi)有結(jié)點(diǎn)接收任何msg，故Pi和Pj及各自的鄰居均處在相同的狀態(tài)(Note: Pi在非主動(dòng)輪里可能改變它的狀態(tài)，但因?yàn)镻j有同樣的轉(zhuǎn)換函數(shù)，故它有同樣的狀態(tài)轉(zhuǎn)換)。343.4.2 有限制算法的下界(nlgn)在第k個(gè)主動(dòng)輪里： i)若Pi和Pj均不接收msg，則它們?cè)谠撦喗Y(jié)束時(shí)有相同的狀態(tài)； ii)因?yàn)镻i 和Pj的鄰居狀態(tài)相同，若Pi接收右(左)鄰的一個(gè)msg，則Pj也接收

25、右(左)鄰?fù)瑯拥膍sg。因此，在第k個(gè)主動(dòng)輪結(jié)束之后，Pi和Pj均處于相同的狀態(tài)。下一引理將上述論斷從具有相同k-鄰居的結(jié)點(diǎn)擴(kuò)展至具有次序等價(jià)的k-鄰居的結(jié)點(diǎn)。這依賴(lài)于事實(shí)：A是基于比較的。更進(jìn)一步要求環(huán)R是有空隙的，即環(huán)R中，每?jī)蓚€(gè)id之間均有n個(gè)未使用的標(biāo)識(shí)符。形式地，在大小為n的環(huán)上，若對(duì)于每一個(gè)標(biāo)識(shí)符x，標(biāo)識(shí)符x-1到x-n均不在環(huán)上，則該環(huán)稱(chēng)為有空隙的。353.4.2 有限制算法的下界(nlgn)引理3.16定義在兩環(huán)上(Pi和Pj的k-鄰居相同)，引理3.17是定義在同一個(gè)環(huán)上(Pi和Pj的k-鄰居序等價(jià))Lemma3.17 設(shè)R是有空隙環(huán)，Pi和Pj是R上具有序等價(jià)k-鄰居的兩個(gè)

26、結(jié)點(diǎn)。則Pi和Pj在exec(R)的第1到第rk輪里有相似的行為。Pf：我們構(gòu)造滿(mǎn)足下述條件的另一個(gè)環(huán)R：R中的Pj和R中Pi的有相同的k-鄰居；R中的標(biāo)識(shí)符唯一R和R序等價(jià)，R中的Pj匹配于R中的Pj。因?yàn)镽是有空隙環(huán)，故我們能夠構(gòu)造R。例如，對(duì)于k=1和n=8有：363.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距離為1373.4.2 有限制算法的下界(nlgn)R上的P

27、i和R上的Pj的前k個(gè)主動(dòng)輪行為相似 因?yàn)镽上Pi和R上Pj的k-鄰居相同，由引理3.16知，Pi和Pj在各自的exec(R)和exec(R)的1到rk輪里所經(jīng)歷的轉(zhuǎn)換序列相同，所以Pi和Pj在各自的執(zhí)行exec(R)和exec(R)的1至rk輪里的行為相似。 Pi(R) Pj(R)(2)R上的Pj和R上的Pj的前k個(gè)主動(dòng)輪行為相似 因?yàn)樗惴ㄊ腔诒容^的，由定義3.2在兩個(gè)序等價(jià)的環(huán)中，每對(duì)匹配的結(jié)點(diǎn)在各自執(zhí)行中有相似的行為。而R里的Pj和R里的Pj是匹配的，故R里的Pj在exec(R)的1至rk輪里的行為相似于R里的Pj在exec(R)的第1至rk輪里的行為。 Pj(R) Pj(R)(3)R

28、上兩節(jié)點(diǎn)的k-鄰居序等價(jià)，則其行為在前k個(gè)主動(dòng)輪里相似 由(1)和(2)得：R里的Pi和Pj在exec(R)的1至rk輪里的行為相似。Pi(R) Pj(R) 383.4.2 有限制算法的下界(nlgn)Th3.18 對(duì)于每個(gè)n8(n是2的冪)，存在一個(gè)大小為n的環(huán)Sn，使得對(duì)每個(gè)基于比較的同步leader選舉算法A，在Sn上A的容許執(zhí)行里發(fā)送msg的數(shù)目為(nlgn)Pf：固定算法A。證明分2步： (1) 構(gòu)造1個(gè)高度對(duì)稱(chēng)(很多結(jié)點(diǎn)有很多序等價(jià)的鄰居)的環(huán)Sn； (2) Sn上發(fā)送的msg總數(shù)。 （1）構(gòu)造Sn（分2步構(gòu)造）定義大小為n的環(huán) ： 對(duì)i0，n-1，設(shè)Pi的id為rev(i)，這里rev(i)是i的二進(jìn)制表示的逆序列。 393.4.2 有限制算法的下界(nlgn)例如，當(dāng)n=8時(shí)有： 若將環(huán) 劃分為長(zhǎng)度為j(j是2的方冪)的連續(xù)片斷，則所有這些片斷是序等價(jià)的(Ex3.9)。 片斷數(shù)：n / j.例如，4,2,6,1和5,3,7,0序等價(jià) 2,6,1,5和