分布式算法課件

1、1第二部分 分布式算法汪煬中國(guó)科學(xué)技術(shù)大學(xué)計(jì)算機(jī)系 國(guó)家高性能計(jì)算中心（合肥）2Ch.1 導(dǎo)論1.1 分布式系統(tǒng)Def：一個(gè)分布式系統(tǒng)是一個(gè)能彼此通信的單個(gè)計(jì)算裝置的集合（計(jì)算單元：硬處理器；軟進(jìn)程） 包括：緊耦合系統(tǒng)-如共享內(nèi)存多處理機(jī) 松散系統(tǒng)-cow、Internet與并行處理的分別(具有更高程度的不確定性和行為的獨(dú)立性)并行處理的目標(biāo)是使用所有處理器來(lái)執(zhí)行一個(gè)大任務(wù)而分布式系統(tǒng)中，每個(gè)處理器一般都有自己獨(dú)立的任務(wù)，但由于各種原因（為共享資源，可用性和容錯(cuò)等），處理機(jī)之間需要協(xié)調(diào)彼此的動(dòng)作。分布式系統(tǒng)無(wú)處不在，其作用是： 共享資源改善性能：并行地解決問(wèn)題改善可用性：提高可靠性，以防某些成

2、分發(fā)生故障31.1 分布式系統(tǒng)分布式系統(tǒng)軟件實(shí)例簡(jiǎn)介ElcomSoft Distributed Password Recovery 是一款俄羅斯安全公司出品的分布式密碼暴力破解工具能夠利用Nvidia顯卡使WPA和WPA2無(wú)線密鑰破解速度提高100倍還允許數(shù)千臺(tái)計(jì)算機(jī)聯(lián)網(wǎng)進(jìn)行分布式并行計(jì)算 41.1 分布式系統(tǒng)系統(tǒng)適用范圍ElcomSoft 的密碼恢復(fù)軟件主要是面向Office，包括（Word, Excel, Access, Outlook, Outlook Express, VBA, PowerPoint and Visio)其他的面向微軟的產(chǎn)品有（Project, Backup, Mail

3、, Schedule+), archive products (including ZIP, RAR, ACE and ARJ files)等 61.1 分布式系統(tǒng)演示主界面71.1 分布式系統(tǒng)最終破解效果DOC加密的文檔，8位數(shù)字型密碼小于1分鐘即可成功解密 91.1 分布式系統(tǒng)NASA SETI尋找外星人計(jì)劃 SETI (搜尋外星智慧) 是一個(gè)尋找地球外智慧生命的科學(xué)性實(shí)驗(yàn)計(jì)劃，使用射電望遠(yuǎn)鏡來(lái)監(jiān)聽太空中的窄頻無(wú)線電訊號(hào)。假設(shè)這些訊號(hào)中有些不是自然產(chǎn)生的，那么只要我們偵測(cè)到這些訊號(hào)就可以證明外星科技的存在。 射電望遠(yuǎn)鏡訊號(hào)主要由噪聲 (來(lái)自天體的發(fā)射源與接收者的電子干擾) 與像電視轉(zhuǎn)播站、

4、雷達(dá)和衛(wèi)星等等的人工訊號(hào)所組成。現(xiàn)代的 Radio SETI 計(jì)劃會(huì)分析這些數(shù)字信息。有更強(qiáng)大的運(yùn)算能力就可以搜尋更廣泛的頻率范圍以及提高靈敏度。因此，Radio SETI 計(jì)劃對(duì)運(yùn)算能力的需求是永無(wú)止盡的。 原來(lái)的 SETI 項(xiàng)目曾經(jīng)使用望遠(yuǎn)鏡旁專用的超級(jí)計(jì)算機(jī)來(lái)進(jìn)行大量的數(shù)據(jù)分析。1995年，David Gedye 提議射電 SETI 使用由全球聯(lián)網(wǎng)的大量計(jì)算機(jī)所組成的虛擬超級(jí)計(jì)算機(jī)來(lái)進(jìn)行計(jì)算，并創(chuàng)建了 SETIhome 項(xiàng)目來(lái)實(shí)驗(yàn)這個(gè)想法。SETIhome 項(xiàng)目于1999年5月開始運(yùn)行。 101.1 分布式系統(tǒng)NASA SETI尋找外星人計(jì)劃 111.1 分布式系統(tǒng)分布式系統(tǒng)面臨的困難異

5、質(zhì)性：軟硬件環(huán)境異步性：事件發(fā)生的絕對(duì)、甚至相對(duì)時(shí)間不可能總是精確地知道局部性：每個(gè)計(jì)算實(shí)體只有全局情況的一個(gè)局部視圖故障：各計(jì)算實(shí)體會(huì)獨(dú)立地出故障，影響其他計(jì)算實(shí)體的工作。121.2 分布式計(jì)算的理論目標(biāo)：針對(duì)分布式系統(tǒng)完成類似于順序式計(jì)算中對(duì)算法的研究具體：對(duì)各種分布式情況發(fā)生的問(wèn)題進(jìn)行抽象，精確地陳述這些問(wèn)題，設(shè)計(jì)和分析有效算法解決這些問(wèn)題，證明這些算法的最優(yōu)性。計(jì)算模型：通信：計(jì)算實(shí)體間msg傳遞還是共享變量？哪些計(jì)時(shí)信息和行為是可用的？容許哪些錯(cuò)誤復(fù)雜性度量標(biāo)準(zhǔn)時(shí)間，空間通信成本：msg的個(gè)數(shù)，共享變量的大小及個(gè)數(shù)故障和非故障的數(shù)目131.2 分布式計(jì)算的理論否定結(jié)果、下界和不可能的

6、結(jié)果 常常要證明在一個(gè)特定的分布式系統(tǒng)中，某個(gè)特定問(wèn)題的不可解性。 就像NP-完全問(wèn)題一樣，表示我們不應(yīng)該總花精力去求解這些問(wèn)題。 當(dāng)然，可以改變規(guī)則，在一種較弱的情況下去求解問(wèn)題。我們側(cè)重研究：可計(jì)算性：?jiǎn)栴}是否可解？計(jì)算復(fù)雜性：求解問(wèn)題的代價(jià)是什么？141.3 理論和實(shí)際之關(guān)系主要的分布式系統(tǒng)的種類，分布式計(jì)算理論中常用的形式模型之間的關(guān)系種類支持多任務(wù)的OS：互斥，死鎖檢測(cè)和防止等技術(shù)在分布式系統(tǒng)中同樣存在。MIMD機(jī)器：緊耦合系統(tǒng)，它由分離的硬件運(yùn)行共同的軟件構(gòu)成。更松散的分布式系統(tǒng)：由網(wǎng)絡(luò)（局域、廣域等）連接起來(lái)的自治主機(jī)構(gòu)成特點(diǎn)是由分離的硬件運(yùn)行分離的軟件。實(shí)體間通過(guò)諸如TCP/I

