分布式算法課件概要

第二部分分布式算法

第四次課中國科學(xué)技術(shù)大學(xué)計算機(jī)系國家高性能計算中心（合肥）1第二部分分布式算法

第四次課中國科學(xué)技術(shù)大學(xué)計算機(jī)系1§2.5不指定根時構(gòu)造DFS生成樹

算法2.2和2.3構(gòu)造連通網(wǎng)絡(luò)的生成樹時，必需存在一個特殊的結(jié)點(diǎn)作為啟動者(Leader)。當(dāng)這樣的特殊結(jié)點(diǎn)不存在時，如何構(gòu)造網(wǎng)絡(luò)的一棵生成樹？但本節(jié)算法須假定：各結(jié)點(diǎn)的標(biāo)識符唯一，不妨設(shè)是自然數(shù)，§3.2仍需此假定?；舅枷朊總€結(jié)點(diǎn)均可自發(fā)喚醒，試圖構(gòu)造一棵以自己為根的DFS生成樹。若兩棵DFS樹試圖鏈接同一節(jié)點(diǎn)(未必同時)時，該節(jié)點(diǎn)將加入根的id較大的DFS樹。為了實現(xiàn)上述思想，須做：每個結(jié)點(diǎn)設(shè)置一個leader變量，其初值為0，當(dāng)Pi喚醒自己時，leaderi=idi；不指定根構(gòu)造DFS生成樹，和后面的領(lǐng)導(dǎo)者選舉問題一樣，都是破對稱問題。2§2.5不指定根時構(gòu)造DFS生成樹 算法2.2§2.5不指定根時構(gòu)造DFS生成樹當(dāng)一結(jié)點(diǎn)自發(fā)喚醒時，它將自己的id(leader)發(fā)送給某一鄰居；當(dāng)一結(jié)點(diǎn)Pi收到來自鄰居Pj的標(biāo)識符y時，Pi比較y和leaderi：

①若y>leaderi，則y可能是具有最大標(biāo)識符結(jié)點(diǎn)的DFS子樹的標(biāo)記。因此，將leaderi置為y，并令Pj是Pi的雙親。從Pi開始繼續(xù)生成標(biāo)記為y的DFS樹。Note：要修改原Pi所在的DFS子樹中所有結(jié)點(diǎn)的leader。3§2.5不指定根時構(gòu)造DFS生成樹當(dāng)一結(jié)點(diǎn)自發(fā)喚醒時，它將§2.5不指定根時構(gòu)造DFS生成樹若y<leaderi，則標(biāo)記為y的DFS樹中最大id(y)小于目前所看到的最大標(biāo)識符。此時無須發(fā)送msg，停止構(gòu)造標(biāo)記為y的DFS。等待最終某個更大的id的leader消息到達(dá)標(biāo)記為y的樹中結(jié)點(diǎn)時，再將該節(jié)點(diǎn)連接到樹中。(至少標(biāo)記為leaderi的msg會到達(dá)標(biāo)記為y的樹)若y=leaderi，則Pi已屬于標(biāo)記y的DFS樹中。

4§2.5不指定根時構(gòu)造DFS生成樹若y<leaderi，則§2.5不指定根時構(gòu)造DFS生成樹算法

Alg2.4構(gòu)造生成樹，不指定根CodeforProcessorPi0≤i≤n-1 Varparent: initnil; leader: init0; children: intφ; unexplored: initallneighborsofPi; 1:uponreceivingnomsg:

//wakeupspontaneously 2:ifparent=nilthen{ //若非空，則Pi在某子樹上，則Pi失去競選機(jī)會 3:leader:=id;parent:=i;//試圖以自己為根構(gòu)造樹 4:Pj∈unexplored; 5:將Pj從unexplored中刪去； 6：send<leader>topj; }5§2.5不指定根時構(gòu)造DFS生成樹算法5§2.5不指定根時構(gòu)造DFS生成樹想像：有m個人競選領(lǐng)袖，id是他自身的素質(zhì)分，不想競爭人的id不參與比較。競爭規(guī)則：將自己的id(如講演片)傳遞給一個熟悉的人，由他再傳給另一人(一次只能送一人。)7:uponreceiving<new-id>fromneighborPj:

