分布式算法（典藏版）

目　　錄
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　更詳細(xì)的算法　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章