第二部分分布式算法黃劉生中國科學技術大學計算機系國家高性能計算中心（合肥）2008.101Ch.1導論論§1.1分分布式系系統Def：：一個分布布式系統統是一個個能彼此此通信的的單個計計算裝置置的集合合（計算算單元：：硬———處理器器；軟———進程程）包括：緊緊耦合系系統-----如如共享內內存多處處理機松散系統統------cow、、Internet與并行處處理的分分別(具有更更高程度度的不確確定性和和行為的的獨立性性)并行處理理的目標標是使用用所有處處理器來來執行一一個大任任務而分布式式系統中中，每個個處理器器一般都都有自己己獨立的的任務，，但由于于各種原原因（為為共享資資源，可可用性和和容錯等等），處處理機之之間需要要協調彼彼此的動動作。分布式系系統無處處不在，，其作用用是：①共享資資源②改善性性能：并并行地解解決問題題③改善可可用性：：提高可可靠性，，以防某某些成分分發生故故障2§1.1分分布式系系統分布式系系統面臨臨的困難難異質性：：軟硬件環環境異步性：：事件發生生的絕對對、甚至至相對時時間不可可能總是是精確地地知道局部性：：每個計算算實體只只有全局局情況的的一個局局部視圖圖故障：各計算實實體會獨獨立地出出故障，，影響其其他計算算實體的的工作。。3§1.2分分布式計計算的理理論目標：針對分布布式系統統完成類類似于順順序式計計算中對對算法的的研究具體：對各種分分布式情情況發生生的問題進行行抽象，精確地陳陳述這些些問題，設計和分分析有效效算法解解決這些些問題，證明這些些算法的的最優性性。計算模型型：通信：計算實體體間msg傳遞遞還是共共享變量量？哪些計時時信息和和行為是是可用的的？容許哪些些錯誤復雜性度度量標準準時間，空空間通信成本本：msg的個個數，共共享變量量的大小小及個數數故障和非非故障的的數目4§1.2分分布式計計算的理理論否定結果果、下界界和不可可能的結結果常常要證證明在一一個特定定的分布布式系統統中，某某個特定定問題的的不可解解性。就像NP-完全全問題一一樣，表表示我們們不應該該總花精精力去求求解這些些問題。。當然，可可以改變變規則，，在一種種較弱的的情況下下去求解解問題。。我們側重重研究：：可計算性性：問題是否否可解？？計算復雜雜性：求解問題題的代價價是什么么？5§1.3理理論和實實際之關關系主要的分分布式系系統的種種類，分分布式計計算理論論中常用用的形式式模型之之間的關關系種類支持多任任務的OS：互斥，死死鎖檢測測和防止止等技術術在分布布式系統統中同樣樣存在。。MIMD機器：：緊耦合系系統，它它由分離的硬硬件運行共同的軟軟件構成。更松散的的分布式式系統：：由網絡（（局域、、廣域等等）連接接起來的的自治主主機構成成特點是由由分離的硬硬件運行分離的軟軟件。實體間間通過諸諸如TCP/IP棧、、CORBA或或某些其其它組件件或中間間件等接接口互相相作用。。6§1.3理理論和實實際之關關系模型模型太多多。這里里主要考考慮三種種，基于于通信介質質和同步程度度考慮。異步共享享存儲模模型：用于緊耦耦合機器器，通常常情況下下各處理理機的時時鐘信號號不是來來源于同同一信號號源異步msg傳遞遞模型：：用于松散散耦合機機器及廣廣域網同步msg傳遞遞模型：：這是一個個理想的的msg傳遞系系統。該該系統中中，某些些計時信信息（如如msg延遲上上界）是是已知的的，更實實際系統統能夠模模擬同步步msg傳遞模模型。該模型便便于設計計算法，，然后將將其翻譯譯成更實實際的模模型。7§1.3理理論和實實際之關關系錯誤的種種類Crashfailure崩潰錯錯誤指處理機機沒有任任何警告告而在某某點上停停止操作作。Byzantinefailure拜占占庭錯誤誤一個出錯錯可引起起任意的的動作8Ch.2消息息傳遞系系統中的的基本算算法本章介紹紹無故障障的msg傳遞系統統，考慮慮兩個主主要的計計時模型型：同步步及異步步。定義主要要的復雜雜性度量量、描述述偽代碼碼約定，，最后介介紹幾個個簡單算算法§2.1消消息傳遞遞系統的的形式化化模型§2.1.1系統統1.基本本概念拓撲：無向圖結結點點——處處理機邊———雙雙向信道道9§2.1.1系統統算法：由由系統中中每個處處理器上上的局部部程序構構成局部程序序執行局部部計算———本地地機器發送和接接收msg———鄰居形式地：：一個系統統或一個個算法是是由n個個處理器器p0,p1,…pn-1構成，每每個處理理器pi可以模型型化為一一個具有有狀態集集Qi的狀態機機（可能能是無限限的）10§2.1.1系統統狀態（進進程的局局部狀態態）由pi的變量，，pi的msgs構成成。pi的每個狀狀態由2r個msg集集構成：：outbufi[l](1≤l≤r):pi經第l條關聯的的信道發發送給鄰鄰居，但但尚未傳傳到鄰居居的msg。inbufi[l](1≤≤l≤r):在pi的第l條信道上上已傳遞遞到pi，但尚未未經pi內部計算算步驟處處理的msg。。模擬在信信道上傳傳輸的msgs

