分布式计算-原理、算法与系统PDF|Epub|txt|kindle电子书版本网盘下载

分布式计算-原理、算法与系统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 物理时钟同步：NTP64

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-Ford120

5.5.7 距离向量路径选择121

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

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

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成强失效检测程序S486

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

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 Napster577

18.1.2 应用层覆盖网络577

18.2 数据索引和覆盖网络578

18.2.1 分布式索引579

18.3 非结构化覆盖网络580

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

18.3.2 Gnutella580

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 Tapestry598

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