7、P棧、CORBA或某些其它組件或中間件等接口互相作用。161.3 理論和實(shí)際之關(guān)系錯(cuò)誤的種類初始死進(jìn)程 指在局部算法中沒(méi)有執(zhí)行過(guò)一步。Crash failure崩潰錯(cuò)誤(損毀模型)指處理機(jī)沒(méi)有任何警告而在某點(diǎn)上停止操作。Byzantine failure拜占庭錯(cuò)誤一個(gè)出錯(cuò)可引起任意的動(dòng)作, 即執(zhí)行了與局部算法不一致的任意步。拜占庭錯(cuò)誤的進(jìn)程發(fā)送的消息可能包含任意內(nèi)容。17Ch.2 消息傳遞系統(tǒng)中的基本算法本章介紹無(wú)故障的msg傳遞系統(tǒng)，考慮兩個(gè)主要的計(jì)時(shí)模型：同步及異步。定義主要的復(fù)雜性度量、描述偽代碼約定，最后介紹幾個(gè)簡(jiǎn)單算法2.1 消息傳遞系統(tǒng)的形式化模型2.1.1 系統(tǒng)1.基本概念拓?fù)洌?/p>

8、無(wú)向圖 結(jié)點(diǎn)處理機(jī) 邊 雙向信道192.1.1 系統(tǒng)狀態(tài)（進(jìn)程的局部狀態(tài)） 由pi的變量，pi的msgs構(gòu)成。 pi的每個(gè)狀態(tài)由2r個(gè)msg集構(gòu)成：outbufil(1lr): pi經(jīng)第l條關(guān)聯(lián)的信道發(fā)送給鄰居，但尚未傳到鄰居的msg。inbufil(1lr): 在pi的第l條信道上已傳遞到pi，但尚未經(jīng)pi內(nèi)部計(jì)算步驟處理的msg。 模擬在信道上傳輸?shù)膍sgs 202.1.1 系統(tǒng)初始狀態(tài)：Qi包含一個(gè)特殊的初始狀態(tài)子集：每個(gè)inbufil必須為空，但outbufil未必為空。轉(zhuǎn)換函數(shù)(transition)：處理器pi的轉(zhuǎn)換函數(shù)(實(shí)際上是一個(gè)局部程序)輸入：pi可訪問(wèn)的狀態(tài)輸出：對(duì)每個(gè)信道

9、l ，至多產(chǎn)生一個(gè)msg輸出轉(zhuǎn)換函數(shù)使輸入緩沖區(qū)(1lr)清空。212.1.1 系統(tǒng)配置：配置是分布式系統(tǒng)在某點(diǎn)上整個(gè)算法的全局狀態(tài)向量=(q0, q1,qn-1), qi是pi的一個(gè)狀態(tài)一個(gè)配置里的outbuf變量的狀態(tài)表示在通信信道上傳輸?shù)男畔?，由del事件模擬傳輸一個(gè)初始的配置是向量=(q0, q1,qn-1), 其中每個(gè)qi是pi的初始狀態(tài)，即每個(gè)處理器處于初始狀態(tài)222.1.1 系統(tǒng)事件：系統(tǒng)里所發(fā)生的事情均被模型化為事件，對(duì)于msg傳遞系統(tǒng)，有兩種：comp(i)計(jì)算事件。代表處理器pi的一個(gè)計(jì)算步驟。其中，pi的轉(zhuǎn)換函數(shù)被用于當(dāng)前可訪問(wèn)狀態(tài)del(i,j,m)傳遞事件，表示msg

10、 m從pi傳送到pj執(zhí)行：系統(tǒng)在時(shí)間上的行為被模型化為一個(gè)執(zhí)行。它是一個(gè)由配置和事件交錯(cuò)的序列。該序列須滿足各種條件，主要分為兩類： 232.1.1 系統(tǒng) Safety條件： (安全性)表示某個(gè)性質(zhì)在每次執(zhí)行中每個(gè)可到達(dá)的配置里都必須成立在序列的每個(gè)有限前綴里必須成立的條件例如：“在leader選舉中，除了pmax外，沒(méi)有哪個(gè)結(jié)點(diǎn)宣稱自己是leader”非形式地：安全性條件陳述了“尚未發(fā)生壞的情況” “壞事從不發(fā)生”242.1.1 系統(tǒng) liveness條件： (活躍性)表示某個(gè)性質(zhì)在每次執(zhí)行中的某些可達(dá)配置里必須成立。必須成立一定次數(shù)的條件(可能是無(wú)數(shù)次) 例如：條件：“p1最終須終止”，要

11、求p1的終止至少發(fā)生一次；“l(fā)eader選舉， pmax最終宣布自己是leader”非形式地，一個(gè)活躍條件陳述：“最終某個(gè)好的情況發(fā)生”對(duì)特定系統(tǒng)，滿足所有要求的安全性條件的序列稱為一個(gè)執(zhí)行;若一個(gè)執(zhí)行也滿足所有要求的活躍性條件，則稱為容許(合法的)(admissible)執(zhí)行262.1.1 系統(tǒng)2.異步系統(tǒng)異步：msg傳遞的時(shí)間和一個(gè)處理器的兩個(gè)相繼步驟之間的時(shí)間無(wú)固定上界例如，Internet中，email雖然常常是幾秒種到達(dá)，但也可能要數(shù)天到達(dá)。當(dāng)然msg延遲有上界，但它可能很大，且隨時(shí)間而改變。因此異步算法設(shè)計(jì)時(shí)，須使之獨(dú)立于特殊的計(jì)時(shí)參數(shù)，不能依賴于該上界。執(zhí)行片斷一個(gè)異步msg傳遞

12、系統(tǒng)的一個(gè)執(zhí)行片斷是一個(gè)有限或無(wú)限的序列： C0, 1, C1, 2, C2, 3, , (C0不一定是初始配置)這里Ck是一個(gè)配置， k是一個(gè)事件。若是有限的，則它須結(jié)束于某個(gè)配置，且須滿足下述條件：272.1.1 系統(tǒng)若k =del(i,j,m)，則m必是Ck-1里的outbufil的一個(gè)元素，這里l是pi的信道pi,pj的標(biāo)號(hào)從Ck-1到Ck的唯一變化是將m從Ck-1里的outbufil中刪去，并將其加入到Ck里的inbufjh中，h是pj的信道pi,pj的標(biāo)號(hào)。即：傳遞事件將msg從發(fā)送者的輸出緩沖區(qū)移至接收者的輸入緩沖區(qū)。若k =comp(i)，則從Ck-1到Ck的變化是改變狀態(tài)：轉(zhuǎn)

13、換函數(shù)在pi的可訪問(wèn)狀態(tài)(在配置Ck-1里)上進(jìn)行操作，清空inbufil，(1lr)發(fā)送msg：將轉(zhuǎn)換函數(shù)指定的消息集合加到Ck里的變量outbufi上。(Note:發(fā)送send，傳遞delivery之區(qū)別)即： pi以當(dāng)前狀態(tài)(在Ck-1中)為基礎(chǔ)按轉(zhuǎn)換函數(shù)改變狀態(tài)并發(fā)出msg。292.1.1 系統(tǒng)容許執(zhí)行：(滿足活躍性條件)異步系統(tǒng)中，若某個(gè)處理器有無(wú)限個(gè)計(jì)算事件，每個(gè)發(fā)送的msg都最終被傳遞，則執(zhí)行稱為容許的。Note: 無(wú)限個(gè)計(jì)算事件是指處理器沒(méi)有出錯(cuò)，但它不蘊(yùn)含處理器的局部程序必須包括一個(gè)無(wú)限循環(huán)非形式地說(shuō)：一個(gè)算法終止是指在某點(diǎn)后轉(zhuǎn)換函數(shù)不改變處理器的狀態(tài)。容許的調(diào)度：若它是一個(gè)

