鏈接：https://pan.baidu.com/s/1q__0sA9cgUxMLwkLR3FXfg?pwd=1igc?

提取碼：1igc

本書對分布式算法進(jìn)行了全面介紹，括同步模型、異步模型和分同步模型，針對這些模型討論互斥性、一性和通信問題，為設(shè)計、實現(xiàn)和分析分布式算法提供了藍(lán)圖。本書對分布式算法領(lǐng)域的許多問題給出了多種解決算法或者不可能性結(jié)果，大分的算法附有詳細(xì)的證明過程，并且有jing確的復(fù)雜度衡量。本書還配有大量題，并在每章后列出了詳細(xì)的參考文獻(xiàn)。本書可作為高等院校計算機(jī)業(yè)的研究生教材，尤其適合對計算機(jī)理論或體系結(jié)構(gòu)感興趣的學(xué)生學(xué)，還適合分布式領(lǐng)域的設(shè)計人員和研究人員參考。

Distributed Algorithms

譯者序

前言

第1章　引言　1

1.1　相關(guān)主題　1

1.2　我們的觀點　2

1.3　本書內(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　運行　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　問題　14

3.2　相同進(jìn)程的不可能性結(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　參考文獻(xiàn)注釋　27

3.9　題　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　廣度先搜索　32

4.2.1　問題　33

4.2.2　基本的廣度先搜索算法　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　隨機(jī)化算法　41

4.5.3　分析*　42

4.6　參考文獻(xiàn)注釋　44

4.7　題　44

第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　題　54

第6章　進(jìn)程故障下的分布式

一性　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一性問題中進(jìn)程的

個數(shù)　75

6.5　一般圖中的Byzantine一性

問題　78

6.6　弱Byzantine一性　81

6.7　有停止故障時的輪數(shù)　82

6.8　參考文獻(xiàn)注釋　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　消息數(shù)的下界　110

7.4　參考文獻(xiàn)注釋　112

7.5　題　112

第二分　異步算法

第8章　建模II：異步系統(tǒng)模型　116

8.1　輸入/輸出自動機(jī)　116

8.2　自動機(jī)的作　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　隨機(jī)化　134

8.9　參考文獻(xiàn)注釋　134

8.10　題　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　隨機(jī)化　146

9.8　參考文獻(xiàn)注釋　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　互斥算法的更強(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　使用單寫者共享寄存器的算法　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　參考文獻(xiàn)注釋　193

10.11　題　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　擴(kuò)展　205

11.4　隨機(jī)哲學(xué)家用餐算法*　208

11.4.1　算法*　208

11.4.2　正確性*　210

11.5　參考文獻(xiàn)注釋　216

11.6　題　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　參考文獻(xiàn)注釋　229

12.7　題　229

第13章　原子對象　232

13.1　定義和基本結(jié)論　232

13.1.1　原子對象的定義　233

13.1.2　規(guī)范無等待原子對象

自動機(jī)　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　參考文獻(xiàn)注釋　264

13.6　題　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　題　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　廣度先搜索和短路徑　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　參考文獻(xiàn)注釋　309

15.7　題　309

第16章　同步器　313

16.1　問題　313

16.2　局同步器　315

16.3　同步器　319

16.3.1　前端自動機(jī)　320

16.3.2　通道自動機(jī)　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　廣度先搜索　327

16.5.3　短路徑　328

16.5.4　廣播與確認(rèn)　328

16.5.5　大獨立集　328

16.6　時間下界　328

16.7　參考文獻(xiàn)注釋　331

16.8　題　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　容忍進(jìn)程故障的算法　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　參考文獻(xiàn)注釋　346

17.4　題　346

第18章　邏輯時間　348

18.1　異步網(wǎng)絡(luò)的邏輯時間　348

18.1.1　發(fā)送/接收系統(tǒng)　348

18.1.2　廣播系統(tǒng)　350

18.2　使用邏輯時間的異步算法　351

18.2.1　時鐘的走動　351

18.2.2　延遲未來事件　352

18.3　應(yīng)用　353

18.3.1　銀行系統(tǒng)　353

18.3.2　全局快照　355

18.3.3　模擬一臺單狀態(tài)機(jī)　356

18.4　從實際時間算法到邏輯時間算法的變換*　359

18.5　參考文獻(xiàn)注釋　359

18.6　題　360

第19章　一全局快照和穩(wěn)定屬性

檢測　362

19.1　發(fā)散算法的止檢測　362

19.1.1　問題　362

19.1.2　DijkstraScholten算法　363

19.2　一全局快照　367

19.2.1　問題　367

19.2.2　ChandyLamport算法　368

19.2.3　應(yīng)用　372

19.3　參考文獻(xiàn)注釋　374

19.4　題　374

第20章　網(wǎng)絡(luò)資源分配　376

20.1　互斥　376

20.1.1　問題　376

20.1.2　模擬共享存儲器　377

20.1.3　循環(huán)令牌算法　377

20.1.4　基于邏輯時間的算法　379

20.1.5　LogicalTimeME算法的改進(jìn)　381

20.2　通用資源分配　383

20.2.1　問題　383

20.2.2　著色算法　384

20.2.3　基于邏輯時間的算法　385

20.2.4　無環(huán)有向圖算法　385

20.2.5　哲學(xué)家飲水*　386

20.3　參考文獻(xiàn)注釋　390

20.4　題　391

第21章　帶進(jìn)程故障的異步網(wǎng)絡(luò)

計算　393

21.1　網(wǎng)絡(luò)模型　393

21.2　有故障環(huán)境中一性的

不可能性　394

21.3　隨機(jī)算法　395

21.4　故障檢測器　398

21.5　k一性　401

21.6　近似一性　401

21.7　異步網(wǎng)絡(luò)的計算*　403

21.8　參考文獻(xiàn)注釋　403

21.9　題　404

第22章　數(shù)據(jù)鏈路協(xié)議　406

22.1　問題闡述　406

22.2　Stenning協(xié)議　407

22.3　位變換協(xié)議　410

22.4　可容忍消息重排序的有界tag

協(xié)議　413

22.4.1　關(guān)于可容忍消息重排序和

重復(fù)的不可能性結(jié)論　414

22.4.2　可容忍消息丟失和重排序的

有界tag協(xié)議　416

22.4.3　不存在可容忍消息丟失和

重排序的高效協(xié)議　419

22.5　可容忍進(jìn)程崩潰　422

22.5.1　簡單的不可能性結(jié)論　423

22.5.2　更復(fù)雜的不可能性結(jié)論　423

22.5.3　實用的協(xié)議　426

22.6　參考文獻(xiàn)注釋　431

22.7　題　431

第三分　分同步算法

第23章　建模V：分同步系統(tǒng)

模型　434

23.1　MMT定時自動機(jī)　434

23.1.1　基本定義　434

23.1.2　作　438

23.2　通用定時自動機(jī)　440

23.2.1　基本定義　440

23.2.2　將MMT自動機(jī)轉(zhuǎn)化為通用

定時自動機(jī)　444

23.2.3　動作　446

23.3　屬性和證明方法　448

23.3.1　不變式斷言　448

23.3.2　定時軌跡屬性　450

23.3.3　模擬關(guān)系　450

23.4　構(gòu)造共享存儲器和網(wǎng)絡(luò)系統(tǒng)的

模型　456

23.4.1　共享存儲器系統(tǒng)　456

23.4.2　網(wǎng)絡(luò)　456

23.5　參考文獻(xiàn)注釋　456

23.6　題　457

第24章　分同步的互斥性　459

24.1　問題　459

24.2　單寄存器算法　460

24.3　對定時故障的恢復(fù)性　466

24.4　不可能性結(jié)果　469

24.4.1　時間下界　469

24.4.2　時間界限的不可能性

結(jié)果*　469

24.5　參考文獻(xiàn)注釋　 470

24.6　題　470

第25章　分同步的一性　473

25.1　問題　473

25.2　故障檢測器　474

25.3　基本結(jié)論　475

25.3.1　上界　475

25.3.2　下界　476

25.4　有效算法　478

25.4.1　算法　478

25.4.2　屬性　479

25.4.3　活性和復(fù)雜度　480

25.5　涉及時間不確定性的下界*　483

25.6　其他結(jié)果*　487

25.6.1　同步進(jìn)程、異步通道*　487

25.6.2　異步進(jìn)程、同步通道*　488

25.6.3　時間界限*　488

25.7　小結(jié)　490

25.8　參考文獻(xiàn)注釋　490

25.9　題　491

參考文獻(xiàn)　493