分布式计算-原理、算法与系统PDF电子书下载

第一章 引言 1

1.1 定义 1

1.2 与计算机系统部件的关系 2

1.3 动机 3

1.4 与并行多处理器／多计算机系统的关系 4

1.4.1 并行系统的特性 4

1.4.2 Flynn的分类法 8

1.4.3 耦合、并行、并发及粒度 9

1.5 消息传递系统与共享内存系统的对比 11

1.5.1 在共享内存的系统上仿真消息传递 11

1.5.2 在消息传递系统上仿真共享内存 12

1.6 分布式通信的原语 12

1.6.1 阻塞／非阻塞，同步／异步原语 12

1.6.2 处理器同步性 15

1.6.3 库与标准 15

1.7 同步与异步执行 16

1.7.1 通过同步系统仿真异步系统 17

1.7.2 通过异步系统仿真同步系统 17

1.7.3 仿真 18

1.8 设计主题与挑战 18

1.8.1 从系统角度看分布式系统的挑战 19

1.8.2 分布式计算中的算法挑战 20

1.8.3 分布式计算的应用以及更新的挑战 25

1.9 关于主题的选择与覆盖 27

1.10 本章小结 27

1.11 习题 28

1.12 参考文献说明 29

参考文献 30

第二章 分布式计算模型 33

2.1 分布式程序 33

2.2 分布式运行模型 33

2.3 通信网络模型 36

2.4 分布式系统的全局状态 36

2.4.1 全局状态 37

2.5 分布式计算的运行分割 38

2.6 事件的过去和未来锥面 39

2.7 进程通信模型 40

2.8 本章小结 40

2.9 习题 40

2.10 参考文献说明 41

参考文献 41

第三章 逻辑时间 42

3.1 引言 42

3.2 逻辑时钟框架 43

3.2.1 定义 43

3.2.2 实现逻辑时钟 43

3.3 标量时间 44

3.3.1 定义 44

3.3.2 基本性质 45

3.4 向量时间 46

3.4.1 定义 46

3.4.2 基本性质 47

3.4.3 有关向量时钟的大小 48

3.5 向量时钟的有效实现 49

3.5.1 Singhal-Kshemkalyani的差量技术 50

3.5.2 Fowler-Zwaenepoel的直接依赖技术 51

3.6 Jard-Jourdan的自适应技术 54

3.7 矩阵时间 56

3.7.1 定义 56

3.7.2 基本性质 58

3.8 虚拟时间 58

3.8.1 虚拟时间的定义 58

3.8.2 与Lamport逻辑时钟比较 59

3.8.3 时间变形机制 60

3.8.4 本地控制机制 60

3.8.5 全局控制机制 62

3.9 物理时钟同步：NTP 64

3.9.1 动机 64

3.9.2 定义及术语 65

3.9.3 时钟不准确性 65

3.10 本章小结 67

3.11 习题 68

3.12 参考文献说明 68

参考文献 69

第四章 记录全局状态与快照算法 71

4.1 引言 71

4.2 系统模型和定义 73

4.2.1 系统模型 73

4.2.2 一致性全局状态 74

4.2.3 有关分割的解 74

4.2.4 记录全局快照时遇到的问题 75

4.3 FIFO通道的快照算法 75

4.3.1 Chandy-Lamport算法 75

4.3.2 被记录全局状态的性质 77

4.4 Chandy-Lamport算法的变种 78

4.4.1 Spezialetti-Kearns算法 79

4.4.2 Venkatesan快照增量算法 80

4.4.3 Helary波同步方法 81

4.5 非FIFO通道的快照算法 81

4.5.1 Lai-Yang算法 82

4.5.2 Li等人的算法 83

4.5.3 Mattern算法 84

4.6 因果传递系统快照 85

4.6.1 进程状态记录 85

4.6.2 Acharya-Badrinath算法中的通道状态记录 86

4.6.3 Alagar-Venkatesan算法中的通道状态记录 86

4.7 监控全局状态 88

4.8 一致性全局快照的必要和充分条件 88

