第二部分分布式算法PPT課件

1、1第二部分第二部分 分布式算法分布式算法第三次課第三次課中國科學(xué)技術(shù)大學(xué)計算機系中國科學(xué)技術(shù)大學(xué)計算機系 國家高性能計算中心（合肥）國家高性能計算中心（合肥）22.2.2 convergecast(匯集，斂播匯集，斂播)與廣播問題相反，匯集是從所有結(jié)點收集信息至根。與廣播問題相反，匯集是從所有結(jié)點收集信息至根。為簡單起見，先考慮一個特殊的變種問題：為簡單起見，先考慮一個特殊的變種問題： 假定每個假定每個pi開始時有一初值開始時有一初值xi，我們希望將這些值中，我們希望將這些值中最大者發(fā)送至根最大者發(fā)送至根pr。32.2.2 convergecast(匯集，斂播匯集，斂播)n算法算法 每個葉子結(jié)

2、點每個葉子結(jié)點pi發(fā)送發(fā)送xi至雙親。至雙親。/啟動者啟動者對每個非葉結(jié)點對每個非葉結(jié)點pj，設(shè)，設(shè)pj有有k個孩子個孩子pi1,pik，pj等待等待k個孩子的個孩子的msg vi1,vi2,vik，當(dāng)，當(dāng)pj收到所有孩子的收到所有孩子的msg之后將之后將vj=maxxj,vi1,vik發(fā)送到發(fā)送到pj的雙親。的雙親。換言之：換言之：葉子先啟動，每個處理器葉子先啟動，每個處理器pi計算以自己為計算以自己為根的子樹里的最大值根的子樹里的最大值vi，將，將vi發(fā)送給發(fā)送給pi的雙親。的雙親。n 復(fù)雜性復(fù)雜性Th2.5 當(dāng)生成樹高為當(dāng)生成樹高為d時，存在一個異步的斂播方法，時，存在一個異步的斂播方法

3、，其其msg復(fù)雜性為復(fù)雜性為n-1，時間復(fù)雜度為，時間復(fù)雜度為d。(與與Th2.2相同相同)n 廣播和斂播算法用途：廣播和斂播算法用途：初始化某一信息請求初始化某一信息請求(廣播發(fā)廣播發(fā)布布)，然后用斂播響應(yīng)信息至根。，然后用斂播響應(yīng)信息至根。42.3 構(gòu)造生成樹構(gòu)造生成樹上節(jié)算法均假設(shè)通信網(wǎng)的生成樹已知。本節(jié)介上節(jié)算法均假設(shè)通信網(wǎng)的生成樹已知。本節(jié)介紹生成樹的構(gòu)造問題。紹生成樹的構(gòu)造問題。1.Flooding算法算法(淹沒淹沒)n 算法算法 設(shè)設(shè)pr是特殊處理是特殊處理器。從器。從pr開始，開始，發(fā)送發(fā)送M到其所有鄰到其所有鄰居。當(dāng)居。當(dāng)pi第第1次收次收到消息到消息M（不妨設(shè)（不妨設(shè)此此m

4、sg來自于鄰來自于鄰居居pj）時，）時，pi發(fā)送發(fā)送M到除到除pj外的所有外的所有鄰居。鄰居。52.3 構(gòu)造生成樹構(gòu)造生成樹n msg復(fù)雜性復(fù)雜性因為每個結(jié)點在任一信道上發(fā)送因為每個結(jié)點在任一信道上發(fā)送M不會多于不會多于1次，次，所以每個信道上所以每個信道上M至多被發(fā)送兩次至多被發(fā)送兩次(使用該信道的每使用該信道的每個處理器各個處理器各1次次)。在最壞情況下：在最壞情況下：M除第除第1次接收的那些信道外，所次接收的那些信道外，所有其他信道上有其他信道上M被傳送被傳送2次。因此，有可能要發(fā)送次。因此，有可能要發(fā)送2m-(n-1)個個msgs。這里。這里m是系統(tǒng)中信道總數(shù)，它是系統(tǒng)中信道總數(shù)，它可

