分佈式算法（典藏版） Distributed Algorithms

本書對分佈式算法進行了全面介紹，包括同步模型、異步模型和部分同步模型，針對這些模型討論互斥性、
一致性和通信問題，為設計、實現和分析分佈式算法提供了藍圖。
本書對分佈式算法領域的許多經典問題給出了多種解決算法或者不可能性結果，
絕大部分的算法附有詳細的證明過程，並且有精確的複雜度衡量。
本書還配有大量習題，並在每章後列出了詳細的參考文獻。

目　　錄
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.2 Byzantine一致性問題的EIG
算法68
6.3.3 使用二元Byzantine一致性的
一般Byzantine一致性問題71
6.3.4 減少通信開銷72
6.4 Byzantine一致性問題中進程的
個數75
6.5 一般圖中的Byzantine一致性
問題78
6.6 弱Byzantine一致性81
6.7 有停止故障時的輪數82
6.8 參考文獻註釋88
6.9 習題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 消息數的下界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.3 Dijkstra的互斥算法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.2 n進程算法165
10.5.3 錦標賽算法169
10.6 使用單寫者共享寄存器的算法172
10.7 Bakery算法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.1 LCR算法279
15.1.2 HS算法283
15.1.3 PetersonLeader算法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.3 GHS算法：概要302
15.5.4 更詳細的算法303
15.5.5 殊消息305
15.5.6 複雜度分析306
15.5.7 GHS算法的正確性證明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 同步器Alpha 322
16.4.2 同步器Beta 323
16.4.3 同步器Gamma 323
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章