分布式算法（典藏版）

目　　錄
Distributed Algorithms
譯者序
前言
第1章　引言　1
1.1　相關(guān)主題　1
1.2　我們的觀點(diǎn)　2
1.3　本書(shū)內(nèi)容綜述　4
1.4　參考文獻(xiàn)注釋　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　運(yùn)行　12
2.5　證明方法　12
2.6　復(fù)雜度度量　12
2.7　隨機(jī)化　13
2.8　參考文獻(xiàn)注釋　13
第3章　同步環(huán)中的領(lǐng)導(dǎo)者選擇　14
3.1　問(wèn)題　14
3.2　相同進(jìn)程的不可能性結(jié)果　15
3.3　基本算法　15
3.4　通信復(fù)雜度為O (nlogn）的算法　17
3.5　非基于比較的算法　20
3.5.1　時(shí)間片算法　20
3.5.2　變速算法　20
3.6　基于比較的算法的下界　22
3.7　非基于比較的算法的下界*　26
3.8　參考文獻(xiàn)注釋　27
3.9　習(xí)題　27
第4章　一般同步網(wǎng)絡(luò)中的算法　29
4.1　一般網(wǎng)絡(luò)中的領(lǐng)導(dǎo)者選舉　29
4.1.1　問(wèn)題　29
4.1.2　簡(jiǎn)單的洪泛算法　29
4.1.3　降低通信復(fù)雜度　31
4.2　廣度優(yōu)先搜索　32
4.2.1　問(wèn)題　33
4.2.2　基本的廣度優(yōu)先搜索算法　33
4.2.3　應(yīng)用　34
4.3　短路徑　35
4.4　小生成樹(shù)　36
4.4.1　問(wèn)題　36
4.4.2　基本定理　36
4.4.3　算法　38
4.5　獨(dú)立集　40
4.5.1　問(wèn)題　40
4.5.2　隨機(jī)化算法　41
4.5.3　分析*　42
4.6　參考文獻(xiàn)注釋　44
4.7　習(xí)題　44
第5章　鏈路故障時(shí)的分布式
一致性　46
5.1　協(xié)同攻擊問(wèn)題—確定性版本　46
5.2　協(xié)同攻擊問(wèn)題—隨機(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　問(wèn)題　57
6.2　針對(duì)停止故障的算法　58
6.2.1　基本算法　58
6.2.2　減少通信　60
6.2.3　指數(shù)信息收集算法　61
6.2.4　帶鑒別的Byzantine一致性　66
6.3　針對(duì)Byzantine故障的算法　66
6.3.1　舉例　67
6.3.2　Byzantine一致性問(wèn)題的EIG
算法　68
6.3.3　使用二元Byzantine一致性的
一般Byzantine一致性問(wèn)題　71
6.3.4　減少通信開(kāi)銷(xiāo)　72
6.4　Byzantine一致性問(wèn)題中進(jìn)程的
個(gè)數(shù)　75
6.5　一般圖中的Byzantine一致性
問(wèn)題　78
6.6　弱Byzantine一致性　81
6.7　有停止故障時(shí)的輪數(shù)　82
6.8　參考文獻(xiàn)注釋　88
6.9　習(xí)題　89
第7章　更多的一致性問(wèn)題　93
7.1　k一致性問(wèn)題　93
7.1.1　問(wèn)題　93
7.1.2　算法　94
7.1.3　下界*　95
7.2　近似一致性　103
7.3　提交問(wèn)題　106
7.3.1　問(wèn)題　106
7.3.2　兩階段提交　107
7.3.3　三階段提交　108
7.3.4　消息數(shù)的下界　110
7.4　參考文獻(xiàn)注釋　112
7.5　習(xí)題　112
第二部分　異步算法
第8章　建模II：異步系統(tǒng)模型　116
8.1　輸入/輸出自動(dòng)機(jī)　116
8.2　自動(dòng)機(jī)的操作　120
8.2.1　合成　120
8.2.2　隱藏　123
8.3　公平性　123
8.4　問(wèn)題的輸入和輸出　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ū)分的運(yùn)行　134
8.8　隨機(jī)化　134
8.9　參考文獻(xiàn)注釋　134
8.10　習(xí)題　135
第二部分A?異步共享存儲(chǔ)器算法
第9章　建模III：異步共享存儲(chǔ)器
模型　138
9.1　共享存儲(chǔ)器系統(tǒng)　138
9.2　環(huán)境模型　140
9.3　不可區(qū)分狀態(tài)　141
9.4　共享變量類(lèi)型　142
9.5　復(fù)雜度衡量　145
9.6　故障　146
9.7　隨機(jī)化　146
9.8　參考文獻(xiàn)注釋　146
9.9　習(xí)題　146
第10章　互斥　148
10.1　異步共享存儲(chǔ)器模型　148
10.2　問(wèn)題　150
10.3　Dijkstra的互斥算法　153
10.3.1　算法　153
10.3.2　正確性證明　156
10.3.3　互斥條件的一個(gè)斷言式
證明　158
10.3.4　運(yùn)行時(shí)間　159
10.4　互斥算法的更強(qiáng)條件　160
10.5　鎖定權(quán)互斥算法　162
10.5.1　雙進(jìn)程算法　162
10.5.2　n進(jìn)程算法　165
10.5.3　錦標(biāo)賽算法　169
10.6　使用單寫(xiě)者共享寄存器的算法　172
10.7　Bakery算法　174
10.8　寄存器數(shù)量的下界　176
10.8.1　基本事實(shí)　177
10.8.2　單寫(xiě)者共享變量　177
10.8.3　多寫(xiě)者共享變量　178
10.9　使用讀–改–寫(xiě)共享變量的
互斥　182
10.9.1　基本問(wèn)題　182
10.9.2　有界繞過(guò)次數(shù)　183
10.9.3　鎖定權(quán)　188
10.9.4　模擬證明　190
10.10　參考文獻(xiàn)注釋　193
10.11　習(xí)題　193
第11章　資源分配　197
11.1?問(wèn)題　197
11.1.1　顯式資源規(guī)格說(shuō)明和互斥規(guī)格說(shuō)明　197
11.1.2　資源分配問(wèn)題　198
11.1.3　哲學(xué)家用餐問(wèn)題　199
11.1.4　解法的受限形式　200
11.2　對(duì)稱哲學(xué)家用餐算法的
不存在性　200
11.3　右–左哲學(xué)家用餐算法　202
11.3.1　等待鏈　202
11.3.2　基本算法　203
11.3.3　擴(kuò)展　205
11.4　隨機(jī)哲學(xué)家用餐算法*　208
11.4.1　算法*　208
11.4.2　正確性*　210
11.5　參考文獻(xiàn)注釋　216
11.6　習(xí)題　216
第12章　一致性　218
12.1?問(wèn)題　218
12.2　使用讀/寫(xiě)共享存儲(chǔ)器的一致性
問(wèn)題　220
12.2.1　限制　221
12.2.2　術(shù)語(yǔ)　221
12.2.3　雙價(jià)初始化　222
12.2.4　無(wú)等待終止性的不可能性　222
12.2.5　單故障終止性的不可能性
結(jié)果　224
12.3　讀/改/寫(xiě)共享存儲(chǔ)器上的
一致性問(wèn)題　227
12.4　其他共享存儲(chǔ)器類(lèi)型　227
12.5　異步共享存儲(chǔ)器系統(tǒng)中的可
計(jì)算性*　227
12.6　參考文獻(xiàn)注釋　229
12.7　習(xí)題　229
第13章　原子對(duì)象　232
13.1　定義和基本結(jié)論　232
13.1.1　原子對(duì)象的定義　233
13.1.2　規(guī)范無(wú)等待原子對(duì)象
自動(dòng)機(jī)　238
13.1.3　原子對(duì)象的合成　240
13.1.4　原子對(duì)象和共享變量　240
13.1.5　顯示原子性的一個(gè)充分
條件　245
13.2　用讀/寫(xiě)變量實(shí)現(xiàn)讀–改–寫(xiě)
原子對(duì)象　246
13.3　共享存儲(chǔ)器的原子快照　247
13.3.1　問(wèn)題　247
13.3.2　帶無(wú)界變量的一個(gè)算法　248
13.3.3　帶有界變量的一個(gè)算法*　251
13.4　讀/寫(xiě)原子對(duì)象　254
13.4.1　問(wèn)題　254
13.4.2　證明原子性的其他引理　255
13.4.3　帶無(wú)界變量的一個(gè)算法　256
13.4.4　兩個(gè)寫(xiě)者的有界算法　259
13.4.5　使用快照的算法　 263
13.5　參考文獻(xiàn)注釋　264
13.6　習(xí)題　265
第二部分B　異步網(wǎng)絡(luò)算法
第14章　建模IV：異步網(wǎng)絡(luò)模型　268
14.1　發(fā)送/接收系統(tǒng)　268
14.1.1　進(jìn)程　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　進(jìn)程　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　進(jìn)程　276
14.3.2　多播通道　276
14.3.3　異步多播系統(tǒng)　276
14.4　參考文獻(xiàn)注釋　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　生成樹(shù)的構(gòu)造、廣播和斂播　292
15.4　廣度優(yōu)先搜索和短路徑　295
15.5　小生成樹(shù)　300
15.5.1　問(wèn)題描述　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　簡(jiǎn)單“同步”策略　308
15.5.9　應(yīng)用到領(lǐng)導(dǎo)者選舉算法中　308
15.6　參考文獻(xiàn)注釋　309
15.7　習(xí)題　309
第16章　同步器　313
16.1　問(wèn)題　313
16.2　局部同步器　315
16.3　安全同步器　319
16.3.1　前端自動(dòng)機(jī)　320
16.3.2　通道自動(dòng)機(jī)　321
16.3.3　安全同步器的任務(wù)　321
16.3.4　正確性　322
16.4　安全同步器的實(shí)現(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　獨(dú)立集　328
16.6　時(shí)間下界　328
16.7　參考文獻(xiàn)注釋　331
16.8　習(xí)題　331
第17章　共享存儲(chǔ)器與網(wǎng)絡(luò)　333
17.1　從異步共享存儲(chǔ)器模型到異步
網(wǎng)絡(luò)模型的轉(zhuǎn)換　333
17.1.1　問(wèn)題　333
17.1.2　無(wú)故障時(shí)的策略　334
17.1.3　容忍進(jìn)程故障的算法　339
17.1.4　對(duì)于n/2故障的不可能性
結(jié)果　342
17.2　從異步網(wǎng)絡(luò)模型到異步共享存儲(chǔ)器模型的轉(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　參考文獻(xiàn)注釋　346
17.4　習(xí)題　346
第18章