8:ifleader<new-idthen{//將Pi所在樹合并到Pj所在樹中9:leader:=new-id;parent:=j;//令Pi的雙親為Pj，可能是修改，而非對nil賦值//并不一定能停止較差的競選者傳播msg10:unexplored:=alltheneighborsofPiexceptPj;

//重置未訪問的鄰居集11:ifunexplored≠φthen{//因為new-id大，使原Pi所在DFS樹修改各自id12：Pk

∈unexplored;13:將Pk從unexplored中刪去；6§2.5不指定根時構(gòu)造DFS生成樹想像：有m個人競選領(lǐng)袖，§2.5不指定根時構(gòu)造DFS生成樹14:send<leader>toPK;15:}elsesend<parent>toparent;//unexplored=φ}else//leader≥new-id

16:ifleader=new-idthensend<already>toPj; //表示自己已經(jīng)傳出過此錄像帶，無需重傳。已在同一樹中 //若leader>new-id，則new-id所在DFS停止構(gòu)造 //以前收到的競選者優(yōu)于new-id，不傳送，使之停止傳播。17:uponreceiving<parent>or<already>fromneighborPj:18:ifreceived<parent>thenaddjtochildren;19:ifunexplored=φthen{//無尚未訪問的鄰居20:ifparent≠ithensend<parent>toparent//返回21:elseterminatesasrootoftheDFStree;//根終止22:}else{//有尚未訪問的鄰居7§2.5不指定根時構(gòu)造DFS生成樹14:§2.5不指定根時構(gòu)造DFS生成樹23:Pk∈unexplored;24:將Pk從unexplored中刪去；25:send<leader>toPk;}分析：只有生成樹的根顯式地終止，其它結(jié)點(diǎn)沒有終止，始終在等待msg。但可修改此算法，使用Alg2.1從根結(jié)點(diǎn)發(fā)送終止msg正確性 該算法比前面的算法更復(fù)雜，這里只給出粗略的證明。

設(shè)Pm是所有自發(fā)喚醒結(jié)點(diǎn)中標(biāo)識符最大者，其標(biāo)識符為idm。消息idm總是被傳播，而一旦一個結(jié)點(diǎn)收到idm，則該節(jié)點(diǎn)(Pm除外)上所有msgs被忽略。因為消息idm的處理和Alg2.3求DFS樹一致，因此產(chǎn)生的parent和children變量的設(shè)置是正確的。因此有：8§2.5不指定根時構(gòu)造DFS生成樹23:§2.5不指定根時構(gòu)造DFS生成樹Lemma2.12設(shè)Pm是所有自發(fā)喚醒結(jié)點(diǎn)中具有最大標(biāo)識符的結(jié)點(diǎn)。在異步模型的每次容許執(zhí)行里，算法2.4構(gòu)造根為Pm的一棵DFS樹。Note：因為在容許執(zhí)行中，網(wǎng)絡(luò)里的所有自發(fā)喚醒結(jié)點(diǎn)中最大標(biāo)識符結(jié)點(diǎn)最終會自發(fā)啟動，故建立的DFS樹的根是Pm 可通過廣播算法從Pm發(fā)出終止msg，即使不廣播，所有非Pm結(jié)點(diǎn)最終也會因為收到Pm的標(biāo)識符而停止。因此，不可能構(gòu)造一棵根不是Pm的生成樹。Lemma2.13在異步模型的每個容許執(zhí)行里，只有一個處理器終止作為一生成樹的根。9§2.5不指定根時構(gòu)造DFS生成樹Lemma2.12設(shè)P§2.5不指定根時構(gòu)造DFS生成樹復(fù)雜性定理：對于一個具有m條邊和n個節(jié)點(diǎn)的網(wǎng)絡(luò)，自發(fā)啟動的節(jié)點(diǎn)共有p個，其中ID值最大者的啟動時間為t，則算法的消息復(fù)雜度為O(pn2)，時間復(fù)雜度為O(t+m)。

