《分布式系统与分布式算法》求取 ⇩

第一章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网的FTI34

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 PERT306

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