14、容許執(zhí)行的調(diào)度。302.1.1 系統(tǒng)3.同步系統(tǒng)在同步模型中，處理器按鎖步驟(lock-step)執(zhí)行：執(zhí)行被劃分為輪，每輪里，每個(gè)處理器能夠發(fā)送一個(gè)msg到每個(gè)鄰居，這些msg被傳遞。每個(gè)處理器一接到msg就進(jìn)行計(jì)算。雖然特殊的分布系統(tǒng)里一般達(dá)不到，但這種模型對(duì)于設(shè)計(jì)算法非常方便，因?yàn)闊o(wú)需和更多的不確定性打交道。當(dāng)按此模型設(shè)計(jì)算法后，能夠很容易模擬得到異步算法。輪：在同步系統(tǒng)中，配置和事件序列可以劃分成不相交的輪，每輪由一個(gè)傳遞事件(將outbuf的消息傳送到信道上使outbuf變空)，后跟一個(gè)計(jì)算事件(處理所有傳遞的msg)組成。312.1.1 系統(tǒng)容許的執(zhí)行：指無(wú)限的執(zhí)行。因?yàn)檩喌慕Y(jié)構(gòu)，

15、所以每個(gè)處理器執(zhí)行無(wú)限數(shù)目的計(jì)算步，每個(gè)被發(fā)送的msg最終被傳遞同步與異步系統(tǒng)的區(qū)別在一個(gè)無(wú)錯(cuò)的同步系統(tǒng)中，一個(gè)算法的執(zhí)行只取決于初始配置但在一個(gè)異步系統(tǒng)中，對(duì)于相同的初始配置及無(wú)錯(cuò)假定，因?yàn)樘幚砥鞑襟E間隔及消息延遲均不確定，故同一算法可能有不同的執(zhí)行。322.1.2 復(fù)雜性度量分布式算法的性能：msg個(gè)數(shù)和時(shí)間。最壞性能、期望性能終止：假定每個(gè)處理器的狀態(tài)集包括終止?fàn)顟B(tài)子集，每個(gè)的pi的轉(zhuǎn)換函數(shù)對(duì)終止?fàn)顟B(tài)只能映射到終止?fàn)顟B(tài)當(dāng)所有處理機(jī)均處于終止?fàn)顟B(tài)且沒(méi)有msg在傳輸時(shí)，稱系統(tǒng)(算法)已終止。算法的msg復(fù)雜性(最壞情況)：算法在所有容許的執(zhí)行上發(fā)送msg總數(shù)的最大值(同步和異步系統(tǒng))332.

16、1.2 復(fù)雜性度量時(shí)間復(fù)雜度同步系統(tǒng)：最大輪數(shù)，即算法的任何容許執(zhí)行直到終止的最大輪數(shù)。異步系統(tǒng)：假定任何執(zhí)行里的msg延遲至多是1個(gè)單位的時(shí)間，然后計(jì)算直到終止的運(yùn)行時(shí)間計(jì)時(shí)執(zhí)行(timed execution)指：每個(gè)事件關(guān)聯(lián)一個(gè)非負(fù)實(shí)數(shù)，表示事件發(fā)生的時(shí)間。時(shí)間起始于零，且須是非遞減的。但對(duì)每個(gè)單個(gè)的處理器而言是嚴(yán)格增的。若執(zhí)行是無(wú)限的，則執(zhí)行的時(shí)間是無(wú)界的。因此執(zhí)行中的事件可根據(jù)其發(fā)生時(shí)間來(lái)排序不在同一處理器上的多個(gè)事件可以同時(shí)發(fā)生，在任何有限時(shí)間之前只有有限數(shù)目的事件發(fā)生。342.1.2 復(fù)雜性度量消息的延遲發(fā)送msg的計(jì)算事件和處理該msg的計(jì)算事件之間所逝去的時(shí)間它主要由msg在

17、發(fā)送者的outbuf中的等待時(shí)間和在接收者的inbuf中的等待時(shí)間所構(gòu)成。異步算法的時(shí)間復(fù)雜性異步算法的時(shí)間復(fù)雜性是所有計(jì)時(shí)容許執(zhí)行中直到終止的最大時(shí)間，其中每個(gè)msg延時(shí)至多為1。352.1.3 偽代碼約定在形式模型中，一個(gè)算法將根據(jù)狀態(tài)轉(zhuǎn)換來(lái)描述。但實(shí)際上很少這樣做，因?yàn)檫@樣做難于理解。 實(shí)際描述算法有兩種方法： 敘述性：對(duì)于簡(jiǎn)單問(wèn)題 偽碼形式：對(duì)于復(fù)雜問(wèn)題362.1.3 偽代碼約定異步算法：對(duì)每個(gè)處理器，用中斷驅(qū)動(dòng)來(lái)描述異步算法。在形式模型中，每個(gè)計(jì)算事件1次處理所有輸入緩沖區(qū)中的msgs。而在算法中，一般須描述每個(gè)msg是如何逐個(gè)處理的異步算法也可在同步系統(tǒng)中工作，因?yàn)橥较到y(tǒng)是異步系

18、統(tǒng)的一個(gè)特例。一個(gè)計(jì)算事件中的局部計(jì)算的描述類似于順序算法的偽代碼描述。同步算法：逐輪描述偽代碼約定：在pi的局部變量中，無(wú)須用i做下標(biāo)，但在討論和證明中，加上下標(biāo)i以示區(qū)別?！?”后跟注釋372.2 生成樹上的廣播和匯集 信息收集及分發(fā)是許多分布式算法的基礎(chǔ)。故通過(guò)介紹這兩個(gè)算法來(lái)說(shuō)明模型、偽碼、正確性證明及復(fù)雜性度量等概念。2.2.1 廣播(Broadcast) 假定網(wǎng)絡(luò)的生成樹已給定。某處理器pr希望將消息M發(fā)送至其余處理器。 假定生成樹的根為pr ，每個(gè)處理器有一個(gè)信道連接其雙親(pr除外)，有若干個(gè)信道連接其孩子。由于分布式系統(tǒng)中，每個(gè)節(jié)點(diǎn)并不知道全局拓?fù)?，但某些算法需要在特定結(jié)構(gòu)下

19、才能達(dá)到最優(yōu)，比如廣播/斂播在樹結(jié)構(gòu)下才能達(dá)到消息復(fù)雜度最優(yōu)，因此構(gòu)造生成樹是必要的，是其他算法的基礎(chǔ)。382.2.1 廣播根pr發(fā)送M給所有孩子。(a)當(dāng)某結(jié)點(diǎn)收到父結(jié)點(diǎn)的M時(shí)，發(fā)送M到自己的所有孩子(b)。392.2.1 廣播1.偽碼算法Alg2.1 Broadcast pr:/發(fā)動(dòng)者。假設(shè)初始化時(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;5.

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

21、bufi j 里， jchildreni412.2.1 廣播pi進(jìn)入終止?fàn)顟B(tài)將terminatedi置為true；若i=r且terminatedr為false，則terminatedr立即置為true，否則空操作。該算法對(duì)同步及異步系統(tǒng)均正確，且在兩模型中，msg和時(shí)間復(fù)雜度相同。Msg復(fù)雜度無(wú)論在同步還是異步模型中，msg M在生成樹的每條邊上恰好發(fā)送一次。因此，msg復(fù)雜性為n-1。422.2.1 廣播時(shí)間復(fù)雜性：同步模型：時(shí)間由輪來(lái)度量。Lemma2.1 在同步模型中，在廣播算法的每個(gè)容許執(zhí)行里，樹中每個(gè)距離pr為t的處理器在第t輪里接收消息M。pf：對(duì)距離t使用歸納法。歸納基礎(chǔ)：t=1

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