消息復(fù)雜性：簡單地分析，最壞情況下，每個處理器均試圖以自己為根構(gòu)造一棵DFS樹。因此，Alg2.4的msg復(fù)雜性至多是Alg2.3的n倍：O(m*n)時間復(fù)雜性：類似于Alg2.3的msg復(fù)雜性O(shè)(m)。10§2.5不指定根時構(gòu)造DFS生成樹復(fù)雜性10§2.5不指定根時構(gòu)造DFS生成樹Ex.2.1分析在同步和異步模型下，convergecast算法的時間復(fù)雜性。2.2證明在引理2.6中，一個處理器在圖G中是從Pr可達(dá)的，當(dāng)且僅當(dāng)它的parent變量曾被賦過值2.3證明Alg2.3構(gòu)造一棵以Pr為根的DFS樹。2.4證明Alg2.3的時間復(fù)雜性為O(m)。2.5修改Alg2.3獲得一新算法，使構(gòu)造DFS樹的時間復(fù)雜性為O(n)。補(bǔ)充§2.6小結(jié)11§2.5不指定根時構(gòu)造DFS生成樹Ex.11§補(bǔ)充構(gòu)造最小生成樹考慮每個信道都有權(quán)重，代表了信道的通信成本，這樣最小生成樹能夠使得執(zhí)行廣播算法總開銷最小。假設(shè)每個信道的權(quán)重都已存儲在其兩端的節(jié)點(diǎn)的局部內(nèi)存中。基本思想：每個節(jié)點(diǎn)都有一個所屬樹的變量編號，用來判斷兩個節(jié)點(diǎn)是否屬于一棵樹。剛開始時，每個節(jié)點(diǎn)獨(dú)立成一棵樹，其ID值為樹的編號，每棵樹并發(fā)的搜索自己權(quán)值最小的出邊，并把這些邊加入到生成森林中，同時幾棵樹也就合并為一棵樹，取其中編號較大的一個為合并之后的樹的編號，更新樹中各節(jié)點(diǎn)的樹編號變量。直至所有的樹都被合并為一棵樹，此即為最小生成樹。12§補(bǔ)充構(gòu)造最小生成樹考慮每個信道都有權(quán)重，代表了§補(bǔ)充構(gòu)造最小生成樹可能出現(xiàn)的4個問題：產(chǎn)生環(huán)

可以證明，如果邊的權(quán)值不相等，那么圖G只有唯一的最小生成樹。利用三元組，將邊表述為{1,i,j},{1,j,k},{1,i,k}當(dāng)權(quán)相同時，按照i,j,k的字典序來排序假設(shè)i<j<k,則有{1,i,j}<{1,i,k}<{1,j,k}這樣就可以避免出現(xiàn)環(huán)PiPjPk111PiPjPk1113§補(bǔ)充構(gòu)造最小生成樹可能出現(xiàn)的4個問題：PiPjPk111§補(bǔ)充構(gòu)造最小生成樹可能出現(xiàn)的4個問題：不平衡

由于異步系統(tǒng)的消息延遲，可能會出現(xiàn)不平衡構(gòu)造樹，從而導(dǎo)致更多的消息。極端的例子：每次都是一個節(jié)點(diǎn)數(shù)目很多的樹，去合并一個單節(jié)點(diǎn)的樹，這樣對于節(jié)點(diǎn)數(shù)目大的樹來說，每次查找權(quán)最小的出邊花去的代價太大。解決辦法：給每棵樹設(shè)置一個level層變量，剛開始時，單節(jié)點(diǎn)樹的level為0，如果一棵樹的權(quán)值最小出邊所連的另一棵樹的level變量大于或等于自己的level變量，則兩棵樹通過這條邊合并，否則等待。所合并的樹的level取決于兩棵樹中l(wèi)evel較大者，若兩棵樹level相同為L，則新合并的樹的level=L+1。(level的含義：好比游戲中的練級)14§補(bǔ)充構(gòu)造最小生成樹可能出現(xiàn)的4個問題：14§補(bǔ)充構(gòu)造最小生成樹可能出現(xiàn)的4個問題：錯誤判斷出邊

異步系統(tǒng)中，可能出現(xiàn)在判斷一條邊是否是出邊時，邊連接的兩點(diǎn)已經(jīng)處在一棵樹當(dāng)中了，但由于消息延遲導(dǎo)致樹編號的更新消息還未傳到，因而導(dǎo)致因為兩節(jié)點(diǎn)的樹編號不同而產(chǎn)生的錯誤。解決方法：

在合并之前，樹中節(jié)點(diǎn)按邊的權(quán)值由小到大的順序開始探測此邊是否是出邊，當(dāng)確認(rèn)某條邊是出邊之后便停止探測其他邊，并將結(jié)果斂播給根節(jié)點(diǎn)，由根節(jié)點(diǎn)確定通過哪一條邊進(jìn)行合并。當(dāng)兩棵樹合并時，合并后的樹的編號以及根節(jié)點(diǎn)取level值較大的那棵樹的根和樹編號。若level值相同，取樹編號較大的樹的根和樹編號。然后由根執(zhí)行廣播操作，更新所有樹編號和level值，并通知尋找權(quán)值最小的出邊。