5、能多達可能多達n(n-1)/2。n 時間復(fù)雜性：時間復(fù)雜性：O(D)D網(wǎng)直徑網(wǎng)直徑2.構(gòu)造生成樹構(gòu)造生成樹對于對于flooding稍事修改即可得到求生成樹的方法。稍事修改即可得到求生成樹的方法。62.3 構(gòu)造生成樹構(gòu)造生成樹基本思想基本思想n 首先，首先，pr發(fā)送發(fā)送M給所有鄰居，給所有鄰居，pr為根為根n 當(dāng)當(dāng)pi從某鄰居從某鄰居pj收到的收到的M是第是第1個來自鄰居的個來自鄰居的msg時，時，pj是是pi的雙親；若的雙親；若pi首次收到的首次收到的M同時來自多個鄰居，同時來自多個鄰居，則用一個則用一個comp事件處理自上一事件處理自上一comp事件以來的事件以來的所有所有已收到已收到的的m

6、sgs，故此時，故此時，pi可在這些鄰居中可在這些鄰居中任選任選一個一個鄰居鄰居pj做雙親。做雙親。n 當(dāng)當(dāng)pi確定雙親是確定雙親是pj時，發(fā)送時，發(fā)送給給pj，并向此后收，并向此后收到發(fā)來到發(fā)來M的處理器發(fā)送的處理器發(fā)送msg72.3 構(gòu)造生成樹構(gòu)造生成樹基本思想基本思想n 因為因為pi收到收到pj的的M是第是第1個個M，就不可能已收到其他結(jié)，就不可能已收到其他結(jié)點的點的M，當(dāng)然可能同時收到，當(dāng)然可能同時收到(說明說明pi與這些鄰居間不是與這些鄰居間不是父子關(guān)系，或說它們不是生成樹中的邊父子關(guān)系，或說它們不是生成樹中的邊)；同時；同時pi將將M轉(zhuǎn)發(fā)給其余鄰居，這些鄰居轉(zhuǎn)發(fā)給其余鄰居，這些鄰居

7、尚未發(fā)尚未發(fā)M給給pi，或雖然已發(fā)，或雖然已發(fā)M給給pi，但，但pi尚未收到尚未收到。n pi向那些尚未發(fā)向那些尚未發(fā)M給給pi(或已發(fā)或已發(fā)M但尚未到達但尚未到達pi)的鄰居的鄰居轉(zhuǎn)發(fā)轉(zhuǎn)發(fā)M之后，等待這些鄰居發(fā)回響應(yīng)之后，等待這些鄰居發(fā)回響應(yīng)msg：或或。那些回應(yīng)。那些回應(yīng)的鄰居是的鄰居是pi的孩子。的孩子。n 當(dāng)當(dāng)pi發(fā)出發(fā)出M的所有接收者均已回應(yīng)的所有接收者均已回應(yīng)(或或)，則，則pi終止。將終止。將parent和和children邊保留即邊保留即為生成樹。為生成樹。82.3 構(gòu)造生成樹構(gòu)造生成樹圖示圖示pi若認(rèn)為若認(rèn)為pj是其雙親，則是其雙親，則pi向向pr發(fā)出發(fā)出M，而，而pr仍會向

8、仍會向pi發(fā)發(fā)reject，但因為此前，但因為此前pr向向pi發(fā)出過發(fā)出過M，故，故pi收到收到M時時仍會向仍會向pr發(fā)發(fā)reject。(可以改進？可以改進？)92.3 構(gòu)造生成樹構(gòu)造生成樹算法：算法： Alg2.2 構(gòu)造生成樹（構(gòu)造生成樹（code for pi 0in-1）初值：初值：parent=nil；集合；集合children和和other均為均為1.upon receiving no message:2. if i=r and parent=nil then /根尚未發(fā)送根尚未發(fā)送M3. send M to all neighbors;4. parent:=i; /根的雙親置為自己

9、根的雙親置為自己5.upon receiving M from neighbor pj:6. if parent=nil then /pi此前未收到過此前未收到過M，M是是pi收到的第收到的第1個個msg7. parent:=j;8. send to pj; /pj是是pi的雙親的雙親9. send M to all neighbors except pj; else /pj不可能是不可能是pi的雙親，的雙親，pi收到的收到的M不是第不是第1個個msg10. send to pj;11. upon receiving from neighbor pj:12. children:=childre

10、n j ; /pj是是pi的孩子，將的孩子，將j加入孩子集加入孩子集13. if childrenother 包含了除包含了除parent外的所有鄰居外的所有鄰居 then terminate;14. upon receiving from neighbor pj:15. other:=other j ; /將將j加入加入other，通過非樹邊發(fā)送的，通過非樹邊發(fā)送的msg。16. if childrenother包含了除包含了除pi的雙親外的所有鄰居的雙親外的所有鄰居 then terminate;102.3 構(gòu)造生成樹構(gòu)造生成樹分析分析Lemma2.6 在異步模型的每個容許執(zhí)行中，算法在異

