目錄
Distributed Algorithms
譯者序
前言
第1章引言1
1.1相關主題1
1.2我們的觀點2
1.3本書內容綜述4
1.4參考文獻注釋7
1.5標記8
部分同步網絡算法
第2章建模I：同步網絡模型10
2.1同步網絡繫統10
2.2故障11
2.3輸入和輸出11
2.4運行12
2.5證明方法12
2.6復雜度度量12
2.7隨機化13
2.8參考文獻注釋13
第3章同步環中的領導者選擇14
3.1問題14
3.2相同進程的不可能性結果15
3.3基本算法15
3.4通信復雜度為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習題27
第4章一般同步網絡中的算法29
4.1一般網絡中的領導者選舉29
4.1.1問題29
4.1.2簡單的洪泛算法29
4.1.3降低通信復雜度31
4.2廣度優先搜索32
4.2.1問題33
4.2.2基本的廣度優先搜索算法33
4.2.3應用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習題44
第5章鏈路故障時的分布式
一致性46
5.1協同攻擊問題—確定性版本46
5.2協同攻擊問題—隨機化版本48
5.2.1形式化模型49
5.2.2算法49
5.2.3不一致的下限52
5.3參考文獻注釋54
5.4習題54
第6章進程故障下的分布式
一致性56
6.1問題57
6.2針對停止故障的算法58
6.2.1基本算法58
6.2.2減少通信60
6.2.3指數信息收集算法61
6.2.4帶鋻別的Byzantine一致性66
6.3針對Byzantine故障的算法66
6.3.1舉例67
6.3.2Byzantine一致性問題的EIG
算法68
6.3.3Byzantine一致性的
一般Byzantine一致性問題71
6.3.4減少通信開銷72
6.4Byzantine一致性問題中進程的
個數75
6.5一般圖中的Byzantine一致性
問題78
6.6弱Byzantine一致性81
6.7有停止故障時的輪數82
6.8參考文獻注釋88
6.9習題89
第7章更多的一致性問題93
7.1k一致性問題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消息數的下界110
7.4參考文獻注釋112
7.5習題112
第二部分異步算法
第8章建模II：異步繫統模型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復雜度衡量133
8.7不可區分的運行134
8.8隨機化134
8.9參考文獻注釋134
8.10習題135
第二部分A?異步共享存儲器算法
第9章建模III：異步共享存儲器
模型138
9.1共享存儲器繫統138
9.2環境模型140
9.3不可區分狀態141
9.4共享變量類型142
9.5復雜度衡量145
9.6故障146
9.7隨機化146
9.8參考文獻注釋146
9.9習題146
第10章互斥148
10.1異步共享存儲器模型148
10.2問題150
10.3Dijkstra的互斥算法153
10.3.1算法153
10.3.2正確性證明156
10.3.3互斥條件的一個斷言式
證明158
10.3.4運行時間159
10.4互斥算法的更強條件160
10.5鎖定權互斥算法162
10.5.1雙進程算法162
10.5.2n進程算法165
10.5.3錦標賽算法169
10.6使用單寫者共享寄存器的算法172
10.7Bakery算法174
10.8寄存器數量的下界176
10.8.1基本事實177
10.8.2單寫者共享變量177
10.8.3多寫者共享變量178
10.9使用讀–改–寫共享變量的
互斥182
10.9.1基本問題182
10.9.2有界繞過次數183
10.9.3鎖定權188
10.9.4模擬證明190
10.10參考文獻注釋193
10.11習題193
第11章資源分配197
11.1?問題197
11.1.1顯式資源規格說明和互斥規格說明197
11.1.2資源分配問題198
11.1.3哲學家用餐問題199
11.1.4解法的受限形式200
11.2對稱哲學家用餐算法的
不存在性200
11.3右–左哲學家用餐算法202
11.3.1等待鏈202
11.3.2基本算法203
11.3.3擴展205
11.4隨機哲學家用餐算法*208
11.4.1算法*208
11.4.2正確性*210
11.5參考文獻注釋216
11.6習題216
第12章一致性218
12.1?問題218
12.2使用讀/寫共享存儲器的一致性
問題220
12.2.1限制221
12.2.2術語221
12.2.3雙價初始化222
12.2.4無等待終止性的不可能性222
12.2.5單故障終止性的不可能性
結果224
12.3讀/改/寫共享存儲器上的
一致性問題227
12.4其他共享存儲器類型227
12.5異步共享存儲器繫統中的可
計算性*227
12.6參考文獻注釋229
12.7習題229
第13章原子對像232
13.1定義和基本結論232
13.1.1原子對像的定義233
13.1.2規範無等待原子對像
自動機238
13.1.3原子對像的合成240
13.1.4原子對像和共享變量240
13.1.5顯示原子性的一個充分
條件245
13.2用讀/寫變量實現讀–改–寫
原子對像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習題265
第二部分B異步網絡算法
第14章建模IV：異步網絡模型268
14.1發送/接收繫統268
14.1.1進程268
14.1.2發送/接收通道269
14.1.3異步發送/接收繫統272
14.1.4使用可靠FIFO通道的發送/
接收繫統的屬性272
14.1.5復雜度度量273
14.2廣播繫統274
14.2.1進程274
14.2.2廣播通道274
14.2.3異步廣播繫統275
14.2.4采用可靠廣播通道的廣播繫統的屬性275
14.2.5復雜度度量275
14.3多播繫統275
14.3.1進程276
14.3.2多播通道276
14.3.3異步多播繫統276
14.4參考文獻注釋277
14.5習題277
第15章基本異步網絡算法279
15.1環中的領導者選舉279
15.1.1LCR算法279
15.1.2HS算法283
15.1.3PetersonLeader算法283
15.1.4通信復雜度的下界286
15.2任意網絡中的領導者選舉291
15.3生成樹的構造、廣播和斂播292
15.4廣度優先搜索和短路徑295
15.5小生成樹300
15.5.1問題描述301
15.5.2同步算法：回顧301
15.5.3GHS算法：概要302
15.5.4更詳細的算法303
15.5.5特殊消息305
15.5.6復雜度分析306
15.5.7GHS算法的正確性證明307
15.5.8簡單“同步”策略308
15.5.9應用到領導者選舉算法中308
15.6參考文獻注釋309
15.7習題309
第16章同步器313
16.1問題313
16.2局部同步器315
16.3安全同步器319
16.3.1前端自動機320
16.3.2通道自動機321
16.3.3安全同步器的任務321
16.3.4正確性322
16.4安全同步器的實現322
16.4.1同步器Alpha322
16.4.2同步器Beta323
16.4.3同步器Gamma323
16.5應用327
16.5.1領導者選舉327
16.5.2廣度優先搜索327
16.5.3短路徑328
16.5.4廣播與確認328
16.5.5獨立集328
16.6時間下界328
16.7參考文獻注釋331
16.8習題331
第17章共享存儲器與網絡333
17.1從異步共享存儲器模型到異步
網絡模型的轉換333
17.1.1問題333
17.1.2無故障時的策略334
17.1.3容忍進程故障的算法339
17.1.4對於n/2故障的不可能性
結果342
17.2從異步網絡模型到異步共享存儲器模型的轉換343
17.2.1發送/接收繫統344
17.2.2廣播繫統345
17.2.3異步網絡中一致性的
不可能性346
17.3參考文獻注釋346
17.4習題346
第18章