23、異步模型的時(shí)間復(fù)雜性定義知，pi至多在時(shí)刻1收到M。 pi 距pr為t的處理器，設(shè)pj是pi的雙親，則pj與pr的距離為t-1，由歸納假設(shè)知，pj至多在時(shí)刻t-1收到M，由算法描述知，pj發(fā)送給pi的M至多在t時(shí)刻到達(dá)。Th2.4 同Th2.244下次繼續(xù)！45第二部分 分布式算法第三次課中國(guó)科學(xué)技術(shù)大學(xué)計(jì)算機(jī)系 國(guó)家高性能計(jì)算中心（合肥）462.2.2 convergecast(匯集，斂播)與廣播問(wèn)題相反，匯集是從所有結(jié)點(diǎn)收集信息至根。為簡(jiǎn)單起見，先考慮一個(gè)特殊的變種問(wèn)題： 假定每個(gè)pi開始時(shí)有一初值xi，我們希望將這些值中最大者發(fā)送至根pr。472.2.2 convergecast(匯集，

24、斂播)算法 每個(gè)葉子結(jié)點(diǎn)pi發(fā)送xi至雙親。/啟動(dòng)者對(duì)每個(gè)非葉結(jié)點(diǎn)pj，設(shè)pj有k個(gè)孩子pi1,pik，pj等待k個(gè)孩子的msg vi1,vi2,vik，當(dāng)pj收到所有孩子的msg之后將vj=maxxj,vi1,vik發(fā)送到pj的雙親。換言之：葉子先啟動(dòng)，每個(gè)處理器pi計(jì)算以自己為根的子樹里的最大值vi，將vi發(fā)送給pi的雙親。復(fù)雜性Th2.5 當(dāng)生成樹高為d時(shí)，存在一個(gè)異步的斂播方法，其msg復(fù)雜性為n-1，時(shí)間復(fù)雜度為d。(與Th2.2相同)廣播和斂播算法用途：初始化某一信息請(qǐng)求(廣播發(fā)布)，然后用斂播響應(yīng)信息至根。482.3 構(gòu)造生成樹上節(jié)算法均假設(shè)通信網(wǎng)的生成樹已知。本節(jié)介紹生成樹的構(gòu)

25、造問(wèn)題。1.Flooding算法(淹沒(méi))算法 設(shè)pr是特殊處理器。從pr開始，發(fā)送M到其所有鄰居。當(dāng)pi第1次收到消息M（不妨設(shè)此msg來(lái)自于鄰居pj）時(shí)，pi發(fā)送M到除pj外的所有鄰居。492.3 構(gòu)造生成樹msg復(fù)雜性因?yàn)槊總€(gè)結(jié)點(diǎn)在任一信道上發(fā)送M不會(huì)多于1次，所以每個(gè)信道上M至多被發(fā)送兩次(使用該信道的每個(gè)處理器各1次)。在最壞情況下：M除第1次接收的那些信道外，所有其他信道上M被傳送2次。因此，有可能要發(fā)送2m-(n-1)個(gè)msgs。這里m是系統(tǒng)中信道總數(shù)，它可能多達(dá)n(n-1)/2。時(shí)間復(fù)雜性：O(D)D網(wǎng)直徑2.構(gòu)造生成樹對(duì)于flooding稍事修改即可得到求生成樹的方法。502.

26、3 構(gòu)造生成樹基本思想首先，pr發(fā)送M給所有鄰居，pr為根當(dāng)pi從某鄰居pj收到的M是第1個(gè)來(lái)自鄰居的msg時(shí)，pj是pi的雙親；若pi首次收到的M同時(shí)來(lái)自多個(gè)鄰居，則用一個(gè)comp事件處理自上一comp事件以來(lái)的所有已收到的msgs，故此時(shí)，pi可在這些鄰居中任選一個(gè)鄰居pj做雙親。當(dāng)pi確定雙親是pj時(shí)，發(fā)送給pj，并向此后收到發(fā)來(lái)M的處理器發(fā)送msg512.3 構(gòu)造生成樹基本思想因?yàn)閜i收到pj的M是第1個(gè)M，就不可能已收到其他結(jié)點(diǎn)的M，當(dāng)然可能同時(shí)收到(說(shuō)明pi與這些鄰居間不是父子關(guān)系，或說(shuō)它們不是生成樹中的邊)；同時(shí)pi將M轉(zhuǎn)發(fā)給其余鄰居，這些鄰居尚未發(fā)M給pi，或雖然已發(fā)M給pi，

27、但pi尚未收到。pi向那些尚未發(fā)M給pi(或已發(fā)M但尚未到達(dá)pi)的鄰居轉(zhuǎn)發(fā)M之后，等待這些鄰居發(fā)回響應(yīng)msg：或。那些回應(yīng)的鄰居是pi的孩子。當(dāng)pi發(fā)出M的所有接收者均已回應(yīng)(或)，則pi終止。將parent和children邊保留即為生成樹。522.3 構(gòu)造生成樹圖示pi若認(rèn)為pj是其雙親，則pi向pr發(fā)出M，而pr仍會(huì)向pi發(fā)reject，但因?yàn)榇饲皃r向pi發(fā)出過(guò)M，故pi收到M時(shí)仍會(huì)向pr發(fā)reject。(可以改進(jìn)？)532.3 構(gòu)造生成樹算法：Alg2.2 構(gòu)造生成樹（code for pi 0in-1）初值：parent=nil；集合children和other均為upon re

28、ceiving no message: if i=r and parent=nil then /根尚未發(fā)送M send M to all neighbors; parent:=i; /根的雙親置為自己upon receiving M from neighbor pj: if parent=nil then /pi此前未收到過(guò)M，M是pi收到的第1個(gè)msg parent:=j; send to pj; /pj是pi的雙親 send M to all neighbors except pj; else /pj不可能是pi的雙親，pi收到的M不是第1個(gè)msg send to pj;upon rece

29、iving from neighbor pj: children:=children j ; /pj是pi的孩子，將j加入孩子集 if childrenother 包含了除parent外的所有鄰居 then terminate;upon receiving from neighbor pj: other:=other j ; /將j加入other，通過(guò)非樹邊發(fā)送的msg。 if childrenother包含了除pi的雙親外的所有鄰居 then terminate;542.3 構(gòu)造生成樹分析Lemma2.6 在異步模型的每個(gè)容許執(zhí)行中，算法2.2構(gòu)造一棵根為pr的生成樹。(正確性)Pf：算法代