11、步模型的每個容許執(zhí)行中，算法2.2構(gòu)造一棵根為構(gòu)造一棵根為pr的生成樹。的生成樹。(正確性正確性)Pf：算法代碼告訴我們兩個重要事實：算法代碼告訴我們兩個重要事實a) 一旦處理器設(shè)置了一旦處理器設(shè)置了parent變量，它絕不改變，即它變量，它絕不改變，即它只有一個雙親只有一個雙親b) 處理器的孩子集合決不會減小。處理器的孩子集合決不會減小。因此，最終由因此，最終由parent和和children確定的圖結(jié)構(gòu)確定的圖結(jié)構(gòu)G是是靜止的，且靜止的，且parent和和children變量在不同結(jié)點上是一變量在不同結(jié)點上是一致的，即若致的，即若pj是是pi的孩子，則的孩子，則pi是是pj的雙親。的雙親。

12、 下述證明結(jié)果圖下述證明結(jié)果圖G是根為是根為pr的有向生成樹。的有向生成樹。112.3 構(gòu)造生成樹構(gòu)造生成樹n 為何從根能到達每一結(jié)點？為何從根能到達每一結(jié)點？(連通連通)反證反證：假設(shè)某結(jié)點在：假設(shè)某結(jié)點在G中從中從pr不可達，因網(wǎng)絡(luò)是連通不可達，因網(wǎng)絡(luò)是連通的，若存在兩個相鄰的結(jié)點的，若存在兩個相鄰的結(jié)點pi和和pj使得使得pj在在G中是從中是從pr可達的可達的(以下簡稱以下簡稱pj可達可達)，但，但pi不可達。因為不可達。因為G里一里一結(jié)點結(jié)點從從pr可達當(dāng)且僅當(dāng)它曾設(shè)置過自己的可達當(dāng)且僅當(dāng)它曾設(shè)置過自己的parent變變量量(Ex 證明證明)，所以，所以pi的的parent變量在整個執(zhí)

13、行中仍變量在整個執(zhí)行中仍為為nil，而，而pj在某點上已設(shè)置過自己的在某點上已設(shè)置過自己的parent變量，變量，于是于是pj發(fā)送發(fā)送M到到pi(line9)，因該執(zhí)行是容許的，此，因該執(zhí)行是容許的，此msg必定最終被必定最終被pi接收，使接收，使pi將自己的將自己的parent變量設(shè)變量設(shè)置為置為j。矛盾！。矛盾！122.3 構(gòu)造生成樹構(gòu)造生成樹n 為何無環(huán)？為何無環(huán)？(無環(huán)無環(huán))假設(shè)有一環(huán)，假設(shè)有一環(huán)，pi1,pikpi1，若，若pi是是pj的孩子，則的孩子，則pi在在pj第第1次收到次收到M之后第之后第1次收到次收到M。因每個處理器在該環(huán)。因每個處理器在該環(huán)上是下一處理器的雙親，這就意味

14、著上是下一處理器的雙親，這就意味著pi1在在pi1第第1次接收次接收M之前第之前第1次接收次接收M。矛盾！。矛盾！n 復(fù)雜性復(fù)雜性顯然，此方法與淹沒算法相比，增加了顯然，此方法與淹沒算法相比，增加了msg復(fù)雜性，復(fù)雜性，但只是一個常數(shù)因子。在異步通信模型里，易看到在但只是一個常數(shù)因子。在異步通信模型里，易看到在時刻時刻t，消息，消息M到達所有與到達所有與pr距離小于等于距離小于等于t的結(jié)點。因的結(jié)點。因此有：此有：Th2.7 對于具有對于具有m條邊和直徑條邊和直徑D的網(wǎng)絡(luò)，給定一特殊結(jié)點，的網(wǎng)絡(luò)，給定一特殊結(jié)點，存在一個存在一個msg復(fù)雜性為復(fù)雜性為O(m)，時間復(fù)雜性為，時間復(fù)雜性為O(D)

