1、12.1.2 復(fù)雜性度量分布式算法的性能：消息復(fù)雜度時間復(fù)雜度空間復(fù)雜度性能衡量：最壞性能、期望性能終止：假定每個處理器的狀態(tài)集包括終止狀態(tài)子集，每個的pi的轉(zhuǎn)換函數(shù)對終止狀態(tài)只能映射到終止狀態(tài)當所有處理機均處于終止狀態(tài)且沒有msg在傳輸時，稱系統(tǒng)(算法)已終止。22.1.2 復(fù)雜性度量算法的msg復(fù)雜性(最壞情況)：算法在所有容許的執(zhí)行上發(fā)送msg總數(shù)的最大值(同步和異步系統(tǒng))消息復(fù)雜度度量消息復(fù)雜度：消息總數(shù)/消息中總的位數(shù)長度消息總數(shù)：4/4消息位數(shù)總長度(位復(fù)雜度)：14/832.1.2 復(fù)雜性度量時間復(fù)雜度同步系統(tǒng)：最大輪數(shù)，即算法的任何容許執(zhí)行直到終止的最大輪數(shù)。異步系統(tǒng)：假設(shè)：節(jié)

2、點計算任何有限數(shù)目事件的時間為0；一條消息發(fā)送和接收之間的時間至多為1個時間單位，定義為：所有計時容許執(zhí)行中直到終止的最大時間。計時執(zhí)行(timed execution)指：每個事件關(guān)聯(lián)一個非負實數(shù)，表示事件發(fā)生的時間。時間起始于零，且須是非遞減的。但對每個單個的處理器而言是嚴格增的。若執(zhí)行是無限的，則執(zhí)行的時間是無界的。因此執(zhí)行中的事件可根據(jù)其發(fā)生時間來排序不在同一處理器上的多個事件可以同時發(fā)生，在任何有限時間之前只有有限數(shù)目的事件發(fā)生。42.1.2 復(fù)雜性度量消息的延遲發(fā)送msg的計算事件和處理該msg的計算事件之間所逝去的時間它主要由msg在發(fā)送者的outbuf中的等待時間和在接收者的i

3、nbuf中的等待時間所構(gòu)成異步算法的時間復(fù)雜性定義中，每個msg延時至多為1，但實際中，至多1個時間單位會很難計算，因此修改假設(shè)： 一條消息發(fā)送和接收之間時間恰好為1個時間單位 一條消息發(fā)送和接收之間時間介于和1之間(0 1) 假設(shè)消息傳遞的延遲滿足某種概率分布，并由此來計算52.1.3 偽代碼約定在形式模型中，一個算法將根據(jù)狀態(tài)轉(zhuǎn)換來描述。但實際上很少這樣做，因為這樣做難于理解。 實際描述算法有兩種方法： 敘述性：對于簡單問題 偽碼形式：對于復(fù)雜問題62.1.3 偽代碼約定異步算法：對每個處理器，用中斷驅(qū)動來描述異步算法。在形式模型中，每個計算事件1次處理所有輸入緩沖區(qū)中的msgs。而在算法

4、中，一般須描述每個msg是如何逐個處理的異步算法也可在同步系統(tǒng)中工作，因為同步系統(tǒng)是異步系統(tǒng)的一個特例。一個計算事件中的局部計算的描述類似于順序算法的偽代碼描述。同步算法：逐輪描述偽代碼約定：在pi的局部變量中，無須用i做下標，但在討論和證明中，加上下標i以示區(qū)別。“/”后跟注釋72.2 生成樹上的廣播和匯集為什么廣播和匯集算法 信息收集（斂播/匯集）及分發(fā)(廣播)是許多分布式算法的基礎(chǔ)。故通過介紹這兩個算法來說明模型、偽碼、正確性證明及復(fù)雜性度量等概念。為什么生成樹上？由于分布式系統(tǒng)中，每個節(jié)點并不知道全局拓撲狀態(tài)，但某些算法需要在特定的結(jié)構(gòu)下才能達到最優(yōu)。例如：廣播/斂播在樹結(jié)構(gòu)下才能達到