4.8.1 Zigzag路径和一致性全局快照 89

4.9 找出分布式计算中的一致性全局快照 92

4.9.1 找出一致性全局快照 92

4.9.2 枚举式一致性快照Manivannan-Netzer-Singhal算法 94

4.9.3 在分布式计算中找出Z路径 96

4.10 本章小结 97

4.11 习题 98

4.12 参考文献说明 99

参考文献 99

第五章 术语和基本算法 102

5.1 拓扑抽象和覆盖 102

5.2 分类和基本概念 104

5.2.1 应用执行和控制算法执行 104

5.2.2 集中式算法和分布式算法 104

5.2.3 对称算法和非对称算法 105

5.2.4 匿名算法 105

5.2.5 一致算法 105

5.2.6 自适应算法 105

5.2.7 确定性执行对非确定性执行 105

5.2.8 执行抑制 106

5.2.9 同步系统和异步系统 107

5.2.10 联机算法与脱机算法 107

5.2.11 故障模型 107

5.2.12 无需等待算法 108

5.2.13 通信通道 109

5.3 复杂度测量和度量 109

5.4 程序结构 110

5.5 图的基本算法 111

5.5.1 使用洪泛法的同步单一启动者生成树算法 111

5.5.2 使用洪泛法的异步单一启动者生成树算法 113

5.5.3 使用洪泛法的异步并发启动者生成树算法 115

5.5.4 异步并发启动者深度优先搜索生成树算法 118

5.5.5 在一棵树上广播和聚播 119

5.5.6 单一源最短路径算法：同步Bellman-Ford 120

5.5.7 距离向量路径选择 121

5.5.8 单一源最短路径算法：异步Bellman-Ford 122

5.5.9 全源最短路径：异步分布式Floyd-Warshall 123

5.5.10 有约束的异步和同步洪泛法（W/O一棵生成树） 126

5.5.11 同步系统的最小权重生成树算法 128

5.5.12 异步系统的最小权重树 132

5.6 同步工具 133

5.7 最大独立集合 138

5.8 连通支配集 140

5.9 紧凑路由表 141

5.10 选领导者 142

5.11 设计分布式图算法的挑战 144

5.12 对象副本问题 144

5.12.1 问题定义 145

5.12.2 算法概要 145

5.12.3 读和写 146

5.12.4 收敛到一个副本模式 146

5.13 本章小结 149

5.14 习题 150

5.15 参考文献说明 152

参考文献 153

第六章 消息序与组通信 156

6.1 消息序的模式 157

6.1.1 异步执行过程 157

6.1.2 先进先出执行过程 157

6.1.3 因果序执行过程 158

6.1.4 同步执行过程 160

6.2 使用同步通信的异步执行过程 161

6.2.1 用同步通信可实现的执行过程 162

6.2.2 序样式的层次体系 165

6.2.3 两种仿真 165

6.3 异步系统中同步程序的序 166

6.3.1 会合 167

6.3.2 双路会合算法 167

6.4 组通信 171

6.5 因果序 171

6.5.1 Raynal-Schiper-Toueg算法［22］ 172

6.5.2 Kshemkalyani-Singhai最优算法［20,21］ 173

6.6 全序 180

6.6.1 为全序设计的集中式算法 180

6.6.2 三阶段分布式算法 181

6.7 多播相关术语 185

6.8 多播传播树 186

6.9 应用层多播算法的分类 190

6.10 容错组通信的语义 192

6.11 网络层的分布式多播算法 194

6.11.1 泛洪约束的反向路径转发 194

6.11.2 Steiner树 195

6.11.3 多播的成本函数 196

6.11.4 有界延迟的Steiner树 196

6.11.5 核基树 199

6.12 本章小结 199

6.13 习题 200

6.14 参考文献说明 201

参考文献 202

第七章 终止检测 204

7.1 引言 204

7.2 分布式计算的系统模型 205

7.3 基于快照的终止检测算法 205

7.3.1 非形式化描述 206

7.3.2 形式化描述 206

7.3.3 讨论 207

7.4 信用-传递终止检测算法 207

