分布式算法PDF电子书下载

目录 1

出版者的话 1

专家指导委员会 1

译者序 1

前言 1

第1章 引言 1

1.1 相关主题 1

1.2 我们的观点 2

1.3 本书内容综述 3

1.5 标记 7

1.4 参考文献注释 7

第一部分 同步网络算法 10

第2章 建模Ⅰ：同步网络模型 10

2.1 同步网络系统 10

2.2 故障 11

2.3 输入和输出 11

2.4 运行 11

2.5 证明方法 12

2.6 复杂度度量 12

2.7 随机化 12

2.8 参考文献注释 13

3.1 问题 14

3.2 相同进程的不可能性结果 14

第3章 同步环中的领导者选择 14

3.3 基本算法 15

3.4 通信复杂度为O（n log n）的算法 17

3.5 非基于比较的算法 19

3.5.1 时间片算法 20

3.5.2 变速算法 20

3.6 基于比较的算法的下界 21

3.7 非基于比较的算法的下界＊ 25

3.8 参考文献注释 26

3.9 习题 27

4.1.1 问题 29

4.1.2 简单的洪泛算法 29

4.1 一般网络中的领导者选举 29

第4章 一般同步网络中的算法 29

4.1.3 降低通信复杂度 31

4.2 广度优先搜索 32

4.2.1 问题 32

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 算法 37

4.5 最大独立集 39

4.5.2 随机化算法 40

4.5.1 问题 40

4.5.3 分析＊ 42

4.6 参考文献注释 43

4.7 习题 43

第5章 链路故障时的分布式一致性 46

5.1 协同攻击问题——确定性版本 46

5.2 协同攻击问题——随机化版本 48

5.2.1 形式化模型 49

5.2.2 算法 49

5.2.3 不一致的下限 52

5.4 习题 54

5.3 参考文献注释 54

第6章 进程故障下的分布式一致性 56

6.1 问题 56

6.2 针对停止故障的算法 58

6.2.1 基本算法 58

6.2.2 减少通信 59

6.2.3 指数信息收集算法 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一致性问题中进程的个数 74

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 算法 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 消息数的下界 109

7.4 参考文献注释 111

7.5 习题 111

第二部分 异步算法 114

第8章 建模Ⅱ：异步系统模型 114

8.1 输入／输出自动机 114

8.2.1 合成 118

8.2 自动机的操作 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 复杂度衡量 130

8.9 参考文献注释 131

8.8 随机化 131

8.7 不可区分运行 131

8.10 习题 132

第二部分A 异步共享存储器算法 136

第9章 建模Ⅲ：异步共享存储器模型 136

9.1 共享存储器系统 136

9.2 环境模型 138

9.3 不可区分状态 140

9.4 共享变量类型 140

9.5 复杂度衡量 144

9.6 故障 144

9.9 习题 145

9.8 参考文献注释 145

9.7 随机化 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 运行时间 157

10.4 互斥算法的更强条件 158

10.5.1 双进程算法 159

10.5 锁定权互斥算法 159

10.5.2 n进程算法 163

10.5.3 锦标赛算法 167

10.6 使用单写者共享存储器的算法 170

10.7 Bakery算法 171

10.8 寄存器数量的下界 173

10.8.1 基本事实 174

10.8.2 单写者共享变量 175

10.8.3 多写者共享变量 175

10.9 使用读-改-写共享变量的互斥 179

10.9.1 基本问题 179

10.9.2 有界绕过次数 180

10.9.3 锁定权 185

10.9.4 模拟证明 187

10.10 参考文献注释 189

10.11 习题 190

第11章 资源分配 194

11.1 问题 194

11.1.1 显式资源说明和互斥说明 194

11.1.2 资源分配问题 195

11.1.3 哲学家用餐问题 196

11.1.4 解法的受限形式 197

11.2 对称哲学家用餐算法的不存在性 197

11.3.1 等待链 199

11.3 右-左哲学家用餐算法 199

11.3.2 基本算法 200

11.3.3 扩展 202