5、消息復(fù)雜度最優(yōu)，因此構(gòu)造生成樹是必要的，且是其他算法的基礎(chǔ)。82.2 生成樹上的廣播和匯集生成樹 一個無向連通圖G的生成樹(Spanning Tree)是指滿足下列條件的G的子圖T： G和T具有相同的頂點數(shù)； 在T中有足夠的邊能夠連接G的所有頂點且不出現(xiàn)回路。最小生成樹 如果圖的每一條邊都指定有一個權(quán)，那么所有的邊權(quán)最小的生成樹，就成為最小代價生成樹(Minimum Cost Spanning Tree, MCST) ，簡稱最小生成樹(MST)。生成樹一共有16棵最小生成樹92.2 生成樹上的廣播和匯集2.2.1 廣播 (Broadcast) 假定網(wǎng)絡(luò)的生成樹已給定。某處理器pr希望將消息M發(fā)

6、送至其余處理器。 假定生成樹的根為pr ，每個處理器有一個信道連接其雙親(pr除外)，有若干個信道連接其孩子。102.2.1 廣播根pr發(fā)送M給所有孩子。(a)當某節(jié)點收到父節(jié)點的M時，發(fā)送M到自己的所有孩子(b)。112.2.1 廣播1.偽碼算法Alg2.1 Broadcast pr:/發(fā)動者。假設(shè)初始化時M已在傳輸狀態(tài)1.upon receiving no msg:/pr發(fā)送M后執(zhí)行終止2. terminate;/將terminated置為true。pi(ir,0i n-1):3.upon receiving M from parent:4. send M to all children;

7、5. terminate;2.用狀態(tài)轉(zhuǎn)換來分析算法每個處理器pi包含狀態(tài)變量parenti：表示處理器pi雙親節(jié)點的標號或為nil(若i=r) 變量childreni：pi的孩子節(jié)點標號的集合布爾變量terminatedi：表示pi是否處于終止狀態(tài)122.2.1 廣播初始狀態(tài)parent和children的值是形成生成樹時確定的所有terminated的值均為假outbufr j , jchildrenr持有消息M，注意j不是信道標號，而是r的鄰居號。（任何系統(tǒng)中，均假定各節(jié)點標號互不相等）所有其他節(jié)點的outbuf變量均為空。comp(i)的結(jié)果若對于某個k，M在inbufik里，則M被放到

8、outbufi j 里， jchildreni132.2.1 廣播pi進入終止狀態(tài)將terminatedi置為true；若i=r且terminatedr為false，則terminatedr立即置為true，否則空操作。該算法對同步及異步系統(tǒng)均正確，且在兩模型中，msg和時間復(fù)雜度相同。Msg復(fù)雜度無論在同步還是異步模型中，msg M在生成樹的每條邊上恰好發(fā)送一次。因此，msg復(fù)雜性為n-1，即O(n)。 時間復(fù)雜度為h，即O(h)，其中h為生成樹的高度。142.2.1 廣播輸入：根節(jié)點上的消息輸出：每個節(jié)點都收到消息Code for PiBegin while (receiving no m

9、essage) do (1) if i=r then 此節(jié)點為根節(jié)點 (1.1) send to all children (1.2) terminates end if end while while (receiving from Pj) do (1) send to all children (2) terminates end whileend 說明：本算法中While并不代表循環(huán)，而是代表滿足條件時，節(jié)點所做的動作152.2.1 廣播時間復(fù)雜性：同步模型：時間由輪來度量。Lemma2.1 在同步模型中，在廣播算法的每個容許執(zhí)行里，樹中每個距離pr為t的處理器在第t輪里接收消息M。pf

10、：對距離t使用歸納法。歸納基礎(chǔ)：t=1，pr的每個孩子在第1輪里接收來自于pr的消息M歸納假設(shè)：假設(shè)樹上每個距pr為t-11的處理器在第t-1輪里已收到M。歸納步驟：設(shè)pi到pr距離為t，設(shè)pj是pi的雙親，因pj到pr的距離為t-1，由歸納假設(shè)，在第t-1輪pj收到M。由算法描述知，在第t輪里pi收到來自于pj的消息MTh2.2 當生成樹高度為d時，存在一個消息復(fù)雜度為n-1，時間復(fù)雜度為d的同步廣播算法162.2.1 廣播異步模型Lemma2.3 在異步模型的廣播算法的每個容許執(zhí)行里，樹中每個距離pr為t的處理器至多在時刻t接收消息M。pf：對距離t做歸納。對t=1，初始時，M處在從pr到