7.4.1 形式化描述 208

7.4.2 算法的正确性 208

7.5 基于生成树的终止检测算法 209

7.5.1 定义 209

7.5.2 一个简单的算法 210

7.5.3 正确的算法 210

7.5.4 一个例子 211

7.5.5 算法性能分析 213

7.6 消息-优化终止检测算法 213

7.6.1 主要思想 213

7.6.2 算法描述 214

7.6.3 算法性能分析 216

7.7 通用分布式计算模型中的终止检测 216

7.7.1 模型定义和假设 217

7.7.2 符号 217

7.7.3 终止定义 217

7.7.4 一个静态终止检测算法 218

7.7.5 一个动态终止检测算法 219

7.8 原子计算模型中的终止检测 221

7.8.1 执行的原子模型 221

7.8.2 一个简单的计数方法 221

7.8.3 四计数器方法 222

7.8.4 怀疑论者算法 223

7.8.5 时间算法 223

7.8.6 向量计数算法 225

7.8.7 信道计数算法 226

7.9 带错分布式系统中的终止检测 229

7.9.1 流检测方案 229

7.9.2 捕获快照 230

7.9.3 算法描述 231

7.9.4 算法性能分析 234

7.10 本章小结 234

7.11 习题 235

7.12 参考文献说明 235

参考文献 236

第八章 知识推理 238

8.1 Muddy children难题 238

8.2 知识的逻辑 239

8.2.1 知识操作符 239

8.2.2 回到muddy children难题 240

8.2.3 克里普克结构 240

8.2.4 使用克里普克结构解决muddy children难题 241

8.2.5 知识的属性 243

8.3 同步系统中的知识 244

8.4 异步系统中的知识 244

8.4.1 逻辑和定义 244

8.4.2 异步系统中的达成一致 245

8.4.3 共同知识的变体 246

8.4.4 并发共同知识 246

8.5 知识转移 250

8.6 知识和时钟 251

8.7 本章小结 253

8.8 习题 253

8.9 参考文献说明 254

参考文献 254

第九章 分布式互斥算法 256

9.1 引言 256

9.2 预备知识 257

9.2.1 系统模型 257

9.2.2 互斥算法的必备条件 257

9.2.3 性能指标 258

9.3 Lamport算法 259

9.4 Ricart-Agrawala算法 262

9.5 Singhal动态信息结构算法 264

9.5.1 算法描述 266

9.5.2 正确性 268

9.5.3 性能分析 269

9.5.4 异构流量模式下的适应性 270

9.6 Lodha和Kshemkalyani的公平互斥算法 270

9.6.1 系统模型 270

9.6.2 算法描述 270

9.6.3 安全性、公平性与活性 275

9.6.4 消息复杂性 275

9.7 基于仲裁团的互斥算法 275

9.8 Maekawa算法 276

9.8.1 死锁问题 277

9.9 Agarwal-EI Abbadi基于仲裁团的算法 278

9.9.1 构造树状结构仲裁团 279

9.9.2 构造树状结构仲裁团算法分析 280

9.9.3 有效性 280

9.9.4 树状结构仲裁团的例子 281

9.9.5 分布式互斥算法 282

9.9.6 正确性证明 283

9.10 基于令牌的算法 283

9.11 Suzuki-Kasami广播算法 283

9.12 基于树的Raymond算法 285

9.12.1 HOLDER变量 286

9.12.2 算法操作 287

9.12.3 算法描述 287

9.12.4 正确性 289

9.12.5 开销和性能分析 290

9.12.6 算法初始化 291

9.12.7 错误和恢复 291

9.13 本章小结 292

9.14 习题 292

9.15 参考文献说明 293

参考文献 293

第十章 死锁检测 296

10.1 简介 296

10.2 系统模型 296

10.2.1 等待图 297

10.3 预备知识 297

10.3.1 死锁处理策略 297

10.3.2 死锁检测问题 298

10.4 死锁模型 298

10.4.1 单资源模型 299

10.4.2 AND模型 299

10.4.3 OR模型 299

10.4.4 AND-OR模型 300