11..4 哲学家用餐随机算法＊ 204

11.4.1 算法＊ 205

11.4.2 正确性＊ 207

11.5 参考文献注释 212

11.6 习题 213

第12章 一致性 215

12.1 问题 215

12.2 使用读／写共享存储器的一致性 217

12.2.3 双价初始化 218

12.2.2 术语 218

12.2.1 限制 218

12.2.4 无等待终止的不可能性 219

12.2.5 单故障终止的不可能性结果 221

12.3 读／改／写共享存储器上的一致性问题 223

12.4 其他共享存储器类型 224

12.5 异步共享存储器系统中的可计算性＊ 224

12.6 参考文献注释 225

12.7 习题 226

第13章 原子对象 229

13.1 定义和基本结论 229

13.1.1 原子对象的定义 229

13.1.2 规范无等待原子对象自动机 235

13.1.3 原子对象的合成 237

13.1.4 原子对象和共享变量 237

13.1.5 显示原子性的一个充分条件 241

13.2 用读／写变量实现读-改-写原子对象 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 参考文献注释 259

13.6 习题 260

第二部分B 异步网络算法 264

第14章 建模Ⅳ：异步网络模型 264

14.1 发送／接收系统 264

14.1.1 进程 264

14.1.2 发送／接收通道 264

14.1.4 使用可靠FIFO通道的发送／ 268

接收系统的特征 268

14.1.3 异步发送／接收系统 268

14.1.5 复杂度度量 269

14.2 广播系统 269

14.2.1 进程 269

14.2.2 广播通道 270

14.2.3 异步广播系统 270

14.2.4 采用可靠广播通道的广播系统的特征 270

14.2.5 复杂度度量 271

14.3 多播系统 271

14.3.1 进程 271

14.3.2 多播通道 271

14.5 习题 272

14.3.3 异步多播系统 272

14.4 参考文献注释 272

第15章 基本异步网络算法 274

15.1 环中的领导者选举 274

15.1.1 LCR算法 275

15.1.2 HS算法 278

15.1.3 Peterson Leader算法 278

15.1.4 通信复杂度的下界 281

15.2 任意网络中的领导者选举 286

15.3 生成树的构造、广播和敛播 287

15.4 广度优先搜索和最短路径 290

15.5.1 问题描述 295

15.5 最小生成树 295

15.5.2 同步算法：回顾 296

15.5.3 GHS算法：概要 296

15.5.4 更详细的算法 297

15.5.5 特殊消息 299

15.5.6 复杂度分析 301

15.5.7 GHS算法的正确性证明 301

15.5.8 简单“同步”策略 302

15.5.9 应用到领导者选举算法中 302

15.6 参考文献注释 303

15.7 习题 303

16.1 问题 307

第16章 同步器 307

16.2 局部同步器 309

16.3 安全同步器 313

16.3.1 前端自动机 314

16.3.2 通道自动机 315

16.3.3 安全同步器 315

16.3.4 正确性 315

16.4 安全同步器的实现 316

16.4.1 同步器Alpha 316

16.4.3 同步器Gamma 317

16.4.2 同步器Beta 317

16.5 应用 320

16.5.1 领导者选举 321

16.5.2 深度优先搜索 321

16.5.3 最短路径 321

16.5.4 广播与确认 321

16.5.5 最大独立集 321

16.6 时间下界 321

16.7 参考文献注释 324

16.8 习题 324

的转换 326

17.1.1 问题 326

17.1 从共享存储器模型到网络模型 326

第17章 共享存储器与网络 326

17.1.2 无故障时的策略 327

17.1.3 容忍进程故障的算法 332

17.1.4 对于n/2故障的不可能性结果 335

17.2 从网络模型转换到共享存储器模型 336

17.2.1 发送／接收系统 336

17.2.2 广播系统 338

17.2.3 异步网络中一致性的不可能性 338

17.3 参考文献注释 339

17.4 习题 339

18.1.1 发送／接收系统 341

18.1 异步网络的逻辑时间 341