30、碼告訴我們兩個(gè)重要事實(shí)一旦處理器設(shè)置了parent變量，它絕不改變，即它只有一個(gè)雙親處理器的孩子集合決不會(huì)減小。因此，最終由parent和children確定的圖結(jié)構(gòu)G是靜止的，且parent和children變量在不同結(jié)點(diǎn)上是一致的，即若pj是pi的孩子，則pi是pj的雙親。 下述證明結(jié)果圖G是根為pr的有向生成樹。552.3 構(gòu)造生成樹為何從根能到達(dá)每一結(jié)點(diǎn)？(連通)反證：假設(shè)某結(jié)點(diǎn)在G中從pr不可達(dá)，因網(wǎng)絡(luò)是連通的，若存在兩個(gè)相鄰的結(jié)點(diǎn)pi和pj使得pj在G中是從pr可達(dá)的(以下簡(jiǎn)稱pj可達(dá))，但pi不可達(dá)。因?yàn)镚里一結(jié)點(diǎn)從pr可達(dá)當(dāng)且僅當(dāng)它曾設(shè)置過(guò)自己的parent變量(Ex2.4證明

31、)，所以pi的parent變量在整個(gè)執(zhí)行中仍為nil，而pj在某點(diǎn)上已設(shè)置過(guò)自己的parent變量，于是pj發(fā)送M到pi(line9)，因該執(zhí)行是容許的，此msg必定最終被pi接收，使pi將自己的parent變量設(shè)置為j。矛盾！562.3 構(gòu)造生成樹為何無(wú)環(huán)？(無(wú)環(huán))假設(shè)有一環(huán)，pi1,pikpi1，若pi是pj的孩子，則pi在pj第1次收到M之后第1次收到M。因每個(gè)處理器在該環(huán)上是下一處理器的雙親，這就意味著pi1在pi1第1次接收M之前第1次接收M。矛盾！復(fù)雜性顯然，此方法與淹沒(méi)算法相比，增加了msg復(fù)雜性，但只是一個(gè)常數(shù)因子。在異步通信模型里，易看到在時(shí)刻t，消息M到達(dá)所有與pr距離小于

32、等于t的結(jié)點(diǎn)。因此有：Th2.7 對(duì)于具有m條邊和直徑D的網(wǎng)絡(luò)，給定一特殊結(jié)點(diǎn)，存在一個(gè)msg復(fù)雜性為O(m)，時(shí)間復(fù)雜性為O(D)的異步算法找到該網(wǎng)絡(luò)的一棵生成樹。572.3 構(gòu)造生成樹Alg2.2在同步模型下仍可工作。其分析類似于異步情形。然而，與異步不同的是，它所構(gòu)造的生成樹一定是一棵廣度優(yōu)先搜索(BFS)樹。Lemma2.8 在同步模型下，Alg2.2的每次容許執(zhí)行均構(gòu)造一棵根為pr的BFS樹。Pf：對(duì)輪t進(jìn)行歸納。即要證明：在第t輪開始時(shí)刻 根據(jù)parent變量構(gòu)造的圖G是一棵包括所有與pr距離至多為t-1結(jié)點(diǎn)的BFS樹； 而傳輸中的消息M僅來(lái)自于與pr距離恰為t-1的結(jié)點(diǎn)。 由此構(gòu)

33、造的樹是一棵根為pr的BFS582.3 構(gòu)造生成樹當(dāng)t=1時(shí)，所有parent初值為nil，M從pr傳出。假設(shè)引理對(duì)第t-11輪為真，在該輪里，從距離 t-2的結(jié)點(diǎn)傳出的M被接收，任何接收M的結(jié)點(diǎn)與pr的距離不超過(guò)t-1(恰為t-1或更短)，那些parent值非空的接收結(jié)點(diǎn)顯然與pr的距離不超過(guò)t-2，他們既不改變parent的值也不轉(zhuǎn)發(fā)M；而與pr距離為t-1的結(jié)點(diǎn)在t-1輪里收到M，因?yàn)樗鼈兊膒arent為nil，故將其置為合適的雙親并轉(zhuǎn)發(fā)M。距離pr大于t-1的結(jié)點(diǎn)不會(huì)收到M，因此也不會(huì)轉(zhuǎn)發(fā)M。因此有如下定理：Th2.9 對(duì)于具有m條邊直徑為D的網(wǎng)絡(luò)，給定一個(gè)特殊結(jié)點(diǎn)，存在一個(gè)同步算法在

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

35、和異步模型中不同,設(shè)網(wǎng)是完全圖求生成樹算法：同步和異步均為 消息復(fù)雜性O(shè)(m) 時(shí)間復(fù)雜性O(shè)(D)匯集算法：同步和異步均有 msg n-1 time d /生成樹高組合算法 同步：組合算法的msg復(fù)雜性O(shè)(m+n)；BFS樹中， d=1， dD，故時(shí)間復(fù)雜性O(shè)(D+d)=O(D)=O(1)。 異步：組合算法的msg復(fù)雜性O(shè)(m+n)；生成樹高 d=n-1，所以時(shí)間復(fù)雜性O(shè)(D+d)=O(d)=O(n)。 1-time復(fù)雜性的組合算法T(n)=O(D)。 612.4 構(gòu)造DFS生成樹(指定根) 構(gòu)造DFS樹時(shí)每次加一個(gè)結(jié)點(diǎn)，而不像Alg2.2那樣，試圖在樹上同時(shí)增加同一層的所有結(jié)點(diǎn)。Alg2.3

36、 構(gòu)造DFS生成樹，為Pr為根Code for processor Pi, 0i n-1varparent:init nil;children:init ;unexplored:init all the neighbors of Pi /未訪問(wèn)過(guò)的鄰居集1: upon receiving no msg:2: if (i=r) and (parent=nil) then /當(dāng)Pi為根且未發(fā)送M時(shí)3: parent := i; /將parent置為自身的標(biāo)號(hào)4: Pj unexplored;5: 將Pj從unexplored中刪去; /若Pr是孤立結(jié)點(diǎn),4-6應(yīng)稍作修改6: send M to P

37、j; /endif622.4 構(gòu)造DFS生成樹(指定根)7: upon receiving M from neighbor Pj:8: if parent=nil then /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)Pi的鄰居均已訪問(wèn)過(guò)，返回到父親16: else send to Pj; /當(dāng)Pi已訪問(wèn)過(guò)時(shí)632.4 構(gòu)

38、造DFS生成樹(指定根)17: upon receiving or from neighbor Pj:18: if received then add j to children; /Pj是Pi的孩子19: if unexplored = then /Pi的鄰居均已訪問(wèn)20: if parent i then send to parent; /Pi非根，返回至雙親21: terminate; /以Pi為根的DFS子樹已構(gòu)造好！22: else /選擇Pi的未訪問(wèn)過(guò)的鄰居訪問(wèn)之23: Pk unexplored;24: 將Pk從unexplored中刪去；25: send M to Pk; 64

39、2.4 構(gòu)造DFS生成樹(指定根)引理2.10 在異步模型里的每個(gè)容許執(zhí)行，Alg2.3構(gòu)造一棵以Pr為根的DFS樹。證明留作練習(xí)。Th2.11 對(duì)于一個(gè)具有m條邊，n個(gè)結(jié)點(diǎn)的網(wǎng)絡(luò)，以及給定的特殊頂點(diǎn)，存在一個(gè)時(shí)間復(fù)雜性和消息復(fù)雜性均為O(m)的異步算法找到一棵DFS樹。Pf：每個(gè)結(jié)點(diǎn)在其鄰接邊上至多發(fā)送M一次，每個(gè)結(jié)點(diǎn)至多生成一個(gè)msg(或)作為對(duì)每個(gè)鄰接邊上收到的M的響應(yīng)。因此Alg2.3至多發(fā)送4m個(gè)消息(其實(shí)大部分沒(méi)有4倍)，即算法的msg復(fù)雜性為O(m)。時(shí)間復(fù)雜性證明留作練習(xí)。如何改進(jìn)使msg的復(fù)雜性不是4m？注意：上述算法msg復(fù)雜性較好，但時(shí)間復(fù)雜性太差?？山抵罯(n)。65