10.4.5 （p q）模型 300

10.4.6 无限制模型 300

10.5 Knapp分布式死锁检测算法分类 301

10.5.1 路径推送算法 301

10.5.2 边探测算法 301

10.5.3 基于计算分散的算法 301

10.5.4 基于全局状态检测的算法 302

10.6 单资源模型下的Mitchell-Merritt算法 302

10.7 针对AND模型的Chandy-Misra-Haas算法 304

10.8 针对OR模型的Chandy-Misra-Haas算法 305

10.9 针对（p q）模型的Kshemkalyani-Singhal算法 307

10.9.1 算法的非正式描述 308

10.9.2 算法描述 310

10.10 本章小结 315

10.11 习题 315

10.12 参考文献说明 315

参考文献 316

第十一章 全局谓词的检测 320

11.1 稳定谓词和不稳定谓词 320

11.1.1 稳定谓词 321

11.1.2 不稳定谓词 322

11.2 谓词的形态 323

11.2.1 谓词检测的复杂性 324

11.3 关系谓词的集中式算法 324

11.4 合取谓词 327

11.4.1 合取谓词基于区间的集中式算法 328

11.4.2 Possibly（φ）基于全局状态的集中式算法 331

11.5 合取谓词的分布式算法 333

11.5.1 Possibly（φ）基于状态的分布式令牌算法 333

11.5.2 Definitely（φ）基于区间的分布式令牌算法 334

11.5.3 Possibly（φ）基于区间的分布式捎带算法 338

11.6 谓词的进一步分类 342

11.7 本章小结 342

11.8 习题 343

11.9 参考文献说明 344

参考文献 344

第十二章 分布式共享内存 347

12.1 抽象化及其优势 347

12.2 内存一致性模型 349

12.2.1 强一致性、原子一致性及线性 350

12.2.2 顺序一致性 352

12.2.3 因果一致性 355

12.2.4 处理器一致性 356

12.2.5 慢内存 357

12.2.6 一致性模型的层次结构 358

12.2.7 其他基于同步指令的一致性模型 358

12.3 共享内存的互斥 360

12.3.1 Lamport面包店算法 360

12.3.2 Lamport's WRWM技术和快速互斥 362

12.3.3 互斥的硬件支持 364

12.4 等待无关性 366

12.5 寄存器层次和无等待模拟 367

12.5.1 构造1：SRSW安全寄存器到MRSW安全寄存器 369

12.5.2 构造2：SRSW普通寄存器到MRSW普通寄存器 370

12.5.3 构造3：布尔MRSW安全寄存器到整数MRSW安全寄存器 370

12.5.4 构造4：布尔MRSW安全寄存器到布尔MRSW普通寄存器 370

12.5.5 构造5：布尔MRSW普通寄存器到整数MRSW普通寄存器 371

12.5.6 构造6：布尔MRSW普通寄存器到整数MRSW原子寄存器 373

12.5.7 构造7：整数MRSW原子寄存器到整数MRMW原子寄存器 375

12.5.8 构造8：整数SRSW原子寄存器到整数MRSW原子寄存器 376

12.6 共享对象的无等待原子快照 378

12.7 本章小结 381

12.8 习题 381

12.9 参考文献说明 383

参考文献 383

第十三章 检查点和卷回恢复 386

13.1 介绍 386

13.2 背景和定义 387

13.2.1 系统模型 387

13.2.2 本地检查点 388

13.2.3 一致的系统状态 388

13.2.4 与外部世界的交互 389

13.2.5 不同消息类型 389

13.3 错误恢复中的问题 390

13.4 基于检查点的恢复 392

13.4.1 无协作检查点 392

13.4.2 协作式检查点 393

13.4.3 最小处理无阻塞检查点的不可能性 395

13.4.4 通信引导检查点 396

13.5 基于日志的卷回恢复 397

13.5.1 确定事件和非确定事件 397

13.5.2 悲观日志 398

13.5.3 乐观日志 399

13.5.4 因果日志 400

13.6 Koo-Toueg协同检查点算法 401