第18章 逻辑时间 341

18.1.2 广播系统 343

18.2 使用逻辑时间的异步算法 344

18.2.1 时钟的走动 344

18.2.2 延迟未来事件 345

18.3 应用 346

18.3.1 银行系统 346

18.3.2 全局快照 348

18.3.3 模拟一台单状态机器 349

18.4 从实际时间算法到逻辑时间算法的变换＊ 352

18.5 参考文献注释 352

18.6 习题 353

19.1 发散算法的终止检测 355

19.1.1 问题 355

第19章 一致全局快照和稳定属性检测 355

19.1.2 DijkstraScholten算法 356

19.2 一致全局快照 360

19.2.1 问题 360

19.2.2 ChandyLamport算法 361

19.2.3 应用 364

19.3 参考文献注释 366

19.4 习题 367

第20章 网络资源分配 369

20.1 互斥 369

20.1.1 问题 369

20.1.3 循环令牌算法 370

20.1.2 模拟共享存储器 370

20.1.4 基于逻辑时间的算法 372

20.1.5 LogicalTimeME算法的改进 374

20.2 通用资源分配 376

20.2.1 问题 376

20.2.2 着色算法 377

20.2.3 基于逻辑时间的算法 377

20.2.4 无环有向图算法 378

20.2.5 哲学家饮水＊ 379

20.3 参考文献注释 383

20.4 习题 383

21.1 网络模型 386

第21章 带进程故障的异步网络计算 386

21.2 有故障环境中一致性的不可能性 387

21.3 随机算法 388

21.4 故障检测器 390

21.5 k一致性 393

21.6 近似一致性 394

21.7 异步网络的计算能力＊ 395

21.8 参考文献注释 396

21.9 习题 396

第22章 数据链路协议 399

22.1 问题阐述 399

22.2 Stenning协议 400

22.3 位变换协议 403

22.4 可重排序的有界标志协议 406

22.4.1 关于重排序和复制的不可能 407

性结论 407

22.4.2 容许丢失和重排序的有界标 408

志协议 408

22.4.3 不存在容许消息丢失和重排序的高效协议 412

22.5 容许进程崩溃 414

22.5.1 简单的不可能性结论 415

22.5.2 更复杂的不可能性结论 415

22.5.3 实用的协议 418

22.7 习题 423

22.6 参考文献注释 423

第三部分 部分同步算法 428

第23章 建模Ⅴ：部分同步系统模型 428

23.1 MMT定时自动机 428

23.1.1 基本定义 428

23.1.2 操作 432

23.2 通用定时自动机 434

23.2.1 基本定义 434

23.2.2 将MMT自动机转化为通用定时 437

自动机 437

23.2.3 操作 440

23.3.1 不变式 441

23.3 属性和证明方法 441

23.3.2 定时轨迹属性 443

23.3.3 模拟 444

23.4 构造共享存储器和网络系统的模型 449

23.4.1 共享存储器系统 449

23.4.2 网络 449

23.5 参考文献注释 449

23.6 习题 450

第24章 部分同步的互斥 452

24.1 问题 452

24.2 单寄存器算法 453

24.3 对时间故障的回复性 459

24.4 不可能性结果 461

24.4.1 时间下界 462

24.4.2 最终时间界限的不可能性结果＊ 462

24.5 参考文献注释 463

24.6 习题 463

第25章 部分同步的一致性 466

25.1 问题 466

25.2 故障检测器 467

25.3 基本结论 468

25.3.1 上界 468

25.3.2 下界 469

25.4 有效算法 470

25.4.1 算法 471

25.4.2 安全属性 472

25.4.3 活性和复杂度 473

25.5 涉及时间不确定性的下界＊ 475

25.6 其他结果＊ 480

25.6.1 同步进程、异步通道＊ 480

25.6.2 异步进程、同步通道＊ 481

25.6.3 最终时间界限＊ 481

25.7 小结 483

25.8 参考文献注释 483

25.9 习题 483

参考文献 486

索引 512