分布式算法导论 原书第2版PDF电子书下载

目录 1

第1章导论：分布式系统 1

1.1分布式系统的定义 1

1.1.1动机 1

1.1.2计算机网络 3

1.1.3广域网络 3

1.1.4局域网 5

1.1.5多处理器计算机 6

1.1.6协同操作进程 8

1.2体系结构和语言 10

1.2.1结构 10

1.2.2 OSI参考模型 11

1.2.3局域网络OSI模型：IEEE标准 13

1.2.4语言支持 14

1.3分布式算法 15

1.3.1分布式算法与集中式算法 15

1.3.2一个例子：单消息通信 16

1.3.3研究领域 20

1.4本书概要 21

第一部分 协 议 25

第2章模型 25

2.1转移系统和算法 25

2.1.1转移系统 26

2.1.2异步消息传递系统 26

2.1.3同步消息传递系统 27

2.1.4公平性 28

2.2.1安全性 29

2.2转移系统性质的证明 29

2.2.2活动性 30

2.3事件的因果序和逻辑时钟 31

2.3.1事件的独立性和相关性 32

2.3.2执行的等价性：计算 33

2.3.3逻辑时钟 35

2.4附加假设，复杂度 37

2.4.1网络拓扑结构 37

2.4.2信道性质 38

2.4.3实时性假设 39

2.4.4进程知识 40

2.4.5分布式算法的复杂度 40

习题 41

第3章通信协议 43

3.1平衡滑动窗口协议 44

3.1.1协议表示 44

3.1.2协议的正确性证明 46

3.1.3协议讨论 47

3.2基于计时器的协议 49

3.2.1协议表示 51

3.2.2协议的正确性证明 54

3.2.3协议讨论 57

习题 60

第4章路由算法 61

4.1基于目的节点的路由 62

4.2.1 Floyd-Warshall算法 65

4.2所有点对之间的最短路径问题 65

4.2.2Toueg最短路径算法 67

4.2.3讨论以及更多算法 70

4.3变更算法 73

4.3.1算法描述 74

4.3.2变更算法的正确性 78

4.3.3算法讨论 79

4.4带有压缩路由表的路由 80

4.4.1树标号模式 80

4.4.2区间路由 82

4.4.3前缀路由 88

4.5 分级路由 90

习题 92

第5章无死锁的包交换 93

5.1引言 93

5.2有结构的方法 94

5.2.1缓冲图 95

5.2.2图G的定向 97

控制器 100

5.3无结构的方法 100

5.3.1前向计数控制器和后向计数 100

5.3.2前向状态控制器和后向状态 101

控制器 101

5.4需进一步研究的问题 102

5.4.1拓扑变化 102

5.4.2其他类型的死锁 103

5.4.3活锁 104

习题 105

第二部分基本算法 107

第6章波动算法与遍历算法 107

6.1波动算法的定义和使用 107

6.1.1波动算法定义 107

6.1.2波动算法的一些基本结果 109

6.1.3具有反馈的信息传播 110

6.1.5计算下确界函数 111

6.1.4同步 111

6.2波动算法集 112

6.2.1环网算法 112

6.2.2树算法 113

6.2.3 回波算法 115

6.2.4轮询算法 116

6.2.5相位算法 117

6.2.6 Finn算法 118

6.3遍历算法 120

6.3.1遍历团 121

6.3.2遍历圆环 121

6.3.3遍历超立方体 122

6.3.4遍历连通网络 123

6.4深度优先搜索的时间复杂度 124

6.4.1分布式深度优先搜索 125

6.4.2线性时间的深度优先搜索算法 126

6.5.1波动算法综述 130

6.5.2计算和 130

6.5 遗留问题 130

6.4.3具有近邻知识的深度优先搜索 130

6.5.3 时间复杂度的另一种定义 132

习题 134

第7章选举算法 137

7.1引言 137

7.1.1本章所做假设 138

7.1.2选举和波动 138

7.2.1LeLann和Chang-Roberts算法 140

7.2环网 140

7.2.2 Peterson/Dolev-Klawe-Rodeh算法 144

7.2.3一个下界 146

7.3任意网 148

7.3.1废止和快速算法 149

7.3.2 Gallager-Humblet-Spira算法 151

7.3.3 GHS算法的全局描述 152

7.3.4 GHS算法的详细描述 153

7.3.5 GHS算法的讨论和变化 157

7.4.1模块构造 158

7.4 Korach-Kutten-Moran算法 158

7.4.2 KKM算法的应用 161

习题 162

第8章终止检测 165

8.1预备知识 165

8.1.1定义 165

8.1.2两个下界 167

8.2计算树和森林 169

8.2.1 Dijkstra-Scholten算法 169

8.1.3终止进程 169

8.2.2 Shavit-Francez算法 172

8.3基于波动的方法 175

8.3.1 Dijkstra-Feijen-Van Gasteren算法 175

8.3.2基本消息的计数：Safra算法 178

8.3.3利用确认 181

8.34带波动的终止检测 183

8.4其他方法 184

8.4.1信用－恢复算法 184