40、下次繼續(xù)！66第二部分 分布式算法第四次課中國(guó)科學(xué)技術(shù)大學(xué)計(jì)算機(jī)系 國(guó)家高性能計(jì)算中心（合肥）672.5 不指定根時(shí)構(gòu)造DFS生成樹 算法2.2和2.3構(gòu)造連通網(wǎng)絡(luò)的生成樹時(shí)，必需存在一個(gè)特殊的結(jié)點(diǎn)作為啟動(dòng)者(Leader)。當(dāng)這樣的特殊結(jié)點(diǎn)不存在時(shí)，如何構(gòu)造網(wǎng)絡(luò)的一棵生成樹？但本節(jié)算法須假定：各結(jié)點(diǎn)的標(biāo)識(shí)符唯一，不妨設(shè)是自然數(shù)，3.2仍需此假定。基本思想每個(gè)結(jié)點(diǎn)均可自發(fā)喚醒，試圖構(gòu)造一棵以自己為根的DFS生成樹。若兩棵DFS樹試圖鏈接同一節(jié)點(diǎn)(未必同時(shí))時(shí)，該節(jié)點(diǎn)將加入根的id較大的DFS樹。為了實(shí)現(xiàn)上述思想，須做：每個(gè)結(jié)點(diǎn)設(shè)置一個(gè)leader變量，其初值為0，當(dāng)Pi喚醒自己時(shí)，leader

41、i=idi；不指定根構(gòu)造DFS生成樹，和后面的領(lǐng)導(dǎo)者選舉問(wèn)題一樣，都是破對(duì)稱問(wèn)題。682.5 不指定根時(shí)構(gòu)造DFS生成樹當(dāng)一結(jié)點(diǎn)自發(fā)喚醒時(shí)，它將自己的id(leader)發(fā)送給某一鄰居；當(dāng)一結(jié)點(diǎn)Pi收到來(lái)自鄰居Pj的標(biāo)識(shí)符y時(shí)，Pi比較y和leaderi： 若yleaderi，則y可能是具有最大標(biāo)識(shí)符結(jié)點(diǎn)的DFS子樹的標(biāo)記。因此，將leaderi置為y，并令Pj是Pi的雙親。從Pi開始繼續(xù)生成標(biāo)記為y的DFS樹。Note：要修改原Pi所在的DFS子樹中所有結(jié)點(diǎn)的leader。692.5 不指定根時(shí)構(gòu)造DFS生成樹若yleaderi，則標(biāo)記為y的DFS樹中最大id(y)小于目前所看到的最大標(biāo)識(shí)符

42、。此時(shí)無(wú)須發(fā)送msg，停止構(gòu)造標(biāo)記為y的DFS。等待最終某個(gè)更大的id的leader消息到達(dá)標(biāo)記為y的樹中結(jié)點(diǎn)時(shí)，再將該節(jié)點(diǎn)連接到樹中。(至少標(biāo)記為leaderi的msg會(huì)到達(dá)標(biāo)記為y的樹)若y=leaderi，則Pi已屬于標(biāo)記y的DFS樹中。702.5 不指定根時(shí)構(gòu)造DFS生成樹算法Alg2.4 構(gòu)造生成樹，不指定根 Code for Processor Pi 0in-1Var parent:init nil; leader:init 0; children:int ; unexplored:init all neighbors of Pi;1: upon receiving no msg:

43、 /wake up spontaneously2: if parent = nil then /若非空，則Pi在某子樹上，則Pi失去競(jìng)選機(jī)會(huì)3: leader := id; parent := i;/試圖以自己為根構(gòu)造樹4: Pjunexplored;5: 將Pj從unexplored中刪去；6： send to pj; 712.5 不指定根時(shí)構(gòu)造DFS生成樹想像：有m個(gè)人競(jìng)選領(lǐng)袖，id是他自身的素質(zhì)分，不想競(jìng)爭(zhēng)人的id不參與比較。競(jìng)爭(zhēng)規(guī)則：將自己的id(如講演片)傳遞給一個(gè)熟悉的人，由他再傳給另一人(一次只能送一人。)7: upon receiving from neighbor Pj: 8

44、: if leadernew-id then /將Pi所在樹合并到Pj所在樹中9: leader := new-id; parent := j; /令Pi的雙親為Pj，可能是修改，而非對(duì)nil賦值 /并不一定能停止較差的競(jìng)選者傳播msg10: unexplored := all the neighbors of Pi except Pj; /重置未訪問(wèn)的鄰居集11: if unexplored then /因?yàn)閚ew-id大，使原Pi所在DFS樹修改各自id12： Pk unexplored;13: 將Pk從unexplored中刪去；722.5 不指定根時(shí)構(gòu)造DFS生成樹14: send t

45、o PK; 15: else send to parent; / unexplored = else / leadernew-id 16: if leader=new-id then send to Pj; /表示自己已經(jīng)傳出過(guò)此錄像帶，無(wú)需重傳。已在同一樹中/若leadernew-id，則new-id所在DFS停止構(gòu)造/以前收到的競(jìng)選者優(yōu)于new-id，不傳送，使之停止傳播。17: upon receiving or from neighbor Pj:18: if received then add j to children;19: if unexplored= then /無(wú)尚未訪問(wèn)的鄰

46、居20: if parenti then send to parent /返回21: else terminates as root of the DFS tree; /根終止22: else /有尚未訪問(wèn)的鄰居732.5 不指定根時(shí)構(gòu)造DFS生成樹23: Pk unexplored;24: 將Pk從unexplored中刪去；25: send to Pk; 分析：只有生成樹的根顯式地終止，其它結(jié)點(diǎn)沒(méi)有終止，始終在等待msg。但可修改此算法，使用Alg2.1從根結(jié)點(diǎn)發(fā)送終止msg正確性該算法比前面的算法更復(fù)雜，這里只給出粗略的證明。設(shè)Pm是所有自發(fā)喚醒結(jié)點(diǎn)中標(biāo)識(shí)符最大者，其標(biāo)識(shí)符為idm。消息

47、idm總是被傳播，而一旦一個(gè)結(jié)點(diǎn)收到idm，則該節(jié)點(diǎn)(Pm除外)上所有msgs被忽略。因?yàn)橄dm的處理和Alg2.3求DFS樹一致，因此產(chǎn)生的parent和children變量的設(shè)置是正確的。因此有：742.5 不指定根時(shí)構(gòu)造DFS生成樹Lemma2.12 設(shè)Pm是所有自發(fā)喚醒結(jié)點(diǎn)中具有最大標(biāo)識(shí)符的結(jié)點(diǎn)。在異步模型的每次容許執(zhí)行里，算法2.4構(gòu)造根為Pm的一棵DFS樹。Note：因?yàn)樵谌菰S執(zhí)行中，網(wǎng)絡(luò)里的所有自發(fā)喚醒結(jié)點(diǎn)中最大標(biāo)識(shí)符結(jié)點(diǎn)最終會(huì)自發(fā)啟動(dòng)，故建立的DFS樹的根是Pm可通過(guò)廣播算法從Pm發(fā)出終止msg，即使不廣播，所有非Pm結(jié)點(diǎn)最終也會(huì)因?yàn)槭盏絇m的標(biāo)識(shí)符而停止。因此，不可能構(gòu)造