前言
Distributed Algorithms
分布式算法是用於解決多個互連處理器運行問題的算法。分布式算法的各部分並發和獨立地運行，每一部分隻承載有限的信息。即使處理器和通信信道以不同的速度運作，或即使某些構件出了故障，這些算法仍然應該正常運行。
分布式算法有廣泛的應用：電信、分布式信息處理、科學計算以及實時進程控制。例如，電話繫統、航班訂票繫統、銀行繫統、全球信息繫統、天氣預報繫統以及飛機和核電站控制繫統都嚴重依賴於分布式算法。很明顯，確保分布式算法準確、高效地運行是非常重要的。然而，由於這種算法的執行環境很復雜，所以設計分布式算法就成了一項困難的
任務。
本書對分布式算法這個領域做了全面的介紹，包括為重要的算法和不可能性結果，且都在一種簡單的自動機理論環境中呈現。幾乎所有的解都附有數學證明（至少是粗略的）。每個算法都根據精確定義的復雜度衡量方法進行了分析。總之，這些內容為更深入地理解分布式算法打下了牢固的基礎。
本書面向不同層次的讀者。首先，本書可以作為計算機繫一年級研究生的教材，尤其適合於對計算機繫統、理論或兩者懷有濃厚興趣的學生學習。其次，本書可作為分布式繫統設計人員的短期培訓教材。後，它也可作為參考手冊，供設計人員、學生、研究人員以及任何對該領域感興趣的人使用。
本書包含了針對很多典型問題的算法，如在幾種不同繫統環境下的一致性（consensus）、通信、資源分配和同步問題。這些算法和相應結果基於分布式環境的基本假設來組織。組織的層基於時序模型（timing model）—同步、異步或部分同步；第二層基於進程間的通信機制—共享存儲器或消息傳遞。每種繫統模型都用數章來闡述：每一部分的頭一章提出所述繫統類型的形式化模型，餘下各章介紹算法和不可能性結果。從頭至尾，本書進行了嚴密的論述，然而非常簡明易懂。
由於該領域很廣闊，變化也很快，因此本書並不包羅萬像，隻包括根本的結果。若以復雜度來衡量，這些結果並不總是的，但它們比較簡單且能夠闡明重要的通用設計和推理方法。
本書將會介紹分布式計算領域中許多重要的問題、算法和不可能性結果。當實際繫統中出現這些問題的時候，你就能將它們識別出來，並進而利用本書介紹的算法來解決它們，或者應用不可能性結果來證明它們是不可解的。本書還介紹各類繫統模型及其能力。這樣一來，你自己就可以設計出新算法（甚至還可以證明出新的不可能性結果）。後，本書還會讓你相信，嚴格推導分布式算法和繫統是可行的：形式化建模，給出其所需行為的精確規格說明，嚴格證明它們符合規格說明，確定合適的復雜度衡量標準以及按照這些標準進行分析。
使用本書
預備知識閱讀本書需要對基本的本科離散數學（包括數學歸納和漸近分析）、一些編程技能以及計算機繫統相當熟悉。有關隨機算法的部分還需要基本的概率知識。有關串行算法及其分析的本科課程對閱讀本書有幫助，但並不是必要的。
章節關繫本書的編排原則是使讀者能比較獨立地閱讀不同模型的各章內容。各章之間的依賴關繫如圖A所示。例如，如果想盡快了解異步網絡，就可以跳過第5～7章。還可以隻讀算法部分，而不必先閱讀算法所依賴的建模部分。