15、的異的異步算法找到該網(wǎng)絡(luò)的一棵生成樹。步算法找到該網(wǎng)絡(luò)的一棵生成樹。132.3 構(gòu)造生成樹構(gòu)造生成樹Alg2.2在同步模型下仍可工作。其分析類似于異步在同步模型下仍可工作。其分析類似于異步情形。然而，與異步不同的是，它所構(gòu)造的生成樹情形。然而，與異步不同的是，它所構(gòu)造的生成樹一定是一棵廣度優(yōu)先搜索一定是一棵廣度優(yōu)先搜索(BFS)樹。樹。Lemma2.8 在同步模型下，在同步模型下，Alg2.2的每次容許執(zhí)行的每次容許執(zhí)行均構(gòu)造一棵根為均構(gòu)造一棵根為pr的的BFS樹。樹。Pf：對輪對輪t進行歸納進行歸納。即要證明：在第。即要證明：在第t輪開始時刻輪開始時刻 根據(jù)根據(jù)parent變量構(gòu)造的圖變量構(gòu)

16、造的圖G是一棵包括所有與是一棵包括所有與pr距離至多為距離至多為t-1結(jié)點的結(jié)點的BFS樹；樹； 而傳輸中的消息而傳輸中的消息M僅來自于與僅來自于與pr距離恰為距離恰為t-1的結(jié)的結(jié)點。點。 由此構(gòu)造的樹是一棵根為由此構(gòu)造的樹是一棵根為pr的的BFS142.3 構(gòu)造生成樹構(gòu)造生成樹當(dāng)當(dāng)t=1時，所有時，所有parent初值為初值為nil，M從從pr傳出。傳出。假設(shè)引理對第假設(shè)引理對第t-11輪為真，在該輪里，從距離輪為真，在該輪里，從距離 t-2的結(jié)點傳出的的結(jié)點傳出的M被接收，任何接收被接收，任何接收M的結(jié)點與的結(jié)點與pr的的距離不超過距離不超過t-1(恰為恰為t-1或更短或更短)，那些，那

17、些parent值非空值非空的接收結(jié)點顯然與的接收結(jié)點顯然與pr的距離不超過的距離不超過t-2，他們既不改，他們既不改變變parent的值也不轉(zhuǎn)發(fā)的值也不轉(zhuǎn)發(fā)M；而與；而與pr距離為距離為t-1的結(jié)點的結(jié)點在在t-1輪里收到輪里收到M，因為它們的，因為它們的parent為為nil，故將其，故將其置為合適的雙親并轉(zhuǎn)發(fā)置為合適的雙親并轉(zhuǎn)發(fā)M。距離。距離pr大于大于t-1的結(jié)點不的結(jié)點不會收到會收到M，因此也不會轉(zhuǎn)發(fā)，因此也不會轉(zhuǎn)發(fā)M。因此有如下定理：。因此有如下定理：Th2.9 對于具有對于具有m條邊直徑為條邊直徑為D的網(wǎng)絡(luò)，給定一個特的網(wǎng)絡(luò)，給定一個特殊結(jié)點，存在一個同步算法在殊結(jié)點，存在一個同步

18、算法在msg復(fù)雜性為復(fù)雜性為O(m)，時間復(fù)雜性為時間復(fù)雜性為O(D)內(nèi)找到一棵內(nèi)找到一棵BFS樹。樹。152.3 構(gòu)造生成樹構(gòu)造生成樹n 異步系統(tǒng)里，異步系統(tǒng)里，Alg2.2能構(gòu)造能構(gòu)造BFS樹？樹？例如，考慮例如，考慮5個頂點的完全連通圖個頂點的完全連通圖P0P2P4P3P1MMMMu P0為根，假定為根，假定M消息按消息按P0到到p1，P1到到P2，P2到到P3，P3到到P4的次的次序快速傳播，而序快速傳播，而M在其它路徑在其它路徑上傳播較慢。結(jié)果生成樹是從上傳播較慢。結(jié)果生成樹是從P0到到P4的鏈，它不是的鏈，它不是BFS樹樹u 雖然此圖直徑雖然此圖直徑D=1，生成樹的，生成樹的高度高

19、度d=4，但是算法的運行時，但是算法的運行時間仍然為間仍然為O(D)而不是而不是O(d)。 理解：理解：P0到到P4的的M在在1個時間個時間內(nèi)到達，即內(nèi)到達，即P0-P1-P2-P3-P4的時間之和不超過的時間之和不超過1。162.3 構(gòu)造生成樹構(gòu)造生成樹n信息的請求和收集信息的請求和收集將算法將算法2.2(求生成樹求生成樹)和匯集算法組合即可完成。組合算法和匯集算法組合即可完成。組合算法的時間復(fù)雜性在同步和異步模型中不同的時間復(fù)雜性在同步和異步模型中不同,設(shè)網(wǎng)是設(shè)網(wǎng)是完全圖完全圖v 求生成樹算法求生成樹算法：同步和異步均為：同步和異步均為 消息復(fù)雜性消息復(fù)雜性O(shè)(m) 時間復(fù)雜性時間復(fù)雜性O(shè)