（確定Pi和Pj是否屬于一棵樹）①如果Pi和Pj編號相同，則肯定屬于一棵樹；②如果編號不同，但Pj的level和Pi一樣大，則肯定不屬于一棵樹，因為每棵樹在一層中不可能有兩個樹編號，且當(dāng)Pi在尋找其權(quán)值最小的出邊的時候，其樹編號是最新的；③如果Pj的樹編號與Pi不同且Pj的層數(shù)嚴(yán)格小于Pi，那么節(jié)點(diǎn)Pj就延遲回答Pi直到他更新到其level值上升到至少和Pi一樣大。(可以證明，這個新增的延遲將不會構(gòu)成節(jié)點(diǎn)間的死鎖)15§補(bǔ)充構(gòu)造最小生成樹可能出現(xiàn)的4個問題：15§補(bǔ)充構(gòu)造最小生成樹可能出現(xiàn)的4個問題：存在干擾不同層的鄰接樹同時尋找權(quán)值最小的出邊有可能發(fā)生相互干擾。具體來說，當(dāng)層低的樹T合并到層高的樹T’，而T’正在確定其權(quán)值最小出邊時可能會發(fā)生此情況。16§補(bǔ)充構(gòu)造最小生成樹可能出現(xiàn)的4個問題：16§補(bǔ)充構(gòu)造最小生成樹算法框架：CodeforEveryTreeTBeginWhile(系統(tǒng)中的子樹個數(shù)大于1)do(1)根節(jié)點(diǎn)廣播ID(T)和level(T)，命令各節(jié)點(diǎn)尋找權(quán)值最小的邊；(2)按權(quán)值由小到大順序?qū)ふ覚?quán)值最小的出邊，找到之后斂播給根節(jié)點(diǎn)；(3)根節(jié)點(diǎn)收到所有節(jié)點(diǎn)的權(quán)值最小出邊后，確定整棵樹的最小出邊e，邊e連接樹T’。/*level(T)≤level(T’)*/(4)T’’=T∪T’∪e(5)iflevel(T’)>level(T)then(5.1)ID(T’’)←ID(T’)(5.2)level(T’’)←level(T’)else//level(T’)=level(T)(5.3)ID(T’’)←max{ID(T),ID(T’)}(5.4)level(T’’)←level(T’’)+1endifendwhileend17§補(bǔ)充構(gòu)造最小生成樹算法框架：17§補(bǔ)充構(gòu)造最小生成樹消息復(fù)雜度：每個level為k的樹中的節(jié)點(diǎn)數(shù)至少為2k，level最大為log(n)(n為節(jié)點(diǎn)數(shù))。因為每個節(jié)點(diǎn)都從邊的權(quán)值從小到大開始探測此邊是否是出邊，當(dāng)確定某邊是出邊后就停止探測并斂播給根節(jié)點(diǎn)，直到根確認(rèn)這條邊是這棵樹的最小邊，并進(jìn)行合并操作，并更新level值，然后繼續(xù)探測。消息分兩類：①每個節(jié)點(diǎn)探測自己的一條邊是否是出邊而得到否認(rèn)消息，這些消息數(shù)目為O(m)；②每一層中在樹T中各種消息的傳遞，其消息數(shù)目為O(|T|)，|T|表示樹的節(jié)點(diǎn)數(shù)，此總數(shù)目為故消息總數(shù)為O(m+nlogn)18§補(bǔ)充構(gòu)造最小生成樹消息復(fù)雜度：18§補(bǔ)充構(gòu)造最小生成樹時間復(fù)雜度：系統(tǒng)中所有節(jié)點(diǎn)，其所在的樹的level值都變成k時所需的時間為O(kn)，又因為k的最大值為log(n)，所以總時間為O(nlogn)。19§補(bǔ)充構(gòu)造最小生成樹時間復(fù)雜度：19§2.6小結(jié)Introductiontodistributedalg分類：單源alg：一個啟動者。又稱centralizedalg。多源alg：任意進(jìn)程(結(jié)點(diǎn))子集均可是啟動者，又稱decentralizedalg啟動者(initiator)：自發(fā)地執(zhí)行局部算法，即由一內(nèi)部事件激發(fā)其執(zhí)行非啟動者：由接收一個msg(外部事件)觸發(fā)其執(zhí)行局部進(jìn)程。復(fù)雜性：Msg復(fù)雜性：msg總數(shù)目Bit復(fù)雜性：發(fā)送msg中bit的總數(shù)目，當(dāng)msg在發(fā)送過程中其長度隨時間增長時20§2.6小結(jié)Introductiontodistrib§2.6小結(jié)時間復(fù)雜性一個分布式算法的時間復(fù)雜性是滿足下述兩個假定的一個計算所耗費(fèi)的最大時間 T1：一個進(jìn)程在零時間內(nèi)可計算任何有限數(shù)目的事件 T2：一個msg的發(fā)送和接受之間的時間至多為1個時間單位

