分布式系统与分布式算法PDF电子书下载

第一章 1

绪论 1

1.1 分布式系统的兴起 1

目录 1

1.2分布式系统的特征 7

1.3分布式系统的研究 7

1.4分布式算法的研究 10

1.5 小结 12

习题 13

2.1拓朴学 14

第二章 14

分布式系统 14

2.1.1 完全地连接的网络 15

2.1.2部分地连接的网络 16

2.1.3 层次网络 17

2.1.4 星形 18

2.1.5 环形网络 19

2.1.6 多路存取总线 20

2.2通讯 21

2.2.1 路径策略 22

2.2.2连接策略 23

2.2.3 竞争 24

2.2.4 安全性 26

2.2.5 设计策略 29

2.3 系统类型 30

2.3.1 计算机网络 30

2.3.2局域网 32

2.4 文件系统 34

2.4.1 ARPA网的FTI 34

2.4.3 分布式的方法 35

2.4.2 集中式的方法 35

2.5 计算的方式 36

2.5.1 数据的移动 36

2.5.2计算的移动 37

2.5.3 作业的移动 38

2.6 事件的顺序 39

2.6.1 在什么之前发生的关系 39

2.6.2 实现全序 41

2.7.1 集中式的方法 43

2.7 同步 43

2.7.2 完全分布的方法 44

2.7.3标记传送的方法 47

2.8死锁处理 49

2.8.1 时间标签排序方法 49

2.8.2 死锁检测 51

2.9 健全性 58

2.9.1 故障检测 58

2.9.2 重新布局 59

2.9.3从故障中恢复 60

2.10达到一致性 61

2.10.1 不可靠的通讯 62

2.10.2 出错进程 63

2.11 选举算法 65

2.11.1 霸道算法 66

2.11.2 环形算法 68

2.12 小结 69

习题 72

共享存储问题 73

第三章 73

3.1 使用共享存储的互斥及其实现 74

3.2改进的互斥算法 85

3.2.1 艾森伯格—麦圭尔互斥算法 86

3.2.2 伯恩斯互斥算法 89

3.2.3 兰勃特的“面包房”算法 98

3.3彼得森—费希尔二进程互斥算法 103

3.4彼得森—费希尔n进程算法 112

3.5.1 实现互斥的一个简单的测试并建立算法 118

3.5测试并建立算法 118

3.5.2 使用测试并建立算法的公平互斥 120

3.5.3 伯恩斯等的测试并建立算法 122

3.6 小结 129

习题 132

第四章 134

一致性问题 134

4.1 对于有关丢失消息时一致性的不可能性的一个结果 135

4.2拜占庭一致性问题 138

4.2.1 证实算法 149

4.2.2限制通讯费用 153

4.2.3 关于进程的个数 155

4.3使用链自变量来建立不可能性结果 161

4.3.1 链自变量 161

4.3.2 费希尔—林奇下界定理 162

4.3.3停止的故障 171

4.4知识理论 179

4.4.1 最优性 180

4.4.2知识的形式理论 183

4.5异步系统的一致性及随机一致性 190

4.6小结 197

习题 200

第五章 204

静态网络算法 204

5.1路径确定算法 205

5.1.1 极小跨越树算法 205

5.1.2 加拉格尔—亨伯勒—斯皮拉算法 215

5.2领导者选举算法 227

5.2.1 勒兰—张—罗伯特的领导者选举算法 229

5.2.2希尔伯格—辛克莱领导者选举算法 233

5.2.3 彼得森领导者选举算法 235

5.2.4 同步领导者选举算法 242

5.3极大流量算法 245

5.3.1 求极大容量的算法 253

5.3.2 求极大流量算法的分析 269

5.4 多终端的极大流量算法 273

5.4.1 可实现性 274

5.4.2 分析 276

5.4.3 综合 289

5.4.4 多种商品的流量 298

5.5极小代价流程 299

5.6.1 不同代表的系统 303

5.6 应用 303

5.6.2 PERT 306

5.6.3最优通讯跨越树 312

5.7小结 319

习题 323

第六章 327

动态网络算法 327

6.1 网络通讯和OSI参考模型 329

6.1.1 虚拟线路通讯 337

6.1.2半同步通讯 341

6.1.3数据网通讯 345

6.2 多点对多点的通讯 348

6.3全局快照 369

6.4 小结 378

习题 380

第七章 382

关于分布式系统的模型 382

7.1 I/O自动机 384

7.1.1 定义和基本结果 386

7.1.2糖果机 397

7.1.3模拟多一多通讯的I/O自动机 404

7.2 Petri网 413

7.3 通讯顺序进程（CSP） 424

7.3.1 并发性 430

7.3.2图形 434

7.3.3例子：就餐的哲学家 435

7.3.4符号的改变 441

7.3.5摘述 453

7.3.6确定进程的数学理论 454

7.3.7非正确性 462

7.4小结 464

习题 466

第八章 468

形式化描述和检验 468

8.1从一个例子谈起 469

8.2证明安全性 488

8.2.1 不变量性 490

8.2.2 无干扰性 495

8.2.3 广义的Horn集 497

8.3消息传递的证明规则 501

8.3.1 使用虚拟线路的通讯 508

8.3.2通过会合点及远程过程的通讯 514

8.3.3 对于会合点及传输的其它证明系统 523

8.4证明活性性质 524

8.5描述 540

8.5.1如何来写一个描述 545

8.6 小结 553

习题 555

参考文献 562