圖A各章之間的依賴關繫
帶星號的小節在本書中，有幾個小節的標題打了星號。它們的內容不太基本或者說比其他部分更深。次閱讀的時候可以忽略這些內容而不會有什麼影響。
課程本書的第1版已經在MIT（麻省理工學院）的研究生導論課中用了很多年，並且在一些計算機軟件和應用公司的繫統設計師夏季課程中用了三年。本書包括足夠一年課程的內容，所以對一些短期課程來說必須有所取舍（注意看章節之間的關繫）。
例如，在學習異步網絡計算的一個學期的課程中，可以選擇第3、4、6章，7.2節，第12章和第14～21章，參考一些有關建模的章節（第2、8和9章），並根據需要加入第10、11和13章中的一些定義。在學習分布一致性的一個學期的課程中，可以選擇第2～9章、第12章、13.1節，以及第15、17、21、23和25章。還有其他多種可能組合。如果你是這個領域的研究者，你可以用所在領域的更新或者更特別的研究結果來補充本書。
在為繫統設計師提供的一兩周的短期課程中，可以突出所有章節的重點，在較高的層次上討論關鍵結果和關鍵證明思想，而無須講解太多細節。
錯誤如果在本書中發現了錯誤，或者對本書有什麼建設性建議，請告訴我。特別歡迎對額外問題的建議。請發送email到distalgs@theory.lcs.mit.edu。
致謝
我很難一一列舉出所有對本書的出版做出貢獻的人們，因為本書是多年教學和研究的成果，得到了許多學生和研究人員的幫助。即使這樣，我還是想盡力而為。
本書是MIT的研究生課程6.852（分布式算法）講稿的終版本。在我早期組織素材的過程中，學生們學過這門課。這些學生在1990年和1992年幫助我完成了講稿的在線版本。有幾位課程助教對我整理筆記給予了極大的幫助，他們是Ken Goldman、Isaac Saias和Boaz Patt-Shamir。助教Jennifer Welch 和Rainer Gawlick也幫了我很大的忙。
許多同事和學生與我一起研究過本書中的一些結果，與我一起討論了其他人的工作，這對我充分理解素材幫助很大。其中包括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。尤其感謝其中的兩位：我的導師Michael Fischer和我的學生Mark Tuttle。從1978年開始，Michael就與我一起致力於研究這個當時還很小但看起來很有前途的領域，而Mark Tuttle的碩士論文定義並發展了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，他們使用本書的早期版本作為教材來教學，給出了很多寶貴的意見。此外，我要感謝 Joanne Talbot 不厭其煩地排版、畫圖、搜集參考文獻，以及不停地打印文稿等。David Jones也參與了排版工作。在此, 我還要感謝 John Guttag、Paul Penfield 和其他MIT EECS的成員，他們為我安排了寫書的時間。Morgan Kaufmann的Bruce Spatz又一次鼓勵並幫助我做這個艱巨的工作，他總能給我正確的建議。在本書後付梓階段，Morgan Kaufmann的Julie Pabst和Diane Cerra給了我很大幫助。同時，也感謝Babel出版社的Ed Sznyter的LATEX技術。
後也是重要的，我要感謝體貼我的家人Dennis、Patrick和Mary Lynch，他們體諒我為本書所做的一切工作，同時幫我處理了其他的事情。特別感謝Dennis，當我把大部分時間花在計算機前時，Dennis在為我準備美味的海鮮晚餐，甚至把我的浴室和洗衣房翻修
一新！

Nancy A. Lynch
Cambridge, Massachusetts