缺點(diǎn):針對一算法的所有計算，其結(jié)果可能是極不可能發(fā)生的計算。一個分布式算法的one-time復(fù)雜性是滿足下述假定的一個計算的最大時間 O1：同T1 O2：發(fā)送和接收一個msg之間的時間恰好是1個單位時間

缺點(diǎn)：某些計算可能被忽略，而其中可能有極其耗時的計算21§2.6小結(jié)時間復(fù)雜性21§2.6小結(jié) 表面上，1-time復(fù)雜性至少等于時間復(fù)雜性，因為T2假定下的最壞時間不會高于O2假定下的時間。但事實并非如此，而往往O1和O2假定之下的1-time復(fù)雜性是前一種時間復(fù)雜性的一個下界。例如：在echo算法里1-time復(fù)雜性是O(D)，時間復(fù)雜性是?(N)，即使直徑為1的網(wǎng)絡(luò)。

兩種復(fù)雜性的折中：α-復(fù)雜性 假定每個msg延遲介于α-1之間(α≤1常數(shù)) 對echo算法α復(fù)雜性為O(min(N,D/α))概率分析：msg延遲服從某種概率分布，由此可獲得精確的時間復(fù)雜性度量22§2.6小結(jié) 表面上，1-time復(fù)雜性至少等于時間復(fù)雜§2.6小結(jié)基于msgchains的分析 任何計算中最長消息鏈的長度。鏈上msgs：m1,m2,…mk序列中，mi因果關(guān)系領(lǐng)先于mi+1。先驗知識：鄰居的id，全局id等。鏈路FIFO假定等23§2.6小結(jié)基于msgchains的分析23下次繼續(xù)！24下次繼續(xù)！24第二部分分布式算法

第四次課中國科學(xué)技術(shù)大學(xué)計算機(jī)系國家高性能計算中心（合肥）25第二部分分布式算法

第四次課中國科學(xué)技術(shù)大學(xué)計算機(jī)系1§2.5不指定根時構(gòu)造DFS生成樹

算法2.2和2.3構(gòu)造連通網(wǎng)絡(luò)的生成樹時，必需存在一個特殊的結(jié)點(diǎn)作為啟動者(Leader)。當(dāng)這樣的特殊結(jié)點(diǎn)不存在時，如何構(gòu)造網(wǎng)絡(luò)的一棵生成樹？但本節(jié)算法須假定：各結(jié)點(diǎn)的標(biāo)識符唯一，不妨設(shè)是自然數(shù)，§3.2仍需此假定?；舅枷朊總€結(jié)點(diǎn)均可自發(fā)喚醒，試圖構(gòu)造一棵以自己為根的DFS生成樹。若兩棵DFS樹試圖鏈接同一節(jié)點(diǎn)(未必同時)時，該節(jié)點(diǎn)將加入根的id較大的DFS樹。為了實現(xiàn)上述思想，須做：每個結(jié)點(diǎn)設(shè)置一個leader變量，其初值為0，當(dāng)Pi喚醒自己時，leaderi=idi；不指定根構(gòu)造DFS生成樹，和后面的領(lǐng)導(dǎo)者選舉問題一樣，都是破對稱問題。26§2.5不指定根時構(gòu)造DFS生成樹 算法2.2§2.5不指定根時構(gòu)造DFS生成樹當(dāng)一結(jié)點(diǎn)自發(fā)喚醒時，它將自己的id(leader)發(fā)送給某一鄰居；當(dāng)一結(jié)點(diǎn)Pi收到來自鄰居Pj的標(biāo)識符y時，Pi比較y和leaderi：