13.6.1 检查点算法 401

13.6.2 卷回恢复算法 403

13.7 异步检查点和恢复的Juang-Venkatesan算法 404

13.7.1 系统模型和假设 404

13.7.2 异步检查点 404

13.7.3 恢复算法 405

13.8 Manivannan-Singhal准同步检查点算法 407

13.8.1 检查点算法 408

13.8.2 恢复算法 410

13.8.3 复杂消息处理 413

13.9 基于矢量时间的Peterson-Kearns算法 415

13.9.1 系统模型 415

13.9.2 算法的非形式化描述 416

13.9.3 卷回协议的形式化描述 418

13.9.4 正确性证明 419

13.10 Helary-Mostefaoui-Netzer-Raynal通信引导协议 421

13.10.1 设计原则 421

13.10.2 检查点协议 424

13.11 本章小结 426

13.12 习题 427

13.13 参考文献说明 427

参考文献 428

第十四章 共识和协定算法 431

14.1 问题定义 431

14.1.1 拜占庭协定及相关问题 433

14.1.2 问题的等价性及标示 433

14.2 结果概观 434

14.3 无故障系统（同步或者异步）中的协定问题 435

14.4 有故障的同步系统（消息传输机制）中的协定问题 436

14.4.1 针对崩溃故障（同步系统）的共识算法 436

14.4.2 针对拜占庭错误的共识算法（同步系统） 437

14.5 有故障的异步消息传输系统中的协定问题 447

14.5.1 得到一致解的不可能性 447

14.5.2 结束可靠的广播 449

14.5.3 分布式事务提交 449

14.5.4 k-set共识问题 450

14.5.5 近似共识 450

14.5.6 重命名问题 455

14.5.7 可靠广播 460

14.6 异步系统中无等待共享内存的共识问题 461

14.6.1 不可能有解 461

14.6.2 共识数以及共识层级 463

14.6.3 共识对象的通用性 468

14.6.4 共享内存中的k-set共识 472

14.6.5 共享内存的重命名问题 473

14.6.6 使用分裂器解决共享内存重命名问题 474

14.7 本章小结 476

14.8 习题 477

14.9 参考文献说明 478

参考文献 479

第十五章 失效检测 481

15.1 引言 481

15.2 非可靠失效检测程序 482

15.2.1 系统模型 482

15.2.2 失效检测程序 483

15.2.3 完备性的准确性 483

15.2.4 失效检测程序类型 485

15.2.5 失效检测程序的可简约性 485

15.2.6 简约弱失效检测程序W成强失效检测程序S 486

15.2.7 简约最终弱失效检测程序◇W成最终强失效检测程序◇S 488

15.3 共识问题 490

15.3.1 解共识问题 490

15.3.2 使用强失效检测程序S的解决方案 490

15.3.3 使用最终强失效检测程序◇S的解决方案 492

15.4 原子广播 495

15.5 原子广播的解决方案 495

15.6 解决基本一致问题的最弱失效检测程序 497

15.6.1 实际的失效检测程序 497

15.6.2 对一致的最弱失效检测程序 499

15.6.3 终止可靠广播的最弱失效检测程序 499

15.7 失效检测程序的实现 500

15.8 自适应失效检测程序协议 502

15.8.1 懒惰失效检测协议 502

15.9 习题 505

15.10 参考文献说明 505

参考文献 506

第十六章 分布式系统中的验证 508

16.1 简介 508

16.2 背景和定义 508

16.2.1 认证的基础 509

16.2.2 主体的类型 509

16.2.3 认证协议的简单分类 509

16.2.4 标记法 510

16.2.5 密码协议的设计原则 510

16.3 基于对称密码系统的协议 511

16.3.1 基本协议 512

16.3.2 使用nonce的修正协议 512

16.3.3 Wide-mouth frog协议 513

16.3.4 基于认证服务器的协议 514

16.3.5 一次性口令方案 515

16.3.6 Otway-Rees协议 517

16.3.7 Kerberos认证服务 518

16.4 基于非对称密码系统的协议 522

