分布式算法（典藏版）

图书标准信息

• 作者 [美]南希·A. 林奇（Nancy A. Lynch）
• 出版社 机械工业出版社
• 出版时间 2023-05
• 版次 1
• ISBN 9787111724247
• 定价 119.00元
• 装帧 其他
• 开本 16开
• 纸张 胶版纸
• 页数 532页
• 字数 845千字

【内容简介】

本书对分布式算法进行了全面介绍，包括同步模型、异步模型和部分同步模型，针对这些模型讨论互斥性、一致性和通信问题，为设计、实现和分析分布式算法提供了蓝图。本书对分布式算法领域的许多经典问题给出了多种解决算法或者不可能性结果，绝大部分的算法附有详细的证明过程，并且有jing确的复杂度衡量。本书还配有大量习题，并在每章后列出了详细的参考文献。本书可作为高等院校计算机专业的研究生教材，尤其适合对计算机理论或体系结构感兴趣的学生学习，还适合分布式领域的设计人员和研究人员参考。

【作者简介】

南希·A. 林奇（Nancy A. Lynch）　麻省理工学院电子工程和计算机科学系教授，领导麻省理工学院的分布式系统理论研究组，在分布式算法和不可能解以及分布式系统的形式化建模和证明方面编写了大量著作。

【目录】

目　　录

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章