11、所有距離為1的處理器pi的傳輸之中，由異步模型的時間復(fù)雜性定義知，pi至多在時刻1收到M。 pi 距pr為t的處理器，設(shè)pj是pi的雙親，則pj與pr的距離為t-1，由歸納假設(shè)知，pj至多在時刻t-1收到M，由算法描述知，pj發(fā)送給pi的M至多在t時刻到達。Th2.4 同Th2.2172.2.2 convergecast(匯集/斂播)與廣播問題相反，匯集是從所有節(jié)點收集信息至根。為簡單起見，先考慮一個特殊的變種問題： 假定每個pi開始時有一初值xi，我們希望將這些值中最大者發(fā)送至根pr。182.2.2 convergecast(匯集，斂播)算法 每個葉子節(jié)點pi發(fā)送xi至雙親。/啟動者對每個非

12、葉節(jié)點pj，設(shè)pj有k個孩子pi1,pik，pj等待k個孩子的msg vi1,vi2,vik，當pj收到所有孩子的msg之后將vj=maxxj,vi1,vik發(fā)送到pj的雙親。換言之：葉子先啟動，每個處理器pi計算以自己為根的子樹里的最大值vi，將vi發(fā)送給pi的雙親。復(fù)雜性Th2.5 當生成樹高為d時，存在一個異步的斂播方法，其msg復(fù)雜性為n-1，時間復(fù)雜度為d。(與Th2.2相同)廣播和斂播算法用途：初始化某一信息請求(廣播發(fā)布)，然后用斂播響應(yīng)信息至根。192.2.2 convergecast(匯集，斂播)輸入：每個節(jié)點的初值x輸出：根節(jié)點上輸出最大值Code for PiInit v

13、ar: maxx, received 0begin while (receiving no message) do (1) if children=then /葉子節(jié)點 (1.1) send to Pparent (1.2) terminates end if end while while (receiving from Pj) do (1) if ymax them max y end if (2) received received+1 (3) if |children|=received then /已收到所有孩子的消息 (3.1) if ir then (i) send to Ppa

14、rent (ii) terminates (3.2) else terminates and maximum value of the Tree is max end if end if end whileend202.3 構(gòu)造生成樹上節(jié)算法均假設(shè)通信網(wǎng)的生成樹已知。本節(jié)介紹生成樹的構(gòu)造問題。1.Flooding算法(洪泛/淹沒)算法 設(shè)pr是特殊處理器。從pr開始，發(fā)送M到其所有鄰居。當pi第1次收到消息M（不妨設(shè)此msg來自于鄰居pj）時，pi發(fā)送M到除pj外的所有鄰居。212.3 構(gòu)造生成樹1.Flooding算法(洪泛/淹沒)輸入：特殊節(jié)點上的消息輸出：每個節(jié)點都接收到的消息Code

15、for PiBegin while (receiving no message) do (1) if i=r then /此節(jié)點為初始節(jié)點(1.1) send to all neighbors(1.2) terminates end if end while while (receiving from Pj) do (1) send to all neighbors except Pj (2) terminates end whileend 222.3 構(gòu)造生成樹msg復(fù)雜性因為每個節(jié)點在任一信道上發(fā)送不會多于1次，所以每個信道上至多被發(fā)送兩次(使用該信道的每個處理器各1次)。在最壞情況下：除

16、了發(fā)送消息被使用的那些信道外，所有其他信道上被傳送2次。因此，最壞情況為2e-E(Pr)。這里e是系統(tǒng)中信道總數(shù)，它可能多達n(n-1)/2，E(Pr)是與Pr相連接的信道數(shù)，所以其為O(e)。時間復(fù)雜性：O(D)D網(wǎng)直徑2.構(gòu)造生成樹對于flooding稍事修改即可得到求生成樹的方法。232.3 構(gòu)造生成樹基本思想首先，pr發(fā)送M給所有鄰居，pr為根當pi從某鄰居pj收到的M是第1個來自鄰居的msg時，pj是pi的雙親；若pi首次收到的M同時來自多個鄰居，則用一個comp事件處理自上一comp事件以來的所有已收到的msgs，故此時，pi可在這些鄰居中任選一個鄰居pj做雙親。當pi確定雙親是p

17、j時，發(fā)送給pj，并向此后收到發(fā)來M的處理器發(fā)送msg242.3 構(gòu)造生成樹基本思想因為pi收到pj的M是第1個M，就不可能已收到其他節(jié)點的M，當然可能同時收到(說明pi與這些鄰居間不是父子關(guān)系，或說它們不是生成樹中的邊)；同時pi將M轉(zhuǎn)發(fā)給其余鄰居，這些鄰居尚未發(fā)M給pi，或雖然已發(fā)M給pi，但pi尚未收到。pi向那些尚未發(fā)M給pi(或已發(fā)M但尚未到達pi)的鄰居轉(zhuǎn)發(fā)M之后，等待這些鄰居發(fā)回響應(yīng)msg：或。那些回應(yīng)的鄰居是pi的孩子。當pi發(fā)出M的所有接收者均已回應(yīng)(或)，則pi終止。將parent和children邊保留即為生成樹。252.3 構(gòu)造生成樹圖示pi若認為pj是其雙親，則pi向