48、一棵根不是Pm的生成樹。Lemma2.13 在異步模型的每個(gè)容許執(zhí)行里，只有一個(gè)處理器終止作為一生成樹的根。752.5 不指定根時(shí)構(gòu)造DFS生成樹復(fù)雜性定理：對(duì)于一個(gè)具有m條邊和n個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)，自發(fā)啟動(dòng)的節(jié)點(diǎn)共有p個(gè)，其中ID值最大者的啟動(dòng)時(shí)間為t，則算法的消息復(fù)雜度為O(pn2)，時(shí)間復(fù)雜度為O(t+m)。消息復(fù)雜性：簡(jiǎn)單地分析，最壞情況下，每個(gè)處理器均試圖以自己為根構(gòu)造一棵DFS樹。因此，Alg2.4的msg復(fù)雜性至多是Alg2.3的n倍：O(m*n) 時(shí)間復(fù)雜性：類似于Alg2.3的msg復(fù)雜性O(shè)(m)。762.5 不指定根時(shí)構(gòu)造DFS生成樹Ex.2.1 分析在同步和異步模型下，conv

49、ergecast算法的時(shí)間復(fù)雜性。2.2 證明在引理2.6中，一個(gè)處理器在圖G中是從Pr可達(dá)的，當(dāng)且僅當(dāng)它的parent變量曾被賦過(guò)值2.3 證明Alg2.3構(gòu)造一棵以Pr為根的DFS樹。2.4 證明Alg2.3的時(shí)間復(fù)雜性為O(m)。2.5 修改Alg2.3獲得一新算法，使構(gòu)造DFS樹的時(shí)間復(fù)雜性為O(n)。補(bǔ)充 2.6 小結(jié)77補(bǔ)充 構(gòu)造最小生成樹 考慮每個(gè)信道都有權(quán)重，代表了信道的通信成本，這樣最小生成樹能夠使得執(zhí)行廣播算法總開銷最小。 假設(shè)每個(gè)信道的權(quán)重都已存儲(chǔ)在其兩端的節(jié)點(diǎn)的局部?jī)?nèi)存中?；舅枷耄?每個(gè)節(jié)點(diǎn)都有一個(gè)所屬樹的變量編號(hào)，用來(lái)判斷兩個(gè)節(jié)點(diǎn)是否屬于一棵樹。剛開始時(shí)，每個(gè)節(jié)點(diǎn)獨(dú)

50、立成一棵樹，其ID值為樹的編號(hào)，每棵樹并發(fā)的搜索自己權(quán)值最小的出邊，并把這些邊加入到生成森林中，同時(shí)幾棵樹也就合并為一棵樹，取其中編號(hào)較大的一個(gè)為合并之后的樹的編號(hào)，更新樹中各節(jié)點(diǎn)的樹編號(hào)變量。直至所有的樹都被合并為一棵樹，此即為最小生成樹。78補(bǔ)充 構(gòu)造最小生成樹可能出現(xiàn)的4個(gè)問(wèn)題：產(chǎn)生環(huán) 可以證明，如果邊的權(quán)值不相等， 那么圖G只有唯一的最小生成樹。 利用三元組，將邊表述為 1,i,j,1,j,k,1,i,k 當(dāng)權(quán)相同時(shí)，按照i,j,k的字典序來(lái)排序 假設(shè)ijk,則有1,i,j1,i,k level(T) then (5.1) ID(T)ID(T) (5.2) level(T)level(

51、T) else / level(T)=level(T) (5.3) ID(T)maxID(T), ID(T) (5.4) level(T)level(T)+1 end if end whileend83補(bǔ)充 構(gòu)造最小生成樹消息復(fù)雜度： 每個(gè)level為k的樹中的節(jié)點(diǎn)數(shù)至少為2k，level最大為log(n)(n為節(jié)點(diǎn)數(shù))。因?yàn)槊總€(gè)節(jié)點(diǎn)都從邊的權(quán)值從小到大開始探測(cè)此邊是否是出邊，當(dāng)確定某邊是出邊后就停止探測(cè)并斂播給根節(jié)點(diǎn)，直到根確認(rèn)這條邊是這棵樹的最小邊，并進(jìn)行合并操作，并更新level值，然后繼續(xù)探測(cè)。 消息分兩類：每個(gè)節(jié)點(diǎn)探測(cè)自己的一條邊是否是出邊而得到否認(rèn)消息，這些消息數(shù)目為O(m)；每一

52、層中在樹T中各種消息的傳遞，其消息數(shù)目為O(|T|)，|T|表示樹的節(jié)點(diǎn)數(shù)，此總數(shù)目為故消息總數(shù)為O(m+nlogn)84補(bǔ)充 構(gòu)造最小生成樹 時(shí)間復(fù)雜度： 系統(tǒng)中所有節(jié)點(diǎn)，其所在的樹的level值都變成k 時(shí)所需的時(shí)間為O(kn)，又因?yàn)閗的最大值為log(n)，所以總時(shí)間為O(nlogn)。852.6 小結(jié)Introduction to distributed alg分類：?jiǎn)卧碼lg：一個(gè)啟動(dòng)者。又稱centralized alg。多源alg：任意進(jìn)程(結(jié)點(diǎn))子集均可是啟動(dòng)者，又稱decentralized alg啟動(dòng)者(initiator)：自發(fā)地執(zhí)行局部算法，即由一內(nèi)部事件激發(fā)其執(zhí)行非

53、啟動(dòng)者：由接收一個(gè)msg(外部事件)觸發(fā)其執(zhí)行局部進(jìn)程。復(fù)雜性：Msg復(fù)雜性：msg總數(shù)目Bit復(fù)雜性：發(fā)送msg中bit的總數(shù)目，當(dāng)msg在發(fā)送過(guò)程中其長(zhǎng)度隨時(shí)間增長(zhǎng)時(shí)862.6 小結(jié)時(shí)間復(fù)雜性一個(gè)分布式算法的時(shí)間復(fù)雜性是滿足下述兩個(gè)假定的一個(gè)計(jì)算所耗費(fèi)的最大時(shí)間T1：一個(gè)進(jìn)程在零時(shí)間內(nèi)可計(jì)算任何有限數(shù)目的事件T2：一個(gè)msg的發(fā)送和接受之間的時(shí)間至多為1個(gè)時(shí)間單位缺點(diǎn):針對(duì)一算法的所有計(jì)算，其結(jié)果可能是極不可能發(fā)生的計(jì)算。一個(gè)分布式算法的one-time復(fù)雜性是滿足下述假定的一個(gè)計(jì)算的最大時(shí)間O1：同T1O2：發(fā)送和接收一個(gè)msg之間的時(shí)間恰好是1個(gè)單位時(shí)間缺點(diǎn)：某些計(jì)算可能被忽略，而其中