11§2.1.1系統統初始狀態態：Qi包含一個個特殊的的初始狀狀態子集集：每個個inbufi[l]必須為空空，但outbufi[l]未必為空空。轉換函數數(transition))：處理器pi的轉換函函數(實實際上是是一個局局部程序序)輸入：pi可訪問的的狀態輸出：對每個信信道l，至多產產生一個個msg輸出轉換函數數使輸入入緩沖區區(1≤l≤r)清空。12§2.1.1系統統配置：配置是分分布式系系統在某某點上整整個算法法的全局局狀態向量=((q0,q1,…qn-1),qi是pi的一個狀狀態一個配置置里的outbuf變量的狀狀態表示示在通信信信道上上傳輸的的信息，，由del事件件模擬傳傳輸一個初始始的配置置是向量量=(q0,q1,…qn-1),其其中每個個qi是pi的初始狀狀態，即即每個處處理器處處于初始始狀態13§2.1.1系統統事件：系統里所所發生的的事情均均被模型型化為事事件，對對于msg傳遞遞系統，，有兩種種：comp(i))——計算事件件。代表表處理器器pi的一個計計算步驟驟。其中中，pi的轉換函函數被用用于當前前可訪問問狀態del((i,j,m))——傳遞事件件，表示示msgm從從pi傳送到pj執行：系統在時時間上的的行為被被模型化化為一個個執行。。它是一個個由配置置和事件件交錯的的序列。。該序列列須滿足足各種條條件，主主要分為為兩類：：14§2.1.1系統統①Safety條條件：(安全性)表示某個個性質在在每次執執行中每每個可到到達的配配置里都都必須成成立在序列的的每個有有限前綴綴里必須須成立的的條件例如：““在leader選舉中，，除了pmax外，沒有有哪個結結點宣稱稱自己是是leader””非形式地地：安全全性條件件陳述了了“尚未未發生壞壞的情況況”““壞事從從不發生生”15§2.1.1系統統②liveness條件件：(活躍性)表示某個個性質在在每次執執行中的的某些可可達配置置里必須須成立。。必須成立立一定次次數的條條件(可能是無無數次)例如：條條件：““p1最終須終終止”，，要求p1的終止至至少發生生一次；；“leader選舉，pmax最終宣布布自己是是leader””非形式地地，一個個活躍條條件陳述述：“最最終某個個好的情情況發生生”對特定系系統，滿滿足所有有要求的的安全性性條件的的序列稱稱為一個個執行;若一個執執行也滿滿足所有有要求的的活躍性性條件，，則稱為為容許(合法的)(admissible))執行16§2.1.1系統統2.異步步系統異步：msg傳傳遞的時時間和一一個處理理器的兩兩個相繼繼步驟之之間的時時間無固固定上界界例如，Internet中，，email雖雖然常常常是幾秒秒種到達達，但也也可能要要數天到到達。當當然msg延遲遲有上界界，但它它可能很很大，且且隨時間間而改變變。因此異步步算法設設計時，，須使之之獨立于于特殊的的計時參參數，不不能依賴賴于該上上界。執行片斷斷一個異步步msg傳遞系系統的一一個執行行片斷α是一個有有限或無無限的序序列：C0,Φ1,C1,Φ2,C2,Φ3,…,,((C0不一定是是初始配配置)這里Ck是一個配配置，Φk是一個事事件。若若α是有限的的，則它它須結束束于某個個配置，，且須滿滿足下述述條件：：17§2.1.1系統統若Φk=del(i,,j,m)，則m必必是Ck-1里的outbufi[l]的一個元元素，這這里l是pi的信道{{pi,pj}的標號號從Ck-1到Ck的唯一變變化是將將m從Ck-1里的outbufi[l]中刪去，，并將其其加入到到Ck里的inbufj[h]中，h是是pj的信道{{pi,pj}的標號號。即：傳遞遞事件將將msg從發送送者的輸輸出緩沖沖區移至至接收者者的輸入入緩沖區區。若Φk=comp(i)，則從Ck-1到Ck的變化是是①改變狀態態：轉換換函數在在pi的可訪問問狀態((在配置置Ck-1里)上進進行操作作，清空空inbufi[l]，(1≤l≤r)②發送msg：將將轉換函函數指定定的消息息集合加加到Ck里的變量量outbufi上。(Note:發送送send，傳傳遞delivery之區別別)即：pi以當前狀狀態(在在Ck-1中)為基基礎按轉轉換函數數改變狀狀態并發發出msg。18§2.1.1系統統執行：一個執行行是一個個執行片片斷C0,Φ1,C1,Φ2,…,,這里里C0是一個初初始配置置。調度：一個調度度(或調調度片段段)總是是和執行行(或執執行片斷斷)聯系系在一起起的，它它是執行行中的事事件序列列：Φ1,Φ2,…。。并非每個個事件序序列都是是調度。。例如，，del(1,,2,m)不是是調度，，因為此此事件之之前，p1沒有步驟驟發送((send)m。若局部程程序是確確定的，，則執行行(或執執行片斷斷)就由由初始配配置C0和調度((或調度度片斷))σ唯一確定定，可表表示為exec(C0,σ)。19§2.1.1系統統容許執行行：(滿足活活躍性條條件)異步系統統中，若若某個處處理器有有無限個個計算事事件，每每個發送送的msg都最最終被傳傳遞，則則執行稱稱為容許許的。Note:無限個計計算事件件是指處處理器沒沒有出錯錯，但它不不蘊含處處理器的的局部程程序必須須包括一一個無限限循環非形式地地說：一個算法法終止是是指在某某點后轉轉換函數數不改變變處理器器的狀態態。容許的調調度：若它是一一個容許許執行的的調度。。20§2.1.1系統統3.同步步系統在同步模模型中，，處理器器按鎖步步驟(lock-step))執行：：執行被劃劃分為輪輪，每輪輪里，①每個處理理器能夠夠發送一一個msg到每每個鄰居居，這些些msg被傳遞遞。②每個處理理器一接接到msg就進進行計算算。雖然特殊殊的分布布系統里里一般達達不到，，但這種種模型對對于設計計算法非非常方便便，因為為無需和和更多的的不確定定性打交交道。當當按此模模型設計計算法后后，能夠夠很容易易模擬得得到異步步算法。。輪：在同步系系統中，，配置和和事件序序列可以以劃分成成不相交交的輪，，每輪由由一個傳傳遞事件件(將outbuf的的消息傳傳送到信信道上使使outbuf變空))，后跟跟一個計計算事件件(處理理所有傳傳遞的msg))組成。。21§2.1.1系統統容許的執執行：指無限的的執行。。因為輪的的結構，，所以每個處理理器執行行無限數數目的計計算步，，每個被發發送的msg最最終被傳傳遞同步與異異步系統統的區別別在一個無無錯的同同步系統統中，一一個算法法的執行行只取決決于初始始配置但在一個個異步系系統中，，對于相相同的初初始配置置及無錯錯假定，，因為處處理器步步驟間隔隔及消息息延遲均均不確定定，故同同一算法法可能有有不同的的執行。。22§2.1.2復雜雜性度量量分布式算算法的性性能：msg個個數和時時間。最壞性能能、期望望性能終止：假定每個個處理器器的狀態態集包括括終止狀狀態子集集，每個個的pi的轉換函函數對終終止狀態態只能映映射到終終止狀態態當所有處處理機均處于終終止狀態態且沒有有msg在傳輸輸時，稱系統統(算法法)已終終止。算法的msg復復雜性((最壞情情況)：：算法在所所有容許許的執行行上發送送msg總數的的最大值值(同步步和異步步系統))23§2.1.2復雜雜性度量量時間復雜雜度①同步系統統：最大大輪數，，即算法法的任何何容許執執行直到到終止的的最大輪輪數。②異步系統統：假定定任何執執行里的的msg延遲至至多是1個單位位的時間間，然后后計算直直到終止止的運行行時間計時執行行(timedexecution)指：每個事件件關聯一一個非負負實數，表示事事件發生生的時間間。時間間起始于于零，且且須是非非遞減的的。但對對每個單個個的處理理器而言言是嚴格格增的。若執行是是無限的的，則執執行的時時間是無無界的。。因此執執行中的的事件可可根據其其發生時時間來排排序不在同一一處理器器上的多多個事件件可以同同時發生生，在任任何有限限時間之之前只有有有限數數目的事事件發生生。24§2.1.2復雜雜性度量量消息的延延遲發送msg的計計算事件件和處理理該msg的計計算事件件之間所所逝去的的時間它主要由由msg在發送送者的outbuf中中的等待待時間和和在接收收者的inbuf中的的等待時時間所構構成。異步算法法的時間間復雜性性異步算法法的時間間復雜性性是所有有計時容容許執行行中直到到終止的的最大時時間，其其中每個個msg延時至至多為1。25§2.1.3偽代代碼約定定在形式模模型中，，一個算算法將根根據狀態態轉換來來描述。。但實際際上很少少這樣做做，因為為這樣做做難于理理解。實際描述述算法有有兩種方方法：①敘述性：：對于簡簡單問題題②偽碼形式式：對于于復雜問問題26§2.1.3偽代代碼約定定異步算法法：對每個處處理器，，用中斷驅動動來描述異異步算法法。在形式模模型中，，每個計計算事件件1次處處理所有有輸入緩緩沖區中中的msgs。。而在算算法中，，一般須須描述每每個msg是如如何逐個個處理的的異步算法法也可在在同步系系統中工工作，因因為同步步系統是是異步系系統的一一個特例例。一個計算算事件中中的局部部計算的的描述類類似于順順序算法法的偽代代碼描述述。同步算法法：逐輪描述述偽代碼約約定：—在pi的局部變變量中，，無須用用i做下下標，但但在討論論和證明明中，加加上下標標i以示示區別。。—“///”后跟跟注釋27§2.2生生成樹上上的廣播播和匯集集信息收集集及分發發是許多多分布式式算法的的基礎。。故通過過介紹這這兩個算算法來說說明模型型、偽碼碼、正確確性證明明及復雜雜性度量量等概念念。§2.2.1廣播播(Broadcast)假定網絡絡的生成成樹已給給定。某某處理器器pr希望將消消息M發發送至其其余處理理器。假定生成成樹的根為pr，每個處處理器有有一個信信道連接接其雙親親(pr除外)，，有若干干個信道道連接其其孩子。。28§2.2.1廣播播根pr發送M給給所有孩孩子。((a)當某結點點收到父父結點的的M時，，發送M到自己己的所有有孩子((b)。。29§2.2.1廣播播1.偽碼碼算法Alg2.1Broadcastpr: ///發動者者。假設設初始化化時M已已在傳輸輸狀態1.uponreceivingnomsg:: ///pr發發送M后后執行終終止2.terminate;;///將terminated置為true。pi(i≠r,0≤≤i≤≤n--1)::3.uponreceivingMfromparent:4.sendMtoallchildren;5.terminate;2.用狀狀態轉換換來分析析算法每個處理理器pi包含狀態態—變量parenti：表示處處理器pi雙親結點點的標號號或為nil((若i==r)—變量childreni：pi的孩子結結點標號號的集合合—布爾變變量terminatedi：表示pi是否處于于終止狀狀態30§2.2.1廣播播初始狀態態parent和和children的的值是形形成生成成樹時確確定的所有terminated的的值均為為假outbufr[j]],j∈childrenr持有消息息M，注注意j不不是信道道標號，，而是r的鄰居居號。（（任何系系統中，，均假定定各節點點標號互互不相等等）所有其他他結點的的outbuf變量均均為空。。comp(i))的結果果若對于某某個k，，M在inbufi[k]里里，則M被放到到outbufi[j]]里，，j∈childreni31§2.2.1廣播播pi進入終止止狀態將terminatedi置為true；；若i==r且terminatedr為false，，則terminatedr立即置為為true，否否則空操操作。該算法對對同步及及異步系系統均正正確，且且在兩模模型中，，msg和時間間復雜度度相同。。Msg復復雜度無論在同同步還是是異步模模型中，，msgM在在生成樹樹的每條條邊上恰恰好發送送一次。。因此，msg復復雜性為為n-1。32§2.2.1廣播播時間復雜雜性：①同步模型型：時間由輪輪來度量量。Lemma2..1在同步模模型中，，在廣播播算法的的每個容容許執行行里，樹樹中每個個距離pr為t的處處理器在在第t輪輪里接收收消息M。pf：對距離t使用歸歸納法。。歸納基礎礎：t=1，pr的每個孩孩子在第第1輪里里接收來來自于pr的消息M歸納假設設：假設樹樹上每個個距pr為t-1≥1的的處理器器在第t-1輪輪里已收收到M。。歸納步驟驟：設pi到pr距離為t，設pj是pi的雙親，，因pj到pr的距離為為t-1，由歸歸納假設設，在第第t-1輪pj收到M。。由算法法描述知知，在第第t輪里里pi收到來自自于pj的消息MTh2..2當生成樹樹高度為為d時，，存在一一個消息息復雜度度為n--1，時時間復雜雜度為d的同步步廣播算算法33§2.2.1廣播播②異步模型Lemma2..3在異步模模型的廣廣播算法法的每個個容許執執行里，，樹中每每個距離離pr為t的處處理器至至多在時時刻t接接收消息息M。

pf：對距離t做歸納納。對t=1，初始始時，M處在從從pr到所有距距離為1的處理理器pi的傳輸之之中，由由異步模模型的時時間復雜雜性定義義知，pi至多在時時刻1收收到M。。pi∈{距pr為t的處處理器}}，設pj是pi的雙親，，則pj與pr的距離為為t-1，由歸歸納假設設知，pj至多在時時刻t--1收到到M，由由算法描描述知，，pj發送給pi的M至多多在t時時刻到達達。

Th2..4同Th2.234§2.2.2convergecast(匯匯集，斂斂播)與廣播問問題相反反，匯集集是從所所有結點點收集信信息至根根。為簡簡單起見見，先考考慮一個個特殊的的變種問問題：假定每個個pi開始時有有一初值值xi，我們希希望將這這些值中中最大者者發送至至根pr。35§2.2.2convergecast(匯匯集，斂斂播)算法

每個葉子子結點pi發送xi至雙親。。//啟啟動者對每個非非葉結點點pj，設pj有k個孩孩子pi1,…,pik，pj等待k個個孩子的的msgvi1,vi2,…,vik，當pj收到所有有孩子的的msg之后將將vj=max{xj,vi1,…,vik}發送到到pj的雙親。。換言之：：葉子先啟啟動，每每個處理理器pi計算以自自己為根根的子樹樹里的最最大值vi，將vi發送給pi的雙親。。復雜性Th2..5當生成樹樹高為d時，存存在一個個異步的的斂播方方法，其其msg復雜性性為n--1，時時間復雜雜度為d。(與與Th2.2相相同)廣播和斂斂播算法法用途：：初始化某某一信息息請求((廣播發發布)，，然后用用斂播響響應信息息至根。。36§2.3構造生成成樹上節算法法均假設設通信網網的生成成樹已知知。本節節介紹生生成樹的的構造問問題。1.Flooding算法((淹沒))算法

設pr是特殊處處理器。。從pr開始，發發送M到到其所有有鄰居。。當pi第1次收收到消息息M（不不妨設此此msg來自于于鄰居pj）時，pi發送M到到除pj外的所有有鄰居。。37§2.3構造生成成樹msg復復雜性因為每個個結點在在任一信信道上發發送M不不會多于于1次，，所以每每個信道道上M至至多被發發送兩次次(使用用該信道道的每個個處理器器各1次次)。在最壞情情況下：：M除第第1次接接收的那那些信道道外，所所有其他他信道上上M被傳傳送2次次。因此此，有可可能要發發送2m-(n-1))個msgs。。這里m是系統統中信道道總數，，它可能能多達n(n--1)//2。時間復雜雜性：O(D)) D——網直徑徑2.構造造生成樹樹對于flooding稍事修修改即可可得到求求生成樹樹的方法法。38§2.3構造生成成樹①基本思想想首先，pr發送M給給所有鄰鄰居，pr為根當pi從某鄰居居pj收到的M是第1個來自自鄰居的的msg時，pj是pi的雙親；；若pi首次收到到的M同同時來自自多個鄰鄰居，則則用一個個comp事件件處理自自上一comp事件以以來的所有已收收到的msgs，故故此時，，pi可在這些些鄰居中中任選一個鄰居居pj做雙親。。當pi確定雙親親是pj時，發送送<parent>給給pj，并向此此后收到到發來M的處理理器發送送<reject>msg39§2.3構造生成成樹①基本思想想因為pi收到pj的M是第第1個M，就不不可能已已收到其其他結點點的M，，當然可可能同時時收到((說明pi與這些鄰鄰居間不不是父子子關系，，或說它它們不是是生成樹樹中的邊邊)；同同時pi將M轉發發給其余余鄰居，，這些鄰鄰居尚未發M給pi，或雖然然已發M給pi，但pi尚未收到到。pi向那些尚尚未發M給pi(或已發發M但尚尚未到達達pi)的鄰居居轉發M之后，，等待這這些鄰居居發回響響應msg：<<parent>或<<reject>。那那些回應應<parent>的的鄰居是是pi的孩子。。當pi發出M的的所有接接收者均均已回應應(<parent>>或<reject>>)，則則pi終止。將將parent和children邊保留留即為生生成樹。。40§2.3構造生成成樹②圖示pi若認為pj是其雙親親，則pi向pr發出M，，而pr仍會向pi發reject，但因因為此前前pr向pi發出過M，故pi收到M時時仍會向向pr發reject。(可可以改進進？)41§2.3構造生成成樹③算法：：Alg2.2構構造生生成樹（（codeforpi0≤i≤≤n-1）初值：parent==nil；集合合children和和other均均為φuponreceivingnomessage:ifi=randparent=nilthen{{///根尚尚未發送送MsendMtoallneighbors;parent::=i;;}///根的的雙親置置為自己己uponreceivingMfromneighborpj:ifparent==nilthen{{///pi此前未收收到過M，M是是pi收到的第第1個msgparent::=j;;send<parent>>topj;///pj是pi的雙親sendMtoallneighborsexceptpj;}else///pj不可能是是pi的雙親，，pi收到的M不是第第1個msgsend<reject>topj;uponreceiving<<parent>fromneighborpj:children:==children∪∪{j};;///pj是pi的孩子，，將j加加入孩子子集ifchildren∪other包包含了除除parent外的所所有鄰居居thenterminate;uponreceiving<<reject>fromneighborpj:other:==other∪∪{j};;///將j加入other，通通過非樹樹邊發送送的msg。ifchildren∪other包含含了除pi的雙親外外的所有有鄰居thenterminate;;42§2.3構造生成成樹④分析Lemma2..6在異步模模型的每每個容許許執行中中，算法法2.2構造一一棵根為為pr的生成樹樹。(正正確性))Pf：算算法代碼碼告訴我我們兩個個重要事事實一旦處理理器設置置了parent變量量，它絕絕不改變變，即它它只有一一個雙親親處理器的的孩子集集合決不不會減小小。因此，最最終由parent和和children確確定的圖圖結構G是靜止止的，且且parent和children變量在在不同結結點上是是一致的的，即若若pj是pi的孩子，，則pi是pj的雙親。。下述證明明結果圖圖G是根根為pr的有向生生成樹。。43§2.3構造生成成樹為何從根根能到達達每一結結點？((連通))反證：假設某某結點在在G中從從pr不可達，，因網絡絡是連通通的，若若存在兩兩個相鄰鄰的結點點pi和pj使得pj在G中是是從pr可達的((以下簡簡稱pj可達)，，但pi不可達。。因為G里一結結點從pr可達當且且僅當它它曾設置置過自己己的parent變量量(Ex2.4證證明)，，所以pi的parent變量在在整個執執行中仍仍為nil，而而pj在某點上上已設置置過自己己的parent變量量，于是是pj發送M到到pi(line9))，因該該執行是是容許的的，此msg必必定最終終被pi接收，使使pi將自己的的parent變量設設置為j。矛盾盾！44§2.3構造生成成樹為何無環環？(無無環)假設有一一環，pi1,…pikpi1，若pi是pj的孩子，，則pi在pj第1次收收到M之之后第1次收到到M。因因每個處處理器在在該環上上是下一一處理器器的雙親親，這就就意味著著pi1在pi1第1次接接收M之之前第1次接收收M。矛矛盾！復雜性顯然，此此方法與與淹沒算算法相比比，增加加了msg復雜雜性，但但只是一一個常數數因子。。在異步步通信模模型里，，易看到到在時刻刻t，消消息M到到達所有有與pr距離小于于等于t的結點點。因此此有：Th2..7對于具有有m條邊邊和直徑徑D的網網絡，給給定一特特殊結點點，存在在一個msg復復雜性為為O(m)，時時間復雜雜性為O(D))的異步步算法找找到該網網絡的一一棵生成成樹。45§2.3構造生成成樹Alg2.2在在同步模模型下仍仍可工作作。其分分析類似似于異步步情形。。然而，，與異步步不同的的是，它它所構造造的生成成樹一定定是一棵棵廣度優優先搜索索(BFS)樹樹。Lemma2..8在同步模模型下，，Alg2.2的每次次容許執執行均構構造一棵棵根為pr的BFS樹。Pf：對輪t進進行歸納納。即要證證明：在在第t輪輪開始時時刻①根據parent變量量構造的的圖G是是一棵包包括所有有與pr距離至多多為t--1結點點的BFS樹；；②而傳輸中中的消息息M僅來來自于與與pr距離恰為為t-1的結點點。由此構造造的樹是是一棵根根為pr的BFS46§2.3構造生成成樹當t=1時，所所有parent初值值為nil，M從pr傳出。假設引理理對第t-1≥≥1輪為為真，在在該輪里里，從距距離t-2的結點點傳出的的M被接接收，任任何接收收M的結結點與pr的距離不不超過t-1((恰為t-1或或更短))，那些些parent值非空空的接收收結點顯顯然與pr的距離不不超過t-2，，他們既既不改變變parent的值也也不轉發發M；而而與pr距離為t-1的的結點在在t-1輪里收收到M，，因為它它們的parent為為nil，故將將其置為為合適的的雙親并并轉發M。距離離pr大于t--1的結結點不會會收到M，因此此也不會會轉發M。因此此有如下下定理：：Th2..9對于具有有m條邊邊直徑為為D的網網絡，給給定一個個特殊結結點，存存在一個個同步算算法在msg復復雜性為為O(m)，時時間復雜雜性為O(D))內找到到一棵BFS樹樹。47§2.3構造生成成樹異步系統統里，Alg2.2能能構造BFS樹樹？例如，考考慮5個個頂點的的完全連連通圖