8.4.2基于时戳的终止检测方法 186

习题 188

第9章匿名网络 191

9.1预备知识 192

9.1.1定义 192

9.1.2概率算法的分类 194

9.1.3本章考虑的问题 195

9.1.4同步消息传递与异步消息传递 195

9.2确定算法 196

9.2.1确定性的选举：否定性的结果 196

9.2.2环上函数计算 197

9.3概率选举算法 200

9.4网络规模计算 202

9.4.1否定性结果 203

9.4.2计算环规模的算法 204

习题 206

10.1预备知识 209

第10章快照 209

10.2两个快照算法 212

10.2.1 Chandy-Lamport算法 212

10.2.2 Lai-Yang算法 213

10.3使用快照算法 214

10.3.1计算信道状态 214

10.3.2快照的适时性 215

10.3.3稳定性检测 216

10.4.1基本计算模型和问题阐述 217

10.4应用：死锁检测 217

10.4.2全局－标记算法 219

10.4.3受限模型的死锁检测 220

习题 221

第11章方向侦听与定向 223

11.1引言和定义 223

11.1.1方向侦听的定义和特性 223

11.1.2利用方向侦听 225

11.1.3具有方向侦听的广播 226

11.2.1 Franklin算法 228

11.2环和弦环的选举算法 228

11.2.2 Attiya改进 229

11.2.3最小化弦数 230

11.2.4 1－弦线性算法 232

11.3超立方体上的计算 234

11.3.1基线：没有拓扑知识 235

11.3.2进行比赛的算法 235

11.3.3多路径流量算法 237

1 1.3.4使用掩码的有效超立方体算法 240

1 1.3.5无标号超立方体上的选举算法 241

11.4与复杂度有关的问题 242

11.4.1团或任意图的定向 242

11.4.2位复杂度和多路径流量算法 243

11.4.3 Verweij随机漫步算法 244

11.5结论和未解决的问题 246

11.5.1利用方向侦听 246

11.5.2复杂度归约 246

习题 247

11.5.3当前研究 247

12.1预备知识 249

12.1.1同步网络 249

第12章网络中的同步 249

12.1.2 通过同步提高效率 250

12.1.3异步有限延迟网络 251

12.2同步网络中的选举 254

12.2.1网络规模已知 254

12.2.2网络规模未知 255

12.3.1简单同步器 256

12.2.3补充结果 256

12.3同步器算法 256

12.3.2 α、β和y同步器 258

12.4应用：广度优先搜索 260

12.4.1同步BFS算法 261

12.4.2与同步器组合 261

12.4.3异步BFS算法 261

12.5 Archimedean假设 264

习题 265

第三部分容 错 267

第13章分布式系统中的容错 267

13.1利用容错算法的原因 267

13.2健壮算法 268

13.2.1故障模型 268

13.2.2判定问题 269

13.2.3第14章到第16章综述 270

13.3稳定算法 271

13.2.4本书中没有涉及的主题 271

第14章异步系统中的容错 273

14.1一致性的不可能性 273

14.1.1表示、定义及基本结果 273

14.1.2不可能性证明 274

14.1.3讨论 275

14.2初始死进程 276

14.3确定可实现实例 277

14.3.1可解问题：重命名 278

14.3.2扩展的不可能性结果 280

14.4概率一致性算法 282

14.4.1损毁－健壮一致协议 282

14.4.2 Byzantine－健壮一致性协议 285

14.5弱终止性 288

习题 290

第15章同步系统中的容错 293

15.1同步判定协议 293

15.1.1弹性界限 294

15.1.2 Byzantine广播算法 295

15.1.3多项式级的广播算法 297

15.2鉴别协议 300

15.2.1 高度弹性的协议 301

15.2.2数字签名的实现 303

15.2.3 E1Gamal签名模式 303

15.2.4 RSA签名模式 304

15.2.5 Fiat-Shamir签名模式 305

15.2.6概述和讨论 306

15.3.1读取远程时钟 308

15.3时钟同步 308

15.3.2分布式时钟同步 310

15.3.3轮模型的实现 313

习题 314

第16章故障检测 315

16.1模型和定义 315

16.1.1四种基本检测器类型 316

16.1.2故障检测器的用途和缺陷 317

16.2用弱精确检测器解一致性问题 318

16.3.1弹性上界 319

16.3最终弱精确检测器 319

16.3.2一致算法 320

16.4故障检测器的实现 321

16.4.1同步系统：完美检测 321

16.4.2部分同步系统：最终完美检测 321

164.3 小结 322

习题 323

17.1.1定义 325

17.1引言 325

第17章稳定性 325

17.1.2稳定系统中的通信 326

17.1.3例子：Dijkstra令牌环 327

17.2图论算法 329

17.2.1环定向 329

17.2.2最大匹配 331

17.2.3选举和生成树构造 332

17.3.1协议组合 334

17.3稳定方法学 334

17.3.2计算最小路径 338

17.3.3结论和讨论 342

习题 342

第四部分附 录 345

附录A伪代码使用约定 345

附录B图和网络 349

参考文献 359

主题词索引 375