20、(D)v 匯集算法匯集算法：同步和異步均有：同步和異步均有 msg n-1 time d /生成樹高生成樹高v 組合算法組合算法 同步：組合算法的同步：組合算法的msg復(fù)雜性復(fù)雜性O(shè)(m+n)；BFS樹中，樹中， d=1， dD，故時間復(fù)雜性，故時間復(fù)雜性O(shè)(D+d)=O(D)=O(1)。 異步：組合算法的異步：組合算法的msg復(fù)雜性復(fù)雜性O(shè)(m+n)；生成樹高生成樹高 d=n-1，所以時間復(fù)雜性，所以時間復(fù)雜性O(shè)(D+d)=O(d)=O(n)。 1-time復(fù)雜性的組合算法復(fù)雜性的組合算法T(n)=O(D)。 172.4 構(gòu)造構(gòu)造DFS生成樹生成樹(指定根指定根)回憶無向圖的深度優(yōu)先搜索問題

21、：回憶無向圖的深度優(yōu)先搜索問題：n 方法：方法：v 從任意頂點開始訪問，例如Av 然后訪問它的一個一個沒有訪問過的鄰接點，例如Bv 若無未訪問過的鄰接點,則后退尋找，直至全部被訪問為止ABCDEFGHI123456789182.4 構(gòu)造構(gòu)造DFS生成樹生成樹(指定根指定根)基本思想：n設(shè)定Pr為指定的根節(jié)點，Pr從還未向其發(fā)送消息的鄰接節(jié)點中任選一個節(jié)點發(fā)送消息。n當(dāng)Pi從Pj收到的消息是第一個來自于鄰接節(jié)點的消息時，Pj為Pi的雙親，向其發(fā)送消息，并向此后向自己發(fā)送消息的鄰居發(fā)送消息。nPi從還未發(fā)送過消息的鄰居中任選一個，發(fā)送消息，然后等待或者消息，并將回應(yīng)的節(jié)點加到自己的孩子集合中。n當(dāng)

22、Pi向所有的鄰居都轉(zhuǎn)發(fā)過消息后，Pi終止。ABCDEFGHI123456789192.4 構(gòu)造構(gòu)造DFS生成樹生成樹(指定根指定根) 構(gòu)造構(gòu)造DFS樹時每次加一個結(jié)點，而不像樹時每次加一個結(jié)點，而不像Alg2.2那樣，那樣，試圖在樹上同時增加同一層的所有結(jié)點。試圖在樹上同時增加同一層的所有結(jié)點。Alg2.3 構(gòu)造構(gòu)造DFS生成樹，為生成樹，為Pr為根為根Code for processor Pi, 0i n-1varparent:init nil;children:init ; ;unexplored: init all the neighbors of Pi /未訪問過的鄰居集未訪問過的鄰居

23、集1: upon receiving no msg:2: if (i=r) and (parent=nil) then /當(dāng)當(dāng)Pi為根且未發(fā)送為根且未發(fā)送M時時3: parent := i; /將將parent置為自身的標(biāo)號置為自身的標(biāo)號4: Pj unexplored;5: 將將Pj從從unexplored中刪去中刪去; /若若Pr是孤立結(jié)點是孤立結(jié)點,4-6應(yīng)稍作修改應(yīng)稍作修改6: send M to Pj; /endif202.4 構(gòu)造構(gòu)造DFS生成樹生成樹(指定根指定根)7: upon receiving M from neighbor Pj:8: if parent=nil then

24、 /Pi此前未收到此前未收到M9: parent := j; /Pj是是Pi的父親的父親10: 從從unexplored中刪中刪Pj11: if unexplored then 12: Pk unexplored;13: 將將Pk從從unexplored中刪去；中刪去；14: send M to Pk;15: else send to parent; /當(dāng)當(dāng)Pi的鄰居均已訪問過，返回到父親的鄰居均已訪問過，返回到父親16: else send to Pj; /當(dāng)當(dāng)Pi已訪問過時已訪問過時212.4 構(gòu)造構(gòu)造DFS生成樹生成樹(指定根指定根)17: upon receiving or from neighbor Pj:18: if received t