16.4.1 基本协议 523

16.4.2 使用认证授权的修改协议 523

16.4.3 Needham-Schroeder协议 524

16.4.4 SSL协议 526

16.5 基于口令认证 529

16.5.1 加密密钥交换协议 529

16.5.2 安全远程口令协议 530

16.6 认证协议失效 531

16.7 本章小结 532

16.8 习题 533

16.9 参考文献说明 533

参考文献 534

第十七章 自稳定 537

17.1 介绍 537

17.2 系统模型 538

17.3 自稳定性定义 539

17.3.1 随机自稳定性及概率自稳定性 540

17.4 自稳定性算法设计中的问题 541

17.4.1 个体单元中的状态数 542

17.4.2 一致与非一致网络 546

17.4.3 中央和分布式守护程序 547

17.4.4 减少令牌环中的状态数 548

17.4.5 共享内存模型 549

17.4.6 互斥 549

17.4.7 自稳定的开销 550

17.5 设计自稳定系统的方法 550

17.5.1 分层和模块化 550

17.6 通信协议 552

17.7 自稳定分布式生成树 553

17.8 构建生成树的自稳定算法 554

17.8.1 Dolev、Israeli和Moran算法 554

17.8.2 构建生成树的Afek、Kutten和Yang算法 556

17.8.3 构建生成树的Arora和Gouda算法 557

17.8.4 构建生成树的Huang等人算法 557

17.8.5 构建生成树的Afek和Bremler算法 557

17.9 1-最大独立集合的匿名自稳定算法 558

17.10 概率自稳定头标选择算法 560

17.11 编译在自稳定中的作用 562

17.11.1 顺序程序的编译程序 563

17.11.2 异步消息传递系统的编译程序 563

17.11.3 异步共享内存系统编译程序 564

17.12 自稳定作为容错的一个解法 564

17.13 阻碍自稳定的因素 566

17.14 自稳定的局限 567

17.15 本章小结 568

17.16 习题 569

17.17 参考文献说明 569

参考文献 570

第十八章 对等计算及覆盖网络 576

18.1 概述 576

18.1.1 Napster 577

18.1.2 应用层覆盖网络 577

18.2 数据索引和覆盖网络 578

18.2.1 分布式索引 579

18.3 非结构化覆盖网络 580

18.3.1 非结构化覆盖网络：属性 580

18.3.2 Gnutella 580

18.3.3 Gnutella以及非结构化覆盖网络中的查找 581

18.3.4 复制策略 583

18.3.5 复制策略实现 585

18.4 Chord分布式哈希表 586

18.4.1 概述 586

18.4.2 简单查找 587

18.4.3 可扩展的查找 588

18.4.4 管理网络扰动 589

18.4.5 复杂度 592

18.5 内容寻址网络 593

18.5.1 概述 593

18.5.2 CAN初始化 594

18.5.3 CAN路由 594

18.5.4 CAN维护 595

18.5.5 CAN优化 597

18.5.6 CAN复杂度 598

18.6 Tapestry 598

18.6.1 概述 598

18.6.2 覆盖网络和路由 598

18.6.3 对象发布和对象查找 601

18.6.4 节点插入 602

18.6.5 节点删除 603

18.7 P2P系统设计中的其他挑战 604

18.7.1 公平：一个博弈游戏 604

18.7.2 信任或者声誉管理 605

18.8 在存储空间及路由长度间折中 605

18.8.1 统一DHT协议 605

18.8.2 有关DHT存储和路由距离的约束 607

18.9 复杂网络的图结构 607

18.10 Internet图 609

18.10.1 基本定理和其定义 609

18.10.2 Internet的特性 611

18.10.3 复杂网络的错误和攻击容忍 613

18.11 通用随机图网络 615

18.12 小世界网络 615

18.13 规模无关网络 616

18.13.1 主方程法 617

18.13.2 速率方程法 617

18.14 演化网络 618

18.14.1 扩展的Barabasi-Albert模型 619

18.15 本章小结 621

18.16 习题 621

18.17 参考文献说明 622

参考文献 622

索引 625