①若y>leaderi，則y可能是具有最大標(biāo)識符結(jié)點(diǎn)的DFS子樹的標(biāo)記。因此，將leaderi置為y，并令Pj是Pi的雙親。從Pi開始繼續(xù)生成標(biāo)記為y的DFS樹。Note：要修改原Pi所在的DFS子樹中所有結(jié)點(diǎn)的leader。27§2.5不指定根時構(gòu)造DFS生成樹當(dāng)一結(jié)點(diǎn)自發(fā)喚醒時，它將§2.5不指定根時構(gòu)造DFS生成樹若y<leaderi，則標(biāo)記為y的DFS樹中最大id(y)小于目前所看到的最大標(biāo)識符。此時無須發(fā)送msg，停止構(gòu)造標(biāo)記為y的DFS。等待最終某個更大的id的leader消息到達(dá)標(biāo)記為y的樹中結(jié)點(diǎn)時，再將該節(jié)點(diǎn)連接到樹中。(至少標(biāo)記為leaderi的msg會到達(dá)標(biāo)記為y的樹)若y=leaderi，則Pi已屬于標(biāo)記y的DFS樹中。

28§2.5不指定根時構(gòu)造DFS生成樹若y<leaderi，則§2.5不指定根時構(gòu)造DFS生成樹算法

Alg2.4構(gòu)造生成樹，不指定根CodeforProcessorPi0≤i≤n-1 Varparent: initnil; leader: init0; children: intφ; unexplored: initallneighborsofPi; 1:uponreceivingnomsg:

//wakeupspontaneously 2:ifparent=nilthen{ //若非空，則Pi在某子樹上，則Pi失去競選機(jī)會 3:leader:=id;parent:=i;//試圖以自己為根構(gòu)造樹 4:Pj∈unexplored; 5:將Pj從unexplored中刪去； 6：send<leader>topj; }29§2.5不指定根時構(gòu)造DFS生成樹算法5§2.5不指定根時構(gòu)造DFS生成樹想像：有m個人競選領(lǐng)袖，id是他自身的素質(zhì)分，不想競爭人的id不參與比較。競爭規(guī)則：將自己的id(如講演片)傳遞給一個熟悉的人，由他再傳給另一人(一次只能送一人。)7:uponreceiving<new-id>fromneighborPj:

8:ifleader<new-idthen{//將Pi所在樹合并到Pj所在樹中9:leader:=new-id;parent:=j;//令Pi的雙親為Pj，可能是修改，而非對nil賦值//并不一定能停止較差的競選者傳播msg10:unexplored:=alltheneighborsofPiexceptPj;

//重置未訪問的鄰居集11:ifunexplored≠φthen{//因為new-id大，使原Pi所在DFS樹修改各自id12：Pk

∈unexplored;13:將Pk從unexplored中刪去；30§2.5不指定根時構(gòu)造DFS生成樹想像：有m個人競選領(lǐng)袖，§2.5不指定根時構(gòu)造DFS生成樹14:send<leader>toPK;15:}elsesend<parent>toparent;//unexplored=φ}else//leader≥new-id

16:ifleader=new-idthensend<already>toPj; //表示自己已經(jīng)傳出過此錄像帶，無需重傳。已在同一樹中 //若leader>new-id，則new-id所在DFS停止構(gòu)造 //以前收到的競選者優(yōu)于new-id，不傳送，使之停止傳播。17:uponreceiving<parent>or<already>fromneighborPj:18:ifreceived<parent>thenaddjtochildren;19:ifunexplored=φthen{//無尚未訪問的鄰居20:ifparent≠ithensend<parent>toparent//返回21:elseterminatesasrootoftheDFStree;//根終止22:}else{//有尚未訪問的鄰居31§2.5不指定根時構(gòu)造DFS生成樹14:§2.5不指定根時構(gòu)造DFS生成樹23:Pk∈unexplored;24:將Pk從unexplored中刪去；25:send<leader>toPk;}分析：只有生成樹的根顯式地終止，其它結(jié)點(diǎn)沒有終止，始終在等待msg。但可修改此算法，使用Alg2.1從根結(jié)點(diǎn)發(fā)送終止msg正確性 該算法比前面的算法更復(fù)雜，這里只給出粗略的證明。