P0為根，假假定M消消息按P0到p1，P1到P2，P2到P3，P3到P4的次序快快速傳播播，而M在其它它路徑上上傳播較較慢。結結果生成成樹是從從P0到P4的鏈，它它不是BFS樹樹雖然此圖圖直徑D=1，，生成樹樹的高度度d=4，但是是算法的的運行時時間仍然然為O((D)而而不是O(d))。理解：P0到P4的M在1個時間間內到達達，即P0->P1->P2->P3->P4的時間之之和不超超過1。48§2.3構造生成成樹信息的請請求和收收集將算法2.2((求生成成樹)和和匯集算算法組合合即可完完成。組組合算法法的時間間復雜性性在同步步和異步步模型中中不同,,設網是是完全圖求生成樹樹算法：同步和和異步均均為消消息復雜雜性O((m)時間復雜雜性O((D)匯集算法法：同步和和異步均均有msgn--1timed///生生成樹高高組合算法法①同步：組組合算法法的msg復雜雜性O((m+n)；BFS樹樹中，d=1，，d≤≤D，故故時間復復雜性O(D++d)==O(D))=O(1)。②異步：組組合算法法的msg復雜雜性O((m+n)；生生成樹高高d=n--1，所所以時間間復雜性性O(D+d))=O(d))=O(n)。1-time復復雜性的的組合算算法T((n)==O(D)。

49§2.4構造DFS生成樹(指定根)構造DFS樹時時每次加加一個結結點，而而不像Alg2.2那那樣，試試圖在樹樹上同時時增加同同一層的的所有結結點。Alg2.3構構造DFS生生成樹，，為Pr為根CodeforprocessorPi,0≤≤i≤≤n--1varparent:initnil;;children:initφ;unexplored:initalltheneighborsofPi//未訪訪問過的的鄰居集集1:uponreceivingnomsg::2:if((i=r)and((parent=nil))then{{///當當Pi為根且未未發送M時3:parent::=i;////將parent置為為自身的的標號4:Pj∈unexplored;5:將將Pj從unexplored中刪刪去;///若若Pr是孤立結結點,4-6應應稍作修修改6:sendMtoPj;}//endif50§2.4構造DFS生成樹(指定根)7:uponreceivingMfromneighborPj:8:ifparent=nilthen{////Pi此前未收收到M9:parent::=j;///Pj是Pi的父親10:從從unexplored中中刪Pj11:ifunexplored≠≠φthen{12:Pk∈unexplored;;13:將將Pk從unexplored中刪刪去；14:sendMtoPk;15:}}elsesend<<parent>toparent;//當Pi的鄰居均均已訪問問過，返返回到父父親16:}}elsesend<reject>>toPj;///當Pi已訪問過過時51§2.4構造DFS生成樹(指定根)17:uponreceiving<<parent>or<<reject>fromneighborPj:18:ifreceived<parent>>thenaddjtochildren;;//Pj是Pi的孩子19:ifunexplored==φthen{////Pi的鄰居均均已訪問問20:ifparent≠≠ithensend<<parent>toparent;;//Pi非根，返返回至雙雙親21:terminate;;///以Pi為根的DFS子子樹已構構造好！！22:}}else{{///選擇擇Pi的未訪問問過的鄰鄰居訪問問之23:Pk∈unexplored;;24:將將Pk從unexplored中刪刪去；25:sendMtoPk;}52§2.4構造DFS生成樹(指定根)引理2..10在異步模模型里的的每個容容許執行行，Alg2..3構造造一棵以以Pr為根的DFS樹樹。證明留作作練習。。Th2..11對于一個個具有m條邊，，n個結結點的網網絡，以以及給定定的特殊殊頂點，，存在一一個時間間復雜性性和消息息復雜性性均為O(m))的異步步算法找找到一棵棵DFS樹。Pf：每每個結點點在其鄰鄰接邊上上至多發發送M一一次，每每個結點點至多生生成一個個msg(<reject>>或<parent>>)作為為對每個個鄰接邊邊上收到到的M的的響應。。因此Alg2.3至至多發送送4m個個消息((其實大大部分沒沒有4倍倍)，即即算法的的msg復雜性性為O((m)。。時間復雜雜性證明明留作練練習。如何改進進使msg的復復雜性不不是4m。注意：上上述算法法msg復雜性性較好，，但時間間復雜性性太差。。可降至至O(n)。53§2.5不指定根根時構造造DFS生成樹算法2..2和2.3構構造連通通網絡的的生成樹樹時，必必需存在在一個特特殊的結結點作為為啟動者者(Leader)。。當這樣樣的特殊殊結點不不存在時時，如何何構造網網絡的一一棵生成成樹？但但本節算算法須假假定：各結點的的標識符符唯一，，不妨設設是自然然數，§3.2仍需此假假定。基本思想想每個結點點均可自自發喚醒醒，試圖圖構造一一棵以自自己為根根的DFS生成成樹。若若兩棵DFS樹樹試圖鏈鏈接同一一節點((未必同同時)時時，該節節點將加加入根的的id較較大的DFS樹樹。為了實現現上述思思想，每每個結點點設置一一個leader變量量，其初初值為0，當Pi喚醒自己己時，leaderi=idi。54§2.5不指定根根時構造造DFS生成樹當一結點點自發喚喚醒時，，它將自自己的id(leader))發送給給某一鄰鄰居。當一結點點Pi收到來自自鄰居Pj的標識符符y時，，Pi比較y和和leaderi：①若y>leaderi，則y可可能是具具有最大大標識符符結點的的DFS子樹的的標記。。因此，，將leaderi置為y，，并令Pj是Pi的雙親。。從Pi開始繼續續生成標標記為y的DFS樹。。Note：要要修改原原Pi所在的DFS子子樹中所所有結點點的leader。55§2.5不指定根根時構造造DFS生成樹若y<leaderi，則標記記為y的的DFS樹中最最大id(y))小于目目前所看看到的最最大標識識符。此此時無須須發送msg，，停止構構造標記記為y的的DFS。等待待最終某某個更大大的id的leader消息息到達標標記為y的樹中中結點時時，再將將該節點點連接到到樹中。。(至少少標記為為leaderi的msg會到達達標記為為y的樹樹)若y=leaderi，則Pi已屬于標標記y的的DFS樹中。。

56§2.5不指定根根時構造造DFS生成樹算法Alg2.4構造生成成樹，不不指定根根CodeforProcessorPi0≤i≤≤n-1Varparent:initnil;leader:: init0;children:intφ;unexplored:initallneighborsofPi;;1:uponreceivingnomsg::///wakeupspontaneously2:ifparent=nilthen{{//若非非空，則則Pi在某子樹樹上，則則Pi失去競選選機會3:leader::=id;parent::=i;///試圖以以自己為為根構造造樹4:Pj∈unexplored;5:將將Pj從unexplored中刪刪去；6：send<<leader>topj;}57§2.5不指定根根時構造造DFS生成樹想像：有有m個人人競選領領袖，id是他他自身的的素質分分，不想想競爭人人的id不參與與比較。。競爭規則則：將自自己的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中刪刪去；58§2.5不指定根根時構造造DFS生成樹14:send<<leader>toPK;15:}}elsesend<parent>>toparent;16:}}elseifleader=new--idthensend<already>toPj;//表示示自己已已經傳出出過錄像像帶，無無需重復復發//已在在同一樹樹中。若若leader>new-id，則則new-id所在DFS停停止//構造造//以前前收到的的競選者者優于new--id，，不傳送送，使之之停止傳傳播。17:uponreceiving<<parent>or<<already>>fromneighborPj:18:ifreceived<parent>>thenaddjtochildren;;19:ifunexplored==φthen{////無尚未未訪問的的鄰居20:ifparent≠≠ithensend<<parent>toparent;///返返回21:elseterminatesasrootoftheDFStree;;///根終終止22:}}else{////有尚未未訪問的的鄰居59§2.5不指定根根時構造造DFS生成樹23:Pk∈unexplored;;24:將將Pk從unexplored中刪刪去；25:send<<leader>toPk;}分析：只有生成成樹的根根顯式地地終止，，其它結結點沒有有終止，，始終在在等待msg。。但可修修改此算算法，使使用Alg2..1從根根結點發發送終止止msg正確性該算法比比前面的的算法更更復雜，，這里只只給出粗粗略的證證明。設Pm是所有自自發喚醒醒結點中中標識符符最大者者，其標標識符為為idm。消息idm總是被傳傳播，而而一旦一一個結點點收到idm，則該節節點(Pm除外)上上所有msgs被忽略略。因為為消息idm的處理和和Alg2.3求DFS樹一一致，因因此產生生的parent和children變量量的設置置是正確確的。因因此有：：60§2.5不指定根根時構造造DFS生成樹Lemma2..12設Pm是所有自自發喚醒醒結點中中具有最最大標識識符的結結點。在在異步模模型的每每次容許許執行里里，算法法2.4構造根根為Pm的1棵DFS樹樹。Note：因為為在容許許執行中中，網絡絡里的所所有自發發喚醒結結點中最最大標識識符結點點最終會會自發啟啟動，故故建立的的DFS樹的根根是Pm可通過廣廣播算法法從Pm發出終止止msg，即使使不廣播播，所有有非Pm結點最終終也會因因為收到到Pm的標識符符而停止止。因此此，不可可能構造造一棵根根不是Pm的生成樹樹。Lemma2..13在異步模模型的每每個容許許執行里里，只有有一個處處理器終終止作為為一生成成樹的根根。61§2.5不指定根根時構造造DFS生成樹復雜性簡單地分分析，最最壞情況況下，每每個處理理器均試試圖以自自己為根根構造一一棵DFS樹。。因此，，Alg2.4的msg復雜雜性至多多是Alg2..3的n倍：O(m**n)時間復雜雜性類似似于Alg2..3的msg復復雜性O(m))。62§2.5不指定根根時構造造DFS生成樹Ex2.1分分析在在同步和和異步模模型下，，convergecast算法的的時間復復雜性。。2.2證證明在在引理2.6中中，一個個處理器器在圖G中是從從Pr可達的，，當且僅僅當它的的parent變量曾曾被賦過過值2.3證證明Alg2.3構構造一棵棵以Pr為根的DFS樹樹。2.4證證明Alg2.3的的時間復復雜性為為O(m)。2.5修修改Alg2.3獲獲得一新新算法，，使構造造DFS樹的時時間復雜雜性為O(n))。補充§2.6小小結63§2.6小結Introductiontodistributedalg分類：單源alg：一個啟啟動者。。又稱centralizedalg。。多源alg：任意進進程(結結點)子子集均可可是啟動動者，又又稱decentralizedalg啟動者((initiator)：自發地地執行局局部算法法，即由由一內部部事件激激發其執執行非啟動者者：由接收收一個msg((外部事事件)觸觸發其執執行局部部進程。。復雜性：：Msg復復雜性：msg總數目目Bit復復雜性：發送msg中中bit的總數數目，當當msg在發送送過程中中其長度度隨時間間增長時時64§2.6小結時間復雜雜性一個分布布式算法法的時間復雜雜性是滿足下下述兩個個假定的的一個計計算所耗耗費的最大時間間T1：一一個進程程在零時時間內可可計算任任何有限限數目的的事件T2：一一個msg的發發送和接接受之間間的時間間至多為為1個時時間單位位缺點:針對一一算法的的所有計計算，其其結果可可能是極極不可能能發生的的計算。。一個分布布式算法法的one--time復雜雜性是滿足下下述假定定的一個個計算的的最大時間間O1：同同T1O2：發發送和接接收一個個msg之間的的時間恰恰好是1個單位位時間缺點：某些計計算可能能被忽略略，而其其中可能能有極其其耗時的的計算65§2.6小結表面上，，1-time復雜性性至少等等于時間間復雜性性，因為為T2假假定下的的最壞時時間不會會高于O2假定定下的時時間。但但事實并并非如此此，而往往往O1和O2假定之之下的1-time復復雜性是是前一種種時間復復雜性的的一個下下界。例如：在在echo算法法里1--time復雜雜性是O(D))，時間間復雜性性是?(N)，，即使直直徑為1的網絡絡。

兩種復雜雜性的折折中：α-復雜雜性假定每個個msg延遲介介于α-1之間間(α≤1常數)對echo算算法α復雜性為為O(min((N,D/α))概率分析析：msg延遲服服從某種種概率分分布，由由此可獲獲得精確確的時間間復雜性性度量66§2.6小結基于msgchains的的分析任何計算算中最長長消息鏈鏈的長度度。鏈上msgs：：m1,m2,…mk序列中，，mi因果關系系領先于于mi+1。先驗知識識：鄰居的的id，，全局id等。。鏈路FIFO假定等等設想67Ch3..環上選舉舉leader問題在一組處處理器中中選出一一個特殊殊結點作作為leader用途簡化處理理器之間間的協作作；有助于達達到容錯錯和節省省資源。。例如，有有了一個個leader，就易易于實現現廣播算算法代表了一一類破對對稱問題題。例如，當當死鎖是是由于處處理器相相互環形形等待形形成時，，可使用用選舉算算法，找找到一個個leader并使之之從環上上刪去，，即可打打破死鎖鎖。68§3.1leader選舉問題題Leader選選舉有很很多變種種。我們們這里只只介紹最最一般的的一種。。其問題是是：每個處處理器最最終確定定自己是是否是一一個leader，但但只有一一個處理理器確定定自己是是leader，而其其他處理理器確定定自己是是non-leader。一個算法法解決了了leader選舉問問題需滿滿足(根根據形式式化模型型)：終止狀態態被劃分分為兩類類：選中中和未選選中狀態態。一旦旦一個處處理器進進入選中中(或未未選中))狀態，，則該處處理器上上的轉換換函數將將只會將將其變為為相同的的狀態；；在每個容容許執行行里，只只有一個個處理器器進入選選中狀態態，其余余處理器器進入非非選中((non-selected)狀態態。本章只討討論系統統的拓撲撲結構是是環的情情況。69§3.1leader選舉問題題模型對每個i，0≤≤i<n，Pi到Pi+1的邊標號號為1，，稱為左左(順時時針)Pi到Pi-1的邊標號號為2，，稱為右右(逆時時針)這里的標標號加減減均是modn的70§3.2匿名環匿名算法法：若環中中處理器器沒有唯唯一的標標識符，，則環選選舉算法法是匿名名的。在在這種算算法里，，m