54、可能有極其耗時(shí)的計(jì)算872.6 小結(jié)表面上，1-time復(fù)雜性至少等于時(shí)間復(fù)雜性，因?yàn)門2假定下的最壞時(shí)間不會(huì)高于O2假定下的時(shí)間。但事實(shí)并非如此，而往往O1和O2假定之下的1-time復(fù)雜性是前一種時(shí)間復(fù)雜性的一個(gè)下界。 例如：在echo算法里1-time復(fù)雜性是O(D)，時(shí)間復(fù)雜性是(N)，即使直徑為1的網(wǎng)絡(luò)。兩種復(fù)雜性的折中：-復(fù)雜性假定每個(gè)msg延遲介于-1之間(1常數(shù))對(duì)echo 算法復(fù)雜性為O(min(N, D/ )概率分析：msg延遲服從某種概率分布，由此可獲得精確的時(shí)間復(fù)雜性度量882.6 小結(jié)基于msg chains的分析任何計(jì)算中最長(zhǎng)消息鏈的長(zhǎng)度。 鏈上msgs：m1,m2

55、,mk序列中，mi因果關(guān)系領(lǐng)先于mi+1。先驗(yàn)知識(shí)：鄰居的id，全局id等。鏈路FIFO假定等89下次繼續(xù)！90第三章 環(huán)上選舉算法汪 煬91本章提綱Leader選舉問(wèn)題匿名環(huán)異步環(huán)同步環(huán)92問(wèn)題在一組處理器中選出一個(gè)特殊結(jié)點(diǎn)作為leader用途簡(jiǎn)化處理器之間的協(xié)作；有助于達(dá)到容錯(cuò)和節(jié)省資源。例如，有了一個(gè)leader，就易于實(shí)現(xiàn)廣播算法代表了一類破對(duì)稱問(wèn)題。例如，當(dāng)死鎖是由于處理器相互環(huán)形等待形成時(shí)，可使用選舉算法，找到一個(gè)leader并使之從環(huán)上刪去，即可打破死鎖。933.1 leader選舉問(wèn)題Leader選舉問(wèn)題： 問(wèn)題從具有同一狀態(tài)的進(jìn)程配置開始，最終達(dá)到一種配置狀態(tài)。每個(gè)處理器最終

56、確定自己是否是一個(gè)leader，但只有一個(gè)處理器確定自己是leader，而其他處理器確定自己是non-leader。 算法的作用： 如果要執(zhí)行一個(gè)分布式算法，且沒(méi)有一個(gè)優(yōu)先的優(yōu)選人做為算法的初始進(jìn)程，就要進(jìn)行進(jìn)程選舉。(例如指定根的DFS樹的生成問(wèn)題) 943.1 leader選舉問(wèn)題選舉算法的定義： （1）每個(gè)處理器具有相同的局部算法； （2）算法是分布式的，處理器的任意非空子集都能開 始一次計(jì)算； （3）每次計(jì)算中，算法達(dá)到終止配置。在每一可達(dá)的 終止配置中，只有一個(gè)處理器處于領(lǐng)導(dǎo)人狀態(tài)，其 余均處于失敗狀態(tài)。 一個(gè)算法解決了leader選舉問(wèn)題需滿足(根據(jù)形式化模型)：終止?fàn)顟B(tài)被劃分為兩

57、類：選中和未選中狀態(tài)。一旦一個(gè)處理器進(jìn)入選中(或未選中)狀態(tài)，則該處理器上的轉(zhuǎn)換函數(shù)將只會(huì)將其變?yōu)橄嗤臓顟B(tài)；在每個(gè)容許執(zhí)行里，只有一個(gè)處理器進(jìn)入選中狀態(tài)，其余處理器進(jìn)入非選中(non-selected)狀態(tài)。本章只討論系統(tǒng)的拓?fù)浣Y(jié)構(gòu)是環(huán)的情況。（此項(xiàng)有時(shí)可以弱化）953.1 leader選舉問(wèn)題環(huán)的形式化模型對(duì)每個(gè)i，0i n-1，Pi到Pi+1的邊標(biāo)號(hào)為1，稱為左(順時(shí)針)Pi到Pi-1的邊標(biāo)號(hào)為2，稱為右(逆時(shí)針)這里的標(biāo)號(hào)加減均是mod n的環(huán)網(wǎng)絡(luò)之所以吸引了如此多的研究，是因?yàn)樗鼈兊男袨橐子诿枋?；且從環(huán)網(wǎng)絡(luò)推導(dǎo)出的下界，可應(yīng)用于具有任意拓?fù)浣Y(jié)構(gòu)的網(wǎng)絡(luò)算法設(shè)計(jì)963.2 匿名環(huán)（ano

58、nymous）匿名算法：若環(huán)中處理器沒(méi)有唯一的標(biāo)識(shí)符，則環(huán)選舉算法是匿名的。更形式化的描述：每個(gè)處理器在系統(tǒng)中具有相同的狀態(tài)機(jī)，在這種算法里，msg接收者只能根據(jù)信道標(biāo)號(hào)來(lái)區(qū)別。（一致性的）uniform算法：若算法不知道處理器數(shù)目，則算法稱之為uniform，因?yàn)樵撍惴▽?duì)每個(gè)n值看上去是相同的。non-uniform算法：算法已知處理器數(shù)目n形式化描述：在一個(gè)匿名、一致性的算法中，所有處理器只有一個(gè)狀態(tài)機(jī)；在一個(gè)匿名、非一致性的算法中，對(duì)每個(gè)n值（處理器數(shù)目）都有單個(gè)狀態(tài)機(jī)，但對(duì)不同規(guī)模有不同狀態(tài)機(jī)，也就是說(shuō)n可以在代碼中顯式表達(dá)。973.2 匿名環(huán)（anonymous）對(duì)于環(huán)系統(tǒng)，不存在匿

59、名的選舉算法。為簡(jiǎn)單起見，我們只證明非均勻（非一致性）算法：非均勻算法（n已知）的不可能性=均勻（n未知）算法的不可能性。Ex3.1 證明同步環(huán)系統(tǒng)中不存在匿名的、一致性的領(lǐng)導(dǎo)者選舉算法。同步算法：同步算法的不可能性=異步算法的不可能性。（同步是異步的一種特例） Ex3.2 證明異步環(huán)系統(tǒng)中不存在匿名的領(lǐng)導(dǎo)者選舉算法。983.2 匿名環(huán)同步算法的不可能性 在同步系統(tǒng)中，一個(gè)算法以輪的形式進(jìn)行。每輪里所有待發(fā)送msg被傳遞，隨后每個(gè)處理器進(jìn)行一步計(jì)算。 一個(gè)處理器的初始狀態(tài)包括在outbuf里的任何msg。這些消息在第一輪里被傳遞到某處理器的左和右鄰居。不可能性： 在一個(gè)匿名環(huán)中，處理器間始終保

60、持對(duì)稱，若無(wú)某種初始的非對(duì)稱(如，標(biāo)識(shí)符唯一)，則不可能打破對(duì)稱。在匿名環(huán)算法里，所有處理器開始于相同狀態(tài)。 因?yàn)樗麄儓?zhí)行同樣的程序(即他們的狀態(tài)機(jī)相同)，在每輪里各處理器均發(fā)送同樣的msg，所以在每一輪里各處理器均接收同樣的msg，改變狀態(tài)亦相同。因此，若選中一個(gè)處理器，則其他所有處理器亦被選中。因此，不可能有一個(gè)算法在環(huán)中選中單個(gè)處理器為leader。993.2 匿名環(huán) 假設(shè)R是大小為n1的環(huán)（非均勻），A是其上的一個(gè)匿名算法，它選中某處理器為leader。因?yàn)榄h(huán)是同步的且只有一種初始配置，故在R上A只有唯一的合法執(zhí)行。Lemma3.1 在環(huán)R上算法A的容許執(zhí)行里，對(duì)于每一輪k，所有處理器