設(shè)Pm是所有自發(fā)喚醒結(jié)點(diǎn)中標(biāo)識符最大者，其標(biāo)識符為idm。消息idm總是被傳播，而一旦一個結(jié)點(diǎn)收到idm，則該節(jié)點(diǎn)(Pm除外)上所有msgs被忽略。因為消息idm的處理和Alg2.3求DFS樹一致，因此產(chǎn)生的parent和children變量的設(shè)置是正確的。因此有：32§2.5不指定根時構(gòu)造DFS生成樹23:§2.5不指定根時構(gòu)造DFS生成樹Lemma2.12設(shè)Pm是所有自發(fā)喚醒結(jié)點(diǎn)中具有最大標(biāo)識符的結(jié)點(diǎn)。在異步模型的每次容許執(zhí)行里，算法2.4構(gòu)造根為Pm的一棵DFS樹。Note：因為在容許執(zhí)行中，網(wǎng)絡(luò)里的所有自發(fā)喚醒結(jié)點(diǎn)中最大標(biāo)識符結(jié)點(diǎn)最終會自發(fā)啟動，故建立的DFS樹的根是Pm 可通過廣播算法從Pm發(fā)出終止msg，即使不廣播，所有非Pm結(jié)點(diǎn)最終也會因為收到Pm的標(biāo)識符而停止。因此，不可能構(gòu)造一棵根不是Pm的生成樹。Lemma2.13在異步模型的每個容許執(zhí)行里，只有一個處理器終止作為一生成樹的根。33§2.5不指定根時構(gòu)造DFS生成樹Lemma2.12設(shè)P§2.5不指定根時構(gòu)造DFS生成樹復(fù)雜性定理：對于一個具有m條邊和n個節(jié)點(diǎn)的網(wǎng)絡(luò)，自發(fā)啟動的節(jié)點(diǎn)共有p個，其中ID值最大者的啟動時間為t，則算法的消息復(fù)雜度為O(pn2)，時間復(fù)雜度為O(t+m)。

消息復(fù)雜性：簡單地分析，最壞情況下，每個處理器均試圖以自己為根構(gòu)造一棵DFS樹。因此，Alg2.4的msg復(fù)雜性至多是Alg2.3的n倍：O(m*n)時間復(fù)雜性：類似于Alg2.3的msg復(fù)雜性O(shè)(m)。34§2.5不指定根時構(gòu)造DFS生成樹復(fù)雜性10§2.5不指定根時構(gòu)造DFS生成樹Ex.2.1分析在同步和異步模型下，convergecast算法的時間復(fù)雜性。2.2證明在引理2.6中，一個處理器在圖G中是從Pr可達(dá)的，當(dāng)且僅當(dāng)它的parent變量曾被賦過值2.3證明Alg2.3構(gòu)造一棵以Pr為根的DFS樹。2.4證明Alg2.3的時間復(fù)雜性為O(m)。2.5修改Alg2.3獲得一新算法，使構(gòu)造DFS樹的時間復(fù)雜性為O(n)。補(bǔ)充§2.6小結(jié)35§2.5不指定根時構(gòu)造DFS生成樹Ex.11§補(bǔ)充構(gòu)造最小生成樹考慮每個信道都有權(quán)重，代表了信道的通信成本，這樣最小生成樹能夠使得執(zhí)行廣播算法總開銷最小。假設(shè)每個信道的權(quán)重都已存儲在其兩端的節(jié)點(diǎn)的局部內(nèi)存中。基本思想：每個節(jié)點(diǎn)都有一個所屬樹的變量編號，用來判斷兩個節(jié)點(diǎn)是否屬于一棵樹。剛開始時，每個節(jié)點(diǎn)獨(dú)立成一棵樹，其ID值為樹的編號，每棵樹并發(fā)的搜索自己權(quán)值最小的出邊，并把這些邊加入到生成森林中，同時幾棵樹也就合并為一棵樹，取其中編號較大的一個為合并之后的樹的編號，更新樹中各節(jié)點(diǎn)的樹編號變量。直至所有的樹都被合并為一棵樹，此即為最小生成樹。36§補(bǔ)充構(gòu)造最小生成樹考慮每個信道都有權(quán)重，代表了§補(bǔ)充構(gòu)造最小生成樹可能出現(xiàn)的4個問題：產(chǎn)生環(huán)

可以證明，如果邊的權(quán)值不相等，那么圖G只有唯一的最小生成樹。利用三元組，將邊表述為{1,i,j},{1,j,k},{1,i,k}當(dāng)權(quán)相同時，按照i,j,k的字典序來排序假設(shè)i<j<k,則有{1,i,j}<{1,i,k}<{1,j,k}這樣就可以避免出現(xiàn)環(huán)PiPjPk111PiPjPk1137§補(bǔ)充構(gòu)造最小生成樹可能出現(xiàn)的4個問題：PiPjPk111§補(bǔ)充構(gòu)造最小生成樹可能出現(xiàn)的4個問題：不平衡