18、pr發(fā)出M，而pr仍會向pi發(fā)reject，但因為此前pr向pi發(fā)出過M，故pi收到M時仍會向pr發(fā)reject。(可以改進？)是否已經(jīng)發(fā)送過reject (即已經(jīng)收到過M)的鄰居就不要再發(fā)送M了?因為已經(jīng)發(fā)送過reject或者已經(jīng)收到過M的鄰居，節(jié)點上必然已經(jīng)有M，所以發(fā)送的結(jié)果必然是reject262.3 構(gòu)造生成樹算法：Alg2.2 構(gòu)造生成樹（code for pi 0in-1）初值：parent=nil；集合children和other均為upon receiving no message: if i=r and parent=nil then /根尚未發(fā)送M send M to a

19、ll neighbors; parent:=i; /根的雙親置為自己upon receiving M from neighbor pj: if parent=nil then /pi此前未收到過M，M是pi收到的第1個msg parent:=j; send to pj; /pj是pi的雙親 send M to all neighbors except pj; else /pj不可能是pi的雙親，pi收到的M不是第1個msg send to pj;upon receiving from neighbor pj: children:=children j ; /pj是pi的孩子，將j加入孩子集 i

20、f childrenother 包含了除parent外的所有鄰居 then terminate;upon receiving from neighbor pj: other:=other j ; /將j加入other，通過非樹邊發(fā)送的msg。 if childrenother包含了除pi的雙親外的所有鄰居 then terminate;272.3 構(gòu)造生成樹分析Lemma2.6 在異步模型的每個容許執(zhí)行中，算法2.2構(gòu)造一棵根為pr的生成樹。(正確性)Pf：算法代碼告訴我們兩個重要事實一旦處理器設(shè)置了parent變量，它絕不改變，即它只有一個雙親處理器的孩子集合決不會減小。因此，最終由pare

21、nt和children確定的圖結(jié)構(gòu)G是靜止的，且parent和children變量在不同節(jié)點上是一致的，即若pj是pi的孩子，則pi是pj的雙親。 下述證明結(jié)果圖G是根為pr的有向生成樹。282.3 構(gòu)造生成樹為何從根能到達每一節(jié)點？(連通)反證：假設(shè)某節(jié)點在G中從pr不可達，因網(wǎng)絡(luò)是連通的，若存在兩個相鄰的節(jié)點pi和pj使得pj在G中是從pr可達的(以下簡稱pj可達)，但pi不可達。因為G里一節(jié)點從pr可達當且僅當它曾設(shè)置過自己的parent變量(Ex2.4證明)，所以pi的parent變量在整個執(zhí)行中仍為nil，而pj在某點上已設(shè)置過自己的parent變量，于是pj發(fā)送M到pi(line9

22、)，因該執(zhí)行是容許的，此msg必定最終被pi接收，使pi將自己的parent變量設(shè)置為j。矛盾！292.3 構(gòu)造生成樹為何無環(huán)？(無環(huán))假設(shè)有一環(huán)，pi1,pikpi1，若pi是pj的孩子，則pi在pj第1次收到M之后第1次收到M。因每個處理器在該環(huán)上是下一處理器的雙親，這就意味著pi1在pi1第1次接收M之前第1次接收M。矛盾！復(fù)雜性顯然，此方法與flooding算法相比，增加了msg復(fù)雜性，但只是一個常數(shù)因子。在異步通信模型里，易看到在時刻t，消息M到達所有與pr距離小于等于t的節(jié)點。因此有：Th2.7 對于具有e條邊和直徑D的網(wǎng)絡(luò)，給定一特殊節(jié)點，存在一個msg復(fù)雜性為O(e)，時間復(fù)雜

