分布式算法

出版者的話
專家指導(dǎo)委員會
譯者序
前言
第1章   引言 1
1.1   相關(guān)主題 1
1.2   我們的觀點(diǎn) 2
1.3   本書內(nèi)容綜述 3
1.4   參考文獻(xiàn)注釋 7
1.5   標(biāo)記 7
第一部分   同步網(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   運(yùn)行 11
2.5   證明方法 12
2.6   復(fù)雜度度量 12
2.7   隨機(jī)化 12
2.8   參考文獻(xiàn)注釋 13
第3章   同步環(huán)中的領(lǐng)導(dǎo)者選擇 14
3.1   問題 14
3.2   相同進(jìn)程的不可能性結(jié)果 14
3.3   基本算法 15
3.4   通信復(fù)雜度為O(n log n)的算法 17
3.5   非基于比較的算法 19
3.5.1   時間片算法 20
3.5.2   變速算法 20
3.6   基于比較的算法的下界 21
3.7   非基于比較的算法的下界* 25
3.8   參考文獻(xiàn)注釋 26
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   問題 32
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   算法 37
4.5   最大獨(dú)立集 39
4.5.1   問題 40
4.5.2   隨機(jī)化算法 40
4.5.3   分析* 42
4.6   參考文獻(xiàn)注釋 43
4.7   習(xí)題 43
第5章   鏈路故障時的分布式一致性 46
5.1   協(xié)同攻擊問題—確定性版本 46
5.2   協(xié)同攻擊問題—隨機(jī)化版本 48
5.2.1   形式化模型 49
5.2.2   算法 49
5.2.3   不一致的下限 52
5.3   參考文獻(xiàn)注釋 54
5.4   習(xí)題 54
第6章   進(jìn)程故障下的分布式一致性 56
6.1   問題 56
6.2   針對停止故障的算法 58
6.2.1   基本算法 58
6.2.2   減少通信 59
6.2.3   指數(shù)信息收集算法 61
6.2.4   帶鑒別的Byzantine一致性 66
6.3   針對Byzantine故障的算法 66
6.3.1   舉例 66
6.3.2   Byzantine一致性問題的EIG算法 68
6.3.3   使用二元Byzantine一致的一般
的Byzantine一致性問題 71
6.3.4   減少通信開銷 72
6.4   Byzantine一致性問題中進(jìn)程的個數(shù) 74
6.5   一般圖中的Byzantine一致性問題 78
6.6   弱Byzantine一致性 81
6.7   有停止故障時的輪數(shù) 82
6.8   參考文獻(xiàn)注釋 88
6.9   習(xí)題 89
第7章   更多的一致性問題 93
7.1   k一致性問題 93
7.1.1   問題 93
7.1.2   算法 93
7.1.3   下界* 95
7.2   近似一致性 102
7.3   提交問題 105
7.3.1   問題 105
7.3.2   兩階段提交 106
7.3.3   三階段提交 107
7.3.4   消息數(shù)的下界 109
7.4   參考文獻(xiàn)注釋 111
7.5   習(xí)題 111
第二部分   異步算法
第8章   建模II：異步系統(tǒng)模型 114
8.1   輸入/輸出自動機(jī) 114
8.2   自動機(jī)的操作 118
8.2.1   合成 118
8.2.2   隱藏 121
8.3   公平性 121
8.4   問題的輸入和輸出 123
8.5   屬性與證明方法 124
8.5.1   不變式斷言 124
8.5.2   軌跡屬性 124
8.5.3   安全與活性屬性 125
8.5.4   合成推理 126
8.5.5   層次化證明 128
8.6   復(fù)雜度衡量 130
8.7   不可區(qū)分運(yùn)行 131
8.8   隨機(jī)化 131
8.9   參考文獻(xiàn)注釋 131
8.10   習(xí)題 132
第二部分A   異步共享存儲器算法
第9章   建模III：異步共享存儲器模型 136
9.1   共享存儲器系統(tǒng) 136
9.2   環(huán)境模型 138
9.3   不可區(qū)分狀態(tài) 140
9.4   共享變量類型 140
9.5   復(fù)雜度衡量 144
9.6   故障 144
9.7   隨機(jī)化 145
9.8   參考文獻(xiàn)注釋 145
9.9   習(xí)題 145
第10章   互斥 146
10.1   異步共享存儲器模型 146
10.2   問題 148
10.3   Dijkstra的互斥算法 151
10.3.1   算法 151
10.3.2   正確性證明 154
10.3.3   互斥條件的一個斷言證明 156
10.3.4   運(yùn)行時間 157
10.4   互斥算法的更強(qiáng)條件 158
10.5   鎖定權(quán)互斥算法 159
10.5.1   雙進(jìn)程算法 159
10.5.2   n進(jìn)程算法 163
10.5.3   錦標(biāo)賽算法 167
10.6   使用單寫者共享存儲器的算法 170
10.7   Bakery算法 171
10.8   寄存器數(shù)量的下界 173
10.8.1   基本事實(shí) 174
10.8.2   單寫者共享變量 175
10.8.3   多寫者共享變量 175
10.9   使用讀-改-寫共享變量的互斥 179
10.9.1   基本問題 179
10.9.2   有界繞過次數(shù) 180
10.9.3   鎖定權(quán) 185
10.9.4   模擬證明 187
10.10   參考文獻(xiàn)注釋 189
10.11   習(xí)題 190
第11章   資源分配 194
11.1   問題 194
11.1.1   顯式資源說明和互斥說明 194
11.1.2   資源分配問題 195
11.1.3   哲學(xué)家用餐問題 196
11.1.4   解法的受限形式 197
11.2   對稱哲學(xué)家用餐算法的不存在性 197
11.3   右-左哲學(xué)家用餐算法 199
11.3.1   等待鏈 199
11.3.2   基本算法 200
11.3.3   擴(kuò)展 202
11.4   哲學(xué)家用餐隨機(jī)算法* 204
11.4.1   算法* 205
11.4.2   正確性* 207
11.5   參考文獻(xiàn)注釋 212
11.6   習(xí)題 213
第12章   一致性 215
12.1   問題 215
12.2   使用讀/寫共享存儲器的一致性 217
12.2.1   限制 218
12.2.2   術(shù)語 218
12.2.3   雙價(jià)初始化 218
12.2.4   無等待終止的不可能性 219
12.2.5   單故障終止的不可能性結(jié)果 221
12.3   讀/改/寫共享存儲器上的一致性
問題 223
12.4   其他共享存儲器類型 224
12.5   異步共享存儲器系統(tǒng)中的可計(jì)算性* 224
12.6   參考文獻(xiàn)注釋 225
12.7   習(xí)題 226
第13章   原子對象 229
13.1   定義和基本結(jié)論 229
13.1.1   原子對象的定義 229
13.1.2   規(guī)范無等待原子對象自動機(jī) 235
13.1.3   原子對象的合成 237
13.1.4   原子對象和共享變量 237
13.1.5   顯示原子性的一個充分條件 241
13.2   用讀/寫變量實(shí)現(xiàn)讀-改-寫原子對象 242
13.3   共享存儲器的原子快照 243
13.3.1   問題 243
13.3.2   帶無界變量的一個算法 244
13.3.3   帶有界變量的一個算法* 247
13.4   讀/寫原子對象 250
13.4.1   問題 250
13.4.2   證明原子性的其他引理 250
13.4.3   帶無界變量的一個算法 251
13.4.4   兩個寫者的有界算法 254
13.4.5   使用快照的算法 258
13.5   參考文獻(xiàn)注釋 259
13.6   習(xí)題 260
第二部分B   異步網(wǎng)絡(luò)算法
第14章   建模IV：異步網(wǎng)絡(luò)模型 264
14.1   發(fā)送/接收系統(tǒng) 264
14.1.1   進(jìn)程 264
14.1.2   發(fā)送/接收通道 264
14.1.3   異步發(fā)送/接收系統(tǒng) 268
14.1.4   使用可靠FIFO通道的發(fā)送/
接收系統(tǒng)的特征 268
14.1.5   復(fù)雜度度量 269
14.2   廣播系統(tǒng) 269
14.2.1   進(jìn)程 269
14.2.2   廣播通道 270
14.2.3   異步廣播系統(tǒng) 270
14.2.4   采用可靠廣播通道的廣播系統(tǒng)
的特征 270
14.2.5   復(fù)雜度度量 271
14.3   多播系統(tǒng) 271
14.3.1   進(jìn)程 271
14.3.2   多播通道 271
14.3.3   異步多播系統(tǒng) 272
14.4   參考文獻(xiàn)注釋 272
14.5   習(xí)題 272
第15章   基本異步網(wǎng)絡(luò)算法 274
15.1   環(huán)中的領(lǐng)導(dǎo)者選舉 274
15.1.1   LCR算法 275
15.1.2   HS算法 278
15.1.3   Peterson Leader算法 278
15.1.4   通信復(fù)雜度的下界 281
15.2   任意網(wǎng)絡(luò)中的領(lǐng)導(dǎo)者選舉 286
15.3   生成樹的構(gòu)造. 廣播和斂播 287
15.4   廣度優(yōu)先搜索和最短路徑 290
15.5   最小生成樹 295
15.5.1   問題描述 295
15.5.2   同步算法：回顧 296
15.5.3   GHS算法：概要 296
15.5.4   更詳細(xì)的算法 297
15.5.5   特殊消息 299
15.5.6   復(fù)雜度分析 301
15.5.7   GHS算法的正確性證明 301
15.5.8   簡單“同步”策略 302
15.5.9   應(yīng)用到領(lǐng)導(dǎo)者選舉算法中 302
15.6   參考文獻(xiàn)注釋 303
15.7   習(xí)題 303
第16章   同步器 307
16.1   問題 307
16.2   局部同步器 309
16.3   安全同步器 313
16.3.1   前端自動機(jī) 314
16.3.2   通道自動機(jī) 315
16.3.3   安全同步器 315
16.3.4   正確性 315
16.4   安全同步器的實(shí)現(xiàn) 316
16.4.1   同步器Alpha 316
16.4.2   同步器Beta 317
16.4.3   同步器Gamma 317
16.5   應(yīng)用 320
16.5.1   領(lǐng)導(dǎo)者選舉 321
16.5.2   深度優(yōu)先搜索 321
16.5.3   最短路徑 321
16.5.4   廣播與確認(rèn) 321
16.5.5   最大獨(dú)立集 321
16.6   時間下界 321
16.7   參考文獻(xiàn)注釋 324
16.8   習(xí)題 324
第17章   共享存儲器與網(wǎng)絡(luò) 326
17.1   從共享存儲器模型到網(wǎng)絡(luò)模型
的轉(zhuǎn)換 326
17.1.1   問題 326
17.1.2   無故障時的策略 327
17.1.3   容忍進(jìn)程故障的算法 332
17.1.4   對于n/2故障的不可能性結(jié)果 335
17.2   從網(wǎng)絡(luò)模型轉(zhuǎn)換到共享存儲器模型 336
17.2.1   發(fā)送/接收系統(tǒng) 336
17.2.2   廣播系統(tǒng) 338
17.2.3   異步網(wǎng)絡(luò)中一致性的不可能性 338
17.3   參考文獻(xiàn)注釋 339
17.4   習(xí)題 339
第18章   邏輯時間 341
18.1   異步網(wǎng)絡(luò)的邏輯時間 341
18.1.1   發(fā)送/接收系統(tǒng) 341
18.1.2   廣播系統(tǒng) 343
18.2   使用邏輯時間的異步算法 344
18.2.1   時鐘的走動 344
18.2.2   延遲未來事件 345
18.3   應(yīng)用 346
18.3.1   銀行系統(tǒng) 346
18.3.2   全局快照 348
18.3.3   模擬一臺單狀態(tài)機(jī)器 349
18.4   從實(shí)際時間算法到邏輯時間算法
的變換* 352
18.5   參考文獻(xiàn)注釋 352
18.6   習(xí)題 353
第19章   一致全局快照和穩(wěn)定屬性檢測 355
19.1   發(fā)散算法的終止檢測 355
19.1.1   問題 355
19.1.2   DijkstraScholten算法 356
19.2   一致全局快照 360
19.2.1   問題 360
19.2.2   ChandyLamport算法 361
19.2.3   應(yīng)用 364
19.3   參考文獻(xiàn)注釋 366
19.4   習(xí)題 367
第20章   網(wǎng)絡(luò)資源分配 369
20.1   互斥 369
20.1.1   問題 369
20.1.2   模擬共享存儲器 370
20.1.3   循環(huán)令牌算法 370
20.1.4   基于邏輯時間的算法 372
20.1.5   LogicalTimeME算法的改進(jìn) 374
20.2   通用資源分配 376
20.2.1   問題 376
20.2.2   著色算法 377
20.2.3   基于邏輯時間的算法 377
20.2.4   無環(huán)有向圖算法 378
20.2.5   哲學(xué)家飲水* 379
20.3   參考文獻(xiàn)注釋 383
20.4   習(xí)題 383
第21章   帶進(jìn)程故障的異步網(wǎng)絡(luò)計(jì)算 386
21.1   網(wǎng)絡(luò)模型 386
21.2   有故障環(huán)境中一致性的不可能性 387
21.3   隨機(jī)算法 388
21.4   故障檢測器 390
21.5   k一致性 393
21.6   近似一致性 394
21.7   異步網(wǎng)絡(luò)的計(jì)算能力* 395
21.8   參考文獻(xiàn)注釋 396
21.9   習(xí)題 396
第22章   數(shù)據(jù)鏈路協(xié)議 399
22.1   問題闡述 399
22.2   Stenning協(xié)議 400
22.3   位變換協(xié)議 403
22.4   可重排序的有界標(biāo)志協(xié)議 406
22.4.1   關(guān)于重排序和復(fù)制的不可能
性結(jié)論 407
22.4.2   容許丟失和重排序的有界標(biāo)
志協(xié)議 408
22.4.3   不存在容許消息丟失和重排序
的高效協(xié)議 412
22.5   容許進(jìn)程崩潰 414
22.5.1   簡單的不可能性結(jié)論 415
22.5.2   更復(fù)雜的不可能性結(jié)論 415
22.5.3   實(shí)用的協(xié)議 418
22.6   參考文獻(xiàn)注釋 423
22.7   習(xí)題 423
第三部分   部分同步算法
第23章   建模V:   部分同步系統(tǒng)模型 428
23.1   MMT   定時自動機(jī) 428
23.1.1   基本定義 428
23.1.2   操作 432
23.2   通用定時自動機(jī) 434
23.2.1   基本定義 434
23.2.2   將MMT自動機(jī)轉(zhuǎn)化為通用定時
自動機(jī) 437
23.2.3   操作 440
23.3   屬性和證明方法 441
23.3.1   不變式 441
23.3.2   定時軌跡屬性 443
23.3.3   模擬 444
23.4   構(gòu)造共享存儲器和網(wǎng)絡(luò)系統(tǒng)的模型 449
23.4.1   共享存儲器系統(tǒng) 449
23.4.2   網(wǎng)絡(luò) 449
23.5   參考文獻(xiàn)注釋 449
23.6   習(xí)題 450
第24章   部分同步的互斥 452
24.1   問題 452
24.2   單寄存器算法 453
24.3   對時間故障的回復(fù)性 459
24.4   不可能性結(jié)果 461
24.4.1   時間下界 462
24.4.2   最終時間界限的不可能性結(jié)果* 462
24.5   參考文獻(xiàn)注釋 463
24.6   習(xí)題 463
第25章   部分同步的一致性 466
25.1   問題 466
25.2   故障檢測器 467
25.3   基本結(jié)論 468
25.3.1   上界 468
25.3.2   下界 469
25.4   有效算法 470
25.4.1   算法 471
25.4.2   安全屬性 472
25.4.3   活性和復(fù)雜度 473
25.5   涉及時間不確定性的下界* 475
25.6   其他結(jié)果* 480
25.6.1   同步進(jìn)程. 異步通道* 480
25.6.2   異步進(jìn)程. 同步通道* 481
25.6.3   最終時間界限* 481
25.7   小結(jié) 483
25.8   參考文獻(xiàn)注釋 483
25.9   習(xí)題 483
參考文獻(xiàn) 486
索引 512