本書對分布式算法進行了全面介紹，包括同步模型、異步模型和部分同步模型，針對這些模型討論互斥性、一致性和通信問題，為設(shè)計、實現(xiàn)和分析分布式算法提供了藍圖。本書對分布式算法領(lǐng)域的許多經(jīng)典問題給出了多種解決算法或者不可能性結(jié)果，絕大部分的算法附有詳細的證明過程，并且有jing確的復(fù)雜度衡量。本書還配有大量習(xí)題，并在每章后列出了詳細的參考文獻。本書可作為高等院校計算機專業(yè)的研究生教材，尤其適合對計算機理論或體系結(jié)構(gòu)感興趣的學(xué)生學(xué)習(xí)，還適合分布式領(lǐng)域的設(shè)計人員和研究人員參考。
前 言
Distributed Algorithms
分布式算法是用于解決多個互連處理器運行問題的算法。分布式算法的各部分并發(fā)和獨立地運行，每一部分只承載有限的信息。即使處理器和通信信道以不同的速度運作，或即使某些構(gòu)件出了故障，這些算法仍然應(yīng)該正常運行。
分布式算法有廣泛的應(yīng)用：電信、分布式信息處理、科學(xué)計算以及實時進程控制。例如，電話系統(tǒng)、航班訂票系統(tǒng)、銀行系統(tǒng)、全球信息系統(tǒng)、天氣預(yù)報系統(tǒng)以及飛機和核電站控制系統(tǒng)都嚴(yán)重依賴于分布式算法。很明顯，確保分布式算法準(zhǔn)確、高效地運行是非常重要的。然而，由于這種算法的執(zhí)行環(huán)境很復(fù)雜，所以設(shè)計分布式算法就成了一項困難的
任務(wù)。
本書對分布式算法這個領(lǐng)域做了全面的介紹，包括為重要的算法和不可能性結(jié)果，且都在一種簡單的自動機理論環(huán)境中呈現(xiàn)。幾乎所有的解都附有數(shù)學(xué)證明（至少是粗略的）。每個算法都根據(jù)精確定義的復(fù)雜度衡量方法進行了分析�？傊@些內(nèi)容為更深入地理解分布式算法打下了牢固的基礎(chǔ)。
本書面向不同層次的讀者。首先，本書可以作為計算機系一年級研究生的教材，尤其適合于對計算機系統(tǒng)、理論或兩者懷有濃厚興趣的學(xué)生學(xué)習(xí)。其次，本書可作為分布式系統(tǒng)設(shè)計人員的短期培訓(xùn)教材。后，它也可作為參考手冊，供設(shè)計人員、學(xué)生、研究人員以及任何對該領(lǐng)域感興趣的人使用。
本書包含了針對很多典型問題的算法，如在幾種不同系統(tǒng)環(huán)境下的一致性（consensus）、通信、資源分配和同步問題。這些算法和相應(yīng)結(jié)果基于分布式環(huán)境的基本假設(shè)來組織。組織的層基于時序模型（timing model）—同步、異步或部分同步；第二層基于進程間的通信機制—共享存儲器或消息傳遞。每種系統(tǒng)模型都用數(shù)章來闡述：每一部分的頭一章提出所述系統(tǒng)類型的形式化模型，余下各章介紹算法和不可能性結(jié)果。從頭至尾，本書進行了嚴(yán)密的論述，然而非常簡明易懂。
由于該領(lǐng)域很廣闊，變化也很快，因此本書并不包羅萬象，只包括根本的結(jié)果。若以復(fù)雜度來衡量，這些結(jié)果并不總是的，但它們比較簡單且能夠闡明重要的通用設(shè)計和推理方法。
本書將會介紹分布式計算領(lǐng)域中許多重要的問題、算法和不可能性結(jié)果。當(dāng)實際系統(tǒng)中出現(xiàn)這些問題的時候，你就能將它們識別出來，并進而利用本書介紹的算法來解決它們，或者應(yīng)用不可能性結(jié)果來證明它們是不可解的。本書還介紹各類系統(tǒng)模型及其能力。這樣一來，你自己就可以設(shè)計出新算法（甚至還可以證明出新的不可能性結(jié)果）。后，本書還會讓你相信，嚴(yán)格推導(dǎo)分布式算法和系統(tǒng)是可行的：形式化建模，給出其所需行為的精確規(guī)格說明，嚴(yán)格證明它們符合規(guī)格說明，確定合適的復(fù)雜度衡量標(biāo)準(zhǔn)以及按照這些標(biāo)準(zhǔn)進行分析。
使用本書
預(yù)備知識 閱讀本書需要對基本的本科離散數(shù)學(xué)（包括數(shù)學(xué)歸納和漸近分析）、一些編程技能以及計算機系統(tǒng)相當(dāng)熟悉。有關(guān)隨機算法的部分還需要基本的概率知識。有關(guān)串行算法及其分析的本科課程對閱讀本書有幫助，但并不是必要的。
章節(jié)關(guān)系 本書的編排原則是使讀者能比較獨立地閱讀不同模型的各章內(nèi)容。各章之間的依賴關(guān)系如圖A所示。例如，如果想盡快了解異步網(wǎng)絡(luò)，就可以跳過第5～7章。還可以只讀算法部分，而不必先閱讀算法所依賴的建模部分。
圖A 各章之間的依賴關(guān)系
帶星號的小節(jié) 在本書中，有幾個小節(jié)的標(biāo)題打了星號。它們的內(nèi)容不太基本或者說比其他部分更深。次閱讀的時候可以忽略這些內(nèi)容而不會有什么影響。
課程 本書的第1版已經(jīng)在MIT（麻省理工學(xué)院）的研究生導(dǎo)論課中用了很多年，并且在一些計算機軟件和應(yīng)用公司的系統(tǒng)設(shè)計師夏季課程中用了三年。本書包括足夠一年課程的內(nèi)容，所以對一些短期課程來說必須有所取舍（注意看章節(jié)之間的關(guān)系）。
例如，在學(xué)習(xí)異步網(wǎng)絡(luò)計算的一個學(xué)期的課程中，可以選擇第3、4、6章，7.2節(jié)，第12章和第14～21章，參考一些有關(guān)建模的章節(jié)（第2、8和9章），并根據(jù)需要加入第10、11和13章中的一些定義。在學(xué)習(xí)分布一致性的一個學(xué)期的課程中，可以選擇第2～9章、第12章、13.1節(jié)，以及第15、17、21、23和25章。還有其他多種可能組合。如果你是這個領(lǐng)域的研究者，你可以用所在領(lǐng)域的更新或者更特別的研究結(jié)果來補充本書。
在為系統(tǒng)設(shè)計師提供的一兩周的短期課程中，可以突出所有章節(jié)的重點，在較高的層次上討論關(guān)鍵結(jié)果和關(guān)鍵證明思想，而無須講解太多細節(jié)。
錯誤 如果在本書中發(fā)現(xiàn)了錯誤，或者對本書有什么建設(shè)性建議，請告訴我。特別歡迎對額外問題的建議。請發(fā)送email到distalgs@theory.lcs.mit.edu。
致謝
我很難一一列舉出所有對本書的出版做出貢獻的人們，因為本書是多年教學(xué)和研究的成果，得到了許多學(xué)生和研究人員的幫助。即使這樣，我還是想盡力而為。
本書是MIT的研究生課程6.852（分布式算法）講稿的終版本。在我早期組織素材的過程中，學(xué)生們學(xué)過這門課。這些學(xué)生在1990年和1992年幫助我完成了講稿的在線版本。有幾位課程助教對我整理筆記給予了極大的幫助，他們是Ken Goldman、Isaac Saias和Boaz Patt-Shamir。助教Jennifer Welch 和Rainer Gawlick也幫了我很大的忙。
許多同事和學(xué)生與我一起研究過本書中的一些結(jié)果，與我一起討論了其他人的工作，這對我充分理解素材幫助很大。其中包括Yehuda Afek、Eshrat Arjomandi、Hagit Attiya、Baruch Awerbuch、Bard Bloom、Alan Borodin、James Burns、Soma Chaudhuri、Brian Coan、Harish Devarajan、Danny Dolev、Cynthia Dwork、Alan Fekete、Michael Fischer、Greg Frederickson、Eli Gafni、Rainer Gawlick、Ken Goldman、Art Harvey、Maurice Herlihy、Paul Jackson、Jon Kleinberg、Leslie Lamport、Butler Lampson、Victor Luchangco、Yishay Mansour、Michael Merritt、Michael Paterson、Boaz Patt-Shamir、Gary Peterson、Shlomit Pinter、Stephen Ponzio、Isaac Saias、Russel Schaffer、Roberto Segala、Nir Shavit、Liuba Shrira、J?rgen S?gaard-Andersen、Eugene Stark、Larry Stockmeyer、Mark Tuttle、Frits Vaandrager、George Varghese、Bill Weihl、Jennifer Welch和Lenore Zuck。尤其感謝其中的兩位：我的導(dǎo)師Michael Fischer和我的學(xué)生Mark Tuttle。從1978年開始，Michael就與我一起致力于研究這個當(dāng)時還很小但看起來很有前途的領(lǐng)域，而Mark Tuttle的碩士論文定義并發(fā)展了I/O自動機模型。
我還要感謝Ajoy Datta、Roberto De Prisco、Alan Fekete、Faith Fich、Rainer Gawlick、Shai Halevi、Jon Kleinberg、Richard Ladner、John Leo、Victor Luchangco、Michael Melliar-Smith、Michael Merritt、Daniele Micciancio、Boaz Patt-Shamir、Anya Pogosyants、Stephen Ponzio、Sergio Rajsbaum、Roberto Segala、Nir Shavit、Mark Smith、Larry Stockmeyer、Mark Tuttle、George Varghese、Jennifer Welch和Lenore Zuck，他們審閱了全書的各部分草稿并提出了很多有用的建議。特別是Ajoy、Faith和George，他們使用本書的早期版本作為教材來教學(xué)，給出了很多寶貴的意見。此外，我要感謝 Joanne Talbot 不厭其煩地排版、畫圖、搜集參考文獻，以及不停地打印文稿等。David Jones也參與了排版工作。在此, 我還要感謝 John Guttag、Paul Penfield 和其他MIT EECS的成員，他們?yōu)槲野才帕藢憰臅r間。Morgan Kaufmann的Bruce Spatz又一次鼓勵并幫助我做這個艱巨的工作，他總能給我正確的建議。在本書后付梓階段，Morgan Kaufmann的Julie Pabst和Diane Cerra給了我很大幫助。同時，也感謝Babel出版社的Ed Sznyter的LATEX技術(shù)。
后也是重要的，我要感謝體貼我的家人Dennis、Patrick和Mary Lynch，他們體諒我為本書所做的一切工作，同時幫我處理了其他的事情。特別感謝Dennis，當(dāng)我把大部分時間花在計算機前時，Dennis在為我準(zhǔn)備美味的海鮮晚餐，甚至把我的浴室和洗衣房翻修
一新！
Nancy A. Lynch
Cambridge, Massachusetts
南希·A. 林奇（Nancy A. Lynch） 麻省理工學(xué)院電子工程和計算機科學(xué)系教授，領(lǐng)導(dǎo)麻省理工學(xué)院的分布式系統(tǒng)理論研究組，在分布式算法和不可能解以及分布式系統(tǒng)的形式化建模和證明方面編寫了大量著作。
目 錄
Distributed Algorithms
譯者序
前言
第1章 引言 1
1.1 相關(guān)主題 1
1.2 我們的觀點 2
1.3 本書內(nèi)容綜述 4
1.4 參考文獻注釋 7
1.5 標(biāo)記 8
部分 同步網(wǎng)絡(luò)算法
第2章 建模I：同步網(wǎng)絡(luò)模型 10
2.1 同步網(wǎng)絡(luò)系統(tǒng) 10
2.2 故障 11
2.3 輸入和輸出 11
2.4 運行 12
2.5 證明方法 12
2.6 復(fù)雜度度量 12
2.7 隨機化 13
2.8 參考文獻注釋 13
第3章 同步環(huán)中的領(lǐng)導(dǎo)者選擇 14
3.1 問題 14
3.2 相同進程的不可能性結(jié)果 15
3.3 基本算法 15
3.4 通信復(fù)雜度為O (nlogn）的算法 17
3.5 非基于比較的算法 20
3.5.1 時間片算法 20
3.5.2 變速算法 20
3.6 基于比較的算法的下界 22
3.7 非基于比較的算法的下界* 26
3.8 參考文獻注釋 27
3.9 習(xí)題 27
第4章 一般同步網(wǎng)絡(luò)中的算法 29
4.1 一般網(wǎng)絡(luò)中的領(lǐng)導(dǎo)者選舉 29
4.1.1 問題 29
4.1.2 簡單的洪泛算法 29
4.1.3 降低通信復(fù)雜度 31
4.2 廣度優(yōu)先搜索 32
4.2.1 問題 33
4.2.2 基本的廣度優(yōu)先搜索算法 33
4.2.3 應(yīng)用 34
4.3 短路徑 35
4.4 小生成樹 36
4.4.1 問題 36
4.4.2 基本定理 36
4.4.3 算法 38
4.5 獨立集 40
4.5.1 問題 40
4.5.2 隨機化算法 41
4.5.3 分析* 42
4.6 參考文獻注釋 44
4.7 習(xí)題 44
第5章 鏈路故障時的分布式
一致性 46
5.1 協(xié)同攻擊問題—確定性版本 46
5.2 協(xié)同攻擊問題—隨機化版本 48
5.2.1 形式化模型 49
5.2.2 算法 49
5.2.3 不一致的下限 52
5.3 參考文獻注釋 54
5.4 習(xí)題 54
第6章 進程故障下的分布式
一致性 56
6.1 問題 57
6.2 針對停止故障的算法 58
6.2.1 基本算法 58
6.2.2 減少通信 60
6.2.3 指數(shù)信息收集算法 61
6.2.4 帶鑒別的Byzantine一致性 66
6.3 針對Byzantine故障的算法 66
6.3.1 舉例 67
6.3.2 Byzantine一致性問題的EIG
算法 68
6.3.3 使用二元Byzantine一致性的
一般Byzantine一致性問題 71
6.3.4 減少通信開銷 72
6.4 Byzantine一致性問題中進程的
個數(shù) 75
6.5 一般圖中的Byzantine一致性
問題 78
6.6 弱Byzantine一致性 81
6.7 有停止故障時的輪數(shù) 82
6.8 參考文獻注釋 88
6.9 習(xí)題 89
第7章 更多的一致性問題 93
7.1 k一致性問題 93
7.1.1 問題 93
7.1.2 算法 94
7.1.3 下界* 95
7.2 近似一致性 103
7.3 提交問題 106
7.3.1 問題 106
7.3.2 兩階段提交 107
7.3.3 三階段提交 108
7.3.4 消息數(shù)的下界 110
7.4 參考文獻注釋 112
7.5 習(xí)題 112
第二部分 異步算法
第8章 建模II：異步系統(tǒng)模型 116
8.1 輸入/輸出自動機 116
8.2 自動機的操作 120
8.2.1 合成 120
8.2.2 隱藏 123
8.3 公平性 123
8.4 問題的輸入和輸出 126
8.5 屬性與證明方法 126
8.5.1 不變式斷言 126
8.5.2 軌跡屬性 126
8.5.3 安全與活性屬性 127
8.5.4 合成推理 129
8.5.5 層次化證明 131
8.6 復(fù)雜度衡量 133
8.7 不可區(qū)分的運行 134
8.8 隨機化 134
8.9 參考文獻注釋 134
8.10 習(xí)題 135
第二部分A?異步共享存儲器算法
第9章 建模III：異步共享存儲器
模型 138
9.1 共享存儲器系統(tǒng) 138
9.2 環(huán)境模型 140
9.3 不可區(qū)分狀態(tài) 141
9.4 共享變量類型 142
9.5 復(fù)雜度衡量 145
9.6 故障 146
9.7 隨機化 146
9.8 參考文獻注釋 146
9.9 習(xí)題 146
第10章 互斥 148
10.1 異步共享存儲器模型 148
10.2 問題 150
10.3 Dijkstra的互斥算法 153
10.3.1 算法 153
10.3.2 正確性證明 156
10.3.3 互斥條件的一個斷言式
證明 158
10.3.4 運行時間 159
10.4 互斥算法的更強條件 160
10.5 鎖定權(quán)互斥算法 162
10.5.1 雙進程算法 162
10.5.2 n進程算法 165
10.5.3 錦標(biāo)賽算法 169
10.6 使用單寫者共享寄存器的算法 172
10.7 Bakery算法 174
10.8 寄存器數(shù)量的下界 176
10.8.1 基本事實 177
10.8.2 單寫者共享變量 177
10.8.3 多寫者共享變量 178
10.9 使用讀–改–寫共享變量的
互斥 182
10.9.1 基本問題 182
10.9.2 有界繞過次數(shù) 183
10.9.3 鎖定權(quán) 188
10.9.4 模擬證明 190
10.10 參考文獻注釋 193
10.11 習(xí)題 193
第11章 資源分配 197
11.1?問題 197
11.1.1 顯式資源規(guī)格說明和互斥規(guī)格說明 197
11.1.2 資源分配問題 198
11.1.3 哲學(xué)家用餐問題 199
11.1.4 解法的受限形式 200
11.2 對稱哲學(xué)家用餐算法的
不存在性 200
11.3 右–左哲學(xué)家用餐算法 202
11.3.1 等待鏈 202
11.3.2 基本算法 203
11.3.3 擴展 205
11.4 隨機哲學(xué)家用餐算法* 208
11.4.1 算法* 208
11.4.2 正確性* 210
11.5 參考文獻注釋 216
11.6 習(xí)題 216
第12章 一致性 218
12.1?問題 218
12.2 使用讀/寫共享存儲器的一致性
問題 220
12.2.1 限制 221
12.2.2 術(shù)語 221
12.2.3 雙價初始化 222
12.2.4 無等待終止性的不可能性 222
12.2.5 單故障終止性的不可能性
結(jié)果 224
12.3 讀/改/寫共享存儲器上的
一致性問題 227
12.4 其他共享存儲器類型 227
12.5 異步共享存儲器系統(tǒng)中的可
計算性* 227
12.6 參考文獻注釋 229
12.7 習(xí)題 229
第13章 原子對象 232
13.1 定義和基本結(jié)論 232
13.1.1 原子對象的定義 233
13.1.2 規(guī)范無等待原子對象
自動機 238
13.1.3 原子對象的合成 240
13.1.4 原子對象和共享變量 240
13.1.5 顯示原子性的一個充分
條件 245
13.2 用讀/寫變量實現(xiàn)讀–改–寫
原子對象 246
13.3 共享存儲器的原子快照 247
13.3.1 問題 247
13.3.2 帶無界變量的一個算法 248
13.3.3 帶有界變量的一個算法* 251
13.4 讀/寫原子對象 254
13.4.1 問題 254
13.4.2 證明原子性的其他引理 255
13.4.3 帶無界變量的一個算法 256
13.4.4 兩個寫者的有界算法 259
13.4.5 使用快照的算法 263
13.5 參考文獻注釋 264
13.6 習(xí)題 265
第二部分B 異步網(wǎng)絡(luò)算法
第14章 建模IV：異步網(wǎng)絡(luò)模型 268
14.1 發(fā)送/接收系統(tǒng) 268
14.1.1 進程 268
14.1.2 發(fā)送/接收通道 269
14.1.3 異步發(fā)送/接收系統(tǒng) 272
14.1.4 使用可靠FIFO通道的發(fā)送/
接收系統(tǒng)的屬性 272
14.1.5 復(fù)雜度度量 273
14.2 廣播系統(tǒng) 274
14.2.1 進程 274
14.2.2 廣播通道 274
14.2.3 異步廣播系統(tǒng) 275
14.2.4 采用可靠廣播通道的廣播系統(tǒng)的屬性 275
14.2.5 復(fù)雜度度量 275
14.3 多播系統(tǒng) 275
14.3.1 進程 276
14.3.2 多播通道 276
14.3.3 異步多播系統(tǒng) 276
14.4 參考文獻注釋 277
14.5 習(xí)題 277
第15章 基本異步網(wǎng)絡(luò)算法 279
15.1 環(huán)中的領(lǐng)導(dǎo)者選舉 279
15.1.1 LCR算法 279
15.1.2 HS算法 283
15.1.3 PetersonLeader算法 283
15.1.4 通信復(fù)雜度的下界 286
15.2 任意網(wǎng)絡(luò)中的領(lǐng)導(dǎo)者選舉 291
15.3 生成樹的構(gòu)造、廣播和斂播 292
15.4 廣度優(yōu)先搜索和短路徑 295
15.5 小生成樹 300
15.5.1 問題描述 301
15.5.2 同步算法：回顧 301
15.5.3 GHS算法：概要 302
15.5.4 更詳細的算法 303
15.5.5 特殊消息 305
15.5.6 復(fù)雜度分析 306
15.5.7 GHS算法的正確性證明 307
15.5.8 簡單“同步”策略 308
15.5.9 應(yīng)用到領(lǐng)導(dǎo)者選舉算法中 308
15.6 參考文獻注釋 309
15.7 習(xí)題 309
第16章 同步器 313
16.1 問題 313
16.2 局部同步器 315
16.3 安全同步器 319
16.3.1 前端自動機 320
16.3.2 通道自動機 321
16.3.3 安全同步器的任務(wù) 321
16.3.4 正確性 322
16.4 安全同步器的實現(xiàn) 322
16.4.1 同步器Alpha 322
16.4.2 同步器Beta 323
16.4.3 同步器Gamma 323
16.5 應(yīng)用 327
16.5.1 領(lǐng)導(dǎo)者選舉 327
16.5.2 廣度優(yōu)先搜索 327
16.5.3 短路徑 328
16.5.4 廣播與確認(rèn) 328
16.5.5 獨立集 328
16.6 時間下界 328
16.7 參考文獻注釋 331
16.8 習(xí)題 331
第17章 共享存儲器與網(wǎng)絡(luò) 333
17.1 從異步共享存儲器模型到異步
網(wǎng)絡(luò)模型的轉(zhuǎn)換 333
17.1.1 問題 333
17.1.2 無故障時的策略 334
17.1.3 容忍進程故障的算法 339
17.1.4 對于n/2故障的不可能性
結(jié)果 342
17.2 從異步網(wǎng)絡(luò)模型到異步共享存儲器模型的轉(zhuǎn)換 343
17.2.1 發(fā)送/接收系統(tǒng) 344
17.2.2 廣播系統(tǒng) 345
17.2.3 異步網(wǎng)絡(luò)中一致性的
不可能性 346
17.3 參考文獻注釋 346
17.4 習(xí)題 346
第18章
書單推薦