由于異步系統(tǒng)的消息延遲，可能會出現(xiàn)不平衡構(gòu)造樹，從而導(dǎo)致更多的消息。極端的例子：每次都是一個節(jié)點(diǎn)數(shù)目很多的樹，去合并一個單節(jié)點(diǎn)的樹，這樣對于節(jié)點(diǎn)數(shù)目大的樹來說，每次查找權(quán)最小的出邊花去的代價太大。解決辦法：給每棵樹設(shè)置一個level層變量，剛開始時，單節(jié)點(diǎn)樹的level為0，如果一棵樹的權(quán)值最小出邊所連的另一棵樹的level變量大于或等于自己的level變量，則兩棵樹通過這條邊合并，否則等待。所合并的樹的level取決于兩棵樹中l(wèi)evel較大者，若兩棵樹level相同為L，則新合并的樹的level=L+1。(level的含義：好比游戲中的練級)38§補(bǔ)充構(gòu)造最小生成樹可能出現(xiàn)的4個問題：14§補(bǔ)充構(gòu)造最小生成樹可能出現(xiàn)的4個問題：錯誤判斷出邊

異步系統(tǒng)中，可能出現(xiàn)在判斷一條邊是否是出邊時，邊連接的兩點(diǎn)已經(jīng)處在一棵樹當(dāng)中了，但由于消息延遲導(dǎo)致樹編號的更新消息還未傳到，因而導(dǎo)致因為兩節(jié)點(diǎn)的樹編號不同而產(chǎn)生的錯誤。解決方法：

在合并之前，樹中節(jié)點(diǎn)按邊的權(quán)值由小到大的順序開始探測此邊是否是出邊，當(dāng)確認(rèn)某條邊是出邊之后便停止探測其他邊，并將結(jié)果斂播給根節(jié)點(diǎn)，由根節(jié)點(diǎn)確定通過哪一條邊進(jìn)行合并。當(dāng)兩棵樹合并時，合并后的樹的編號以及根節(jié)點(diǎn)取level值較大的那棵樹的根和樹編號。若level值相同，取樹編號較大的樹的根和樹編號。然后由根執(zhí)行廣播操作，更新所有樹編號和level值，并通知尋找權(quán)值最小的出邊。

（確定Pi和Pj是否屬于一棵樹）①如果Pi和Pj編號相同，則肯定屬于一棵樹；②如果編號不同，但Pj的level和Pi一樣大，則肯定不屬于一棵樹，因為每棵樹在一層中不可能有兩個樹編號，且當(dāng)Pi在尋找其權(quán)值最小的出邊的時候，其樹編號是最新的；③如果Pj的樹編號與Pi不同且Pj的層數(shù)嚴(yán)格小于Pi，那么節(jié)點(diǎn)Pj就延遲回答Pi直到他更新到其level值上升到至少和Pi一樣大。(可以證明，這個新增的延遲將不會構(gòu)成節(jié)點(diǎn)間的死鎖)39§補(bǔ)充構(gòu)造最小生成樹可能出現(xiàn)的4個問題：15§補(bǔ)充構(gòu)造最小生成樹可能出現(xiàn)的4個問題：存在干擾不同層的鄰接樹同時尋找權(quán)值最小的出邊有可能發(fā)生相互干擾。具體來說，當(dāng)層低的樹T合并到層高的樹T’，而T’正在確定其權(quán)值最小出邊時可能會發(fā)生此情況。40§補(bǔ)充構(gòu)造最小生成樹可能出現(xiàn)的4個問題：16§補(bǔ)充構(gòu)造最小生成樹算法框架：CodeforEveryTreeTBeginWhile(系統(tǒng)中的子樹個數(shù)大于1)do(1)根節(jié)點(diǎn)廣播ID(T)和level(T)，命令各節(jié)點(diǎn)尋找權(quán)值最小的邊；(2)按權(quán)值由小到大順序?qū)ふ覚?quán)值最小的出邊，找到之后斂播給根節(jié)點(diǎn)；(3)根節(jié)點(diǎn)收到所有節(jié)點(diǎn)的權(quán)值最小出邊后，確定整棵樹的最小出邊e，邊e連接樹T’。/*level(T)≤level(T’)*/(4)T’’=T∪T’∪e(5)iflevel(T’)>level(T)then(5.1)ID(T’’)←ID(T’)(5.2)level(T’’)←level(T’)else//level(T’)=level(T)(5.3)ID(T’’)←max{ID(T),ID(T’)}(5.4)level(T’’)←level(T’’