23、性為O(D)的異步算法找到該網(wǎng)絡(luò)的一棵生成樹。4e-2E(Pr)，因為可能發(fā)送的消息除了，還有reject和parent中的一個302.3 構(gòu)造生成樹Alg2.2在同步模型下仍可工作。其分析類似于異步情形。然而，與異步不同的是，它所構(gòu)造的生成樹一定是一棵廣度優(yōu)先搜索(BFS)樹。對于異步算法，構(gòu)造出來的未必是廣度優(yōu)先搜索數(shù)，且可能每次生成的數(shù)都不盡相同。Lemma2.8 在同步模型下，Alg2.2的每次容許執(zhí)行均構(gòu)造一棵根為pr的BFS樹。Pf：對輪t進行歸納。即要證明：在第t輪開始時刻 根據(jù)parent變量構(gòu)造的圖G是一棵包括所有與pr距離至多為t-1節(jié)點的BFS樹； 而傳輸中的消息M僅來自

24、于與pr距離恰為t-1的節(jié)點。 由此構(gòu)造的樹是一棵根為pr的BFS312.3 構(gòu)造生成樹當t=1時，所有parent初值為nil，M從pr傳出。假設(shè)引理對第t-11輪為真，在該輪里，從距離 t-2的節(jié)點傳出的M被接收，任何接收M的節(jié)點與pr的距離不超過t-1(恰為t-1或更短)，那些parent值非空的接收節(jié)點顯然與pr的距離不超過t-2，他們既不改變parent的值也不轉(zhuǎn)發(fā)M；而與pr距離為t-1的節(jié)點在t-1輪里收到M，因為它們的parent為nil，故將其置為合適的雙親并轉(zhuǎn)發(fā)M。距離pr大于t-1的節(jié)點不會收到M，因此也不會轉(zhuǎn)發(fā)M。因此有如下定理：Th2.9 對于具有e條邊直徑為D的網(wǎng)絡(luò)

25、，給定一個特殊節(jié)點，存在一個同步算法在msg復(fù)雜性為O(e)，時間復(fù)雜性為O(D)內(nèi)找到一棵BFS樹。322.3 構(gòu)造生成樹異步系統(tǒng)里，Alg2.2能構(gòu)造BFS樹？例如，考慮5個頂點的完全連通圖P0為根，假定M消息按P0到p1，P1到P2，P2到P3，P3到P4的次序快速傳播，而M在其它路徑上傳播較慢。結(jié)果生成樹是從P0到P4的鏈，它不是BFS樹雖然此圖直徑D=1，生成樹的高度d=4，但是算法的運行時間仍然為O(D)而不是O(d)。 理解：P0到P4的M在1個時間內(nèi)到達，即P0-P1-P2-P3-P4的時間之和不超過1。332.3 構(gòu)造生成樹信息的請求和收集將算法2.2(求生成樹)和匯集算法組

26、合即可完成。組合算法的時間復(fù)雜性在同步和異步模型中不同,設(shè)網(wǎng)是完全圖求生成樹算法：同步和異步均為 消息復(fù)雜性O(shè)(m) 時間復(fù)雜性O(shè)(D)匯集算法：同步和異步均有 msg n-1 time d /生成樹高組合算法 同步：組合算法的msg復(fù)雜性O(shè)(m+n)；BFS樹中， d=1， dD，故時間復(fù)雜性O(shè)(D+d)=O(D)=O(1)。 異步：組合算法的msg復(fù)雜性O(shè)(m+n)；生成樹高 d=n-1，所以時間復(fù)雜性O(shè)(D+d)=O(d)=O(n)。 1-time復(fù)雜性的組合算法T(n)=O(D)。 34最小生成樹1、最小生成樹性質(zhì)用貪心算法設(shè)計策略可以設(shè)計出構(gòu)造最小生成樹的有效算法。本節(jié)介紹的構(gòu)造最小

27、生成樹的Prim算法和Kruskal算法都可以看作是應(yīng)用貪心算法設(shè)計策略的例子。盡管這2個算法做貪心選擇的方式不同，它們都利用了下面的最小生成樹性質(zhì)：設(shè)G=(V,E)是連通帶權(quán)圖，U是V的真子集。如果(u,v)E，且uU，vV-U，且在所有這樣的邊中，(u,v)的權(quán)cuv最小，那么一定存在G的一棵最小生成樹，它以(u,v)為其中一條邊。這個性質(zhì)有時也稱為MST性質(zhì)。 35最小生成樹2、Prim算法 設(shè)G=(V,E)是連通帶權(quán)圖，V=1,2,n。構(gòu)造G的最小生成樹的Prim算法的基本思想是：首先置S=1，然后，只要S是V的真子集，就作如下的貪心選擇：選取滿足條件iS，jV-S，且cij最小的邊，將頂點j添加到S