分布式算法
链接:https://pan.baidu.com/s/1q__0sA9cgUxMLwkLR3FXfg?pwd=1igc
提取码:1igc

本书对分布式算法进行了全面介绍,括同步模型、异步模型和分同步模型,针对这些模型讨论互斥性、一性和通信问题,为设计、实现和分析分布式算法提供了蓝图。本书对分布式算法领域的许多问题给出了多种解决算法或者不可能性结果,大分的算法附有详细的证明过程,并且有jing确的复杂度衡量。本书还配有大量题,并在每章后列出了详细的参考文献。本书可作为高等院校计算机业的研究生教材,尤其适合对计算机理论或体系结构感兴趣的学生学,还适合分布式领域的设计人员和研究人员参考。
Distributed Algorithms
译者序
前言
第1章 引言 1
1.1 相关主题 1
1.2 我们的观点 2
1.3 本书内容综述 4
1.4 参考文献注释 7
1.5 标记 8
第一分 同步网络算法
第2章 建模I:同步网络模型 10
2.1 同步网络系统 10
2.2 故障 11
2.3 输入和输出 11
2.4 运行 12
2.5 证明方法 12
2.6 复杂度度量 12
2.7 随机化 13
2.8 参考文献注释 13
第3章 同步环中的领导者选择 14
3.1 问题 14
3.2 相同进程的不可能性结果 15
3.3 基本算法 15
3.4 通信复杂度为O (nlogn)的算法 17
3.5 非基于比较的算法 20
3.5.1 时间片算法 20
3.5.2 变速算法 20
3.6 基于比较的算法的下界 22
3.7 非基于比较的算法的下界* 26
3.8 参考文献注释 27
3.9 题 27
第4章 一般同步网络中的算法 29
4.1 一般网络中的领导者选举 29
4.1.1 问题 29
4.1.2 简单的洪泛算法 29
4.1.3 降低通信复杂度 31
4.2 广度先搜索 32
4.2.1 问题 33
4.2.2 基本的广度先搜索算法 33
4.2.3 应用 34
4.3 短路径 35
4.4 小生成树 36
4.4.1 问题 36
4.4.2 基本定理 36
4.4.3 算法 38
4.5 独立集 40
4.5.1 问题 40
4.5.2 随机化算法 41
4.5.3 分析* 42
4.6 参考文献注释 44
4.7 题 44
第5章 链路故障时的分布式
一性 46
5.1 协同攻击问题—确定性版本 46
5.2 协同攻击问题—随机化版本 48
5.2.1 形式化模型 49
5.2.2 算法 49
5.2.3 不一的下限 52
5.3 参考文献注释 54
5.4 题 54
第6章 进程故障下的分布式
一性 56
6.1 问题 57
6.2 针对停止故障的算法 58
6.2.1 基本算法 58
6.2.2 减少通信 60
6.2.3 指数信息收集算法 61
6.2.4 带鉴别的Byzantine一性 66
6.3 针对Byzantine故障的算法 66
6.3.1 举例 67
6.3.2 Byzantine一性问题的EIG
算法 68
6.3.3 使用二元Byzantine一性的
一般Byzantine一性问题 71
6.3.4 减少通信开销 72
6.4 Byzantine一性问题中进程的
个数 75
6.5 一般图中的Byzantine一性
问题 78
6.6 弱Byzantine一性 81
6.7 有停止故障时的轮数 82
6.8 参考文献注释 88
6.9 题 89
第7章 更多的一性问题 93
7.1 k一性问题 93
7.1.1 问题 93
7.1.2 算法 94
7.1.3 下界* 95
7.2 近似一性 103
7.3 提交问题 106
7.3.1 问题 106
7.3.2 两段提交 107
7.3.3 三段提交 108
7.3.4 消息数的下界 110
7.4 参考文献注释 112
7.5 题 112
第二分 异步算法
第8章 建模II:异步系统模型 116
8.1 输入/输出自动机 116
8.2 自动机的作 120
8.2.1 合成 120
8.2.2 隐藏 123
8.3 公平性 123
8.4 问题的输入和输出 126
8.5 属性与证明方法 126
8.5.1 不变式断言 126
8.5.2 轨迹属性 126
8.5.3 与活性属性 127
8.5.4 合成推理 129
8.5.5 层次化证明 131
8.6 复杂度衡量 133
8.7 不可区分的运行 134
8.8 随机化 134
8.9 参考文献注释 134
8.10 题 135
第二分A?异步共享存储器算法
第9章 建模III:异步共享存储器
模型 138
9.1 共享存储器系统 138
9.2 环境模型 140
9.3 不可区分状态 141
9.4 共享变量类型 142
9.5 复杂度衡量 145
9.6 故障 146
9.7 随机化 146
9.8 参考文献注释 146
9.9 题 146
第10章 互斥 148
10.1 异步共享存储器模型 148
10.2 问题 150
10.3 Dijkstra的互斥算法 153
10.3.1 算法 153
10.3.2 正确性证明 156
10.3.3 互斥条件的一个断言式
证明 158
10.3.4 运行时间 159
10.4 互斥算法的更强条件 160
10.5 锁定权互斥算法 162
10.5.1 双进程算法 162
10.5.2 n进程算法 165
10.5.3 锦标赛算法 169
10.6 使用单写者共享寄存器的算法 172
10.7 Bakery算法 174
10.8 寄存器数量的下界 176
10.8.1 基本事实 177
10.8.2 单写者共享变量 177
10.8.3 多写者共享变量 178
10.9 使用读–改–写共享变量的
互斥 182
10.9.1 基本问题 182
10.9.2 有界绕过次数 183
10.9.3 锁定权 188
10.9.4 模拟证明 190
10.10 参考文献注释 193
10.11 题 193
第11章 资源分配 197
11.1?问题 197
11.1.1 显式资源规格说明和互斥规格说明 197
11.1.2 资源分配问题 198
11.1.3 哲学家用餐问题 199
11.1.4 解法的受限形式 200
11.2 对称哲学家用餐算法的
不存在性 200
11.3 右–左哲学家用餐算法 202
11.3.1 等待链 202
11.3.2 基本算法 203
11.3.3 扩展 205
11.4 随机哲学家用餐算法* 208
11.4.1 算法* 208
11.4.2 正确性* 210
11.5 参考文献注释 216
11.6 题 216
第12章 一性 218
12.1?问题 218
12.2 使用读/写共享存储器的一性
问题 220
12.2.1 限制 221
12.2.2 术语 221
12.2.3 双初始化 222
12.2.4 无等待止性的不可能性 222
12.2.5 单故障止性的不可能性
结果 224
12.3 读/改/写共享存储器上的
一性问题 227
12.4 其他共享存储器类型 227
12.5 异步共享存储器系统中的可
计算性* 227
12.6 参考文献注释 229
12.7 题 229
第13章 原子对象 232
13.1 定义和基本结论 232
13.1.1 原子对象的定义 233
13.1.2 规范无等待原子对象
自动机 238
13.1.3 原子对象的合成 240
13.1.4 原子对象和共享变量 240
13.1.5 显示原子性的一个充分
条件 245
13.2 用读/写变量实现读–改–写
原子对象 246
13.3 共享存储器的原子快照 247
13.3.1 问题 247
13.3.2 带无界变量的一个算法 248
13.3.3 带有界变量的一个算法* 251
13.4 读/写原子对象 254
13.4.1 问题 254
13.4.2 证明原子性的其他引理 255
13.4.3 带无界变量的一个算法 256
13.4.4 两个写者的有界算法 259
13.4.5 使用快照的算法 263
13.5 参考文献注释 264
13.6 题 265
第二分B 异步网络算法
第14章 建模IV:异步网络模型 268
14.1 发送/接收系统 268
14.1.1 进程 268
14.1.2 发送/接收通道 269
14.1.3 异步发送/接收系统 272
14.1.4 使用可靠FIFO通道的发送/
接收系统的属性 272
14.1.5 复杂度度量 273
14.2 广播系统 274
14.2.1 进程 274
14.2.2 广播通道 274
14.2.3 异步广播系统 275
14.2.4 采用可靠广播通道的广播系统的属性 275
14.2.5 复杂度度量 275
14.3 多播系统 275
14.3.1 进程 276
14.3.2 多播通道 276
14.3.3 异步多播系统 276
14.4 参考文献注释 277
14.5 题 277
第15章 基本异步网络算法 279
15.1 环中的领导者选举 279
15.1.1 LCR算法 279
15.1.2 HS算法 283
15.1.3 PetersonLeader算法 283
15.1.4 通信复杂度的下界 286
15.2 任意网络中的领导者选举 291
15.3 生成树的构造、广播和敛播 292
15.4 广度先搜索和短路径 295
15.5 小生成树 300
15.5.1 问题描述 301
15.5.2 同步算法:回顾 301
15.5.3 GHS算法:概要 302
15.5.4 更详细的算法 303
15.5.5 殊消息 305
15.5.6 复杂度分析 306
15.5.7 GHS算法的正确性证明 307
15.5.8 简单“同步”策略 308
15.5.9 应用到领导者选举算法中 308
15.6 参考文献注释 309
15.7 题 309
第16章 同步器 313
16.1 问题 313
16.2 局同步器 315
16.3 同步器 319
16.3.1 前端自动机 320
16.3.2 通道自动机 321
16.3.3 同步器的任务 321
16.3.4 正确性 322
16.4 同步器的实现 322
16.4.1 同步器Alpha 322
16.4.2 同步器Beta 323
16.4.3 同步器Gamma 323
16.5 应用 327
16.5.1 领导者选举 327
16.5.2 广度先搜索 327
16.5.3 短路径 328
16.5.4 广播与确认 328
16.5.5 大独立集 328
16.6 时间下界 328
16.7 参考文献注释 331
16.8 题 331
第17章 共享存储器与网络 333
17.1 从异步共享存储器模型到异步
网络模型的转换 333
17.1.1 问题 333
17.1.2 无故障时的策略 334
17.1.3 容忍进程故障的算法 339
17.1.4 对于n/2故障的不可能性
结果 342
17.2 从异步网络模型到异步共享存储器模型的转换 343
17.2.1 发送/接收系统 344
17.2.2 广播系统 345
17.2.3 异步网络中一性的
不可能性 346
17.3 参考文献注释 346
17.4 题 346
第18章 逻辑时间 348
18.1 异步网络的逻辑时间 348
18.1.1 发送/接收系统 348
18.1.2 广播系统 350
18.2 使用逻辑时间的异步算法 351
18.2.1 时钟的走动 351
18.2.2 延迟未来事件 352
18.3 应用 353
18.3.1 银行系统 353
18.3.2 全局快照 355
18.3.3 模拟一台单状态机 356
18.4 从实际时间算法到逻辑时间算法的变换* 359
18.5 参考文献注释 359
18.6 题 360
第19章 一全局快照和稳定属性
检测 362
19.1 发散算法的止检测 362
19.1.1 问题 362
19.1.2 DijkstraScholten算法 363
19.2 一全局快照 367
19.2.1 问题 367
19.2.2 ChandyLamport算法 368
19.2.3 应用 372
19.3 参考文献注释 374
19.4 题 374
第20章 网络资源分配 376
20.1 互斥 376
20.1.1 问题 376
20.1.2 模拟共享存储器 377
20.1.3 循环令牌算法 377
20.1.4 基于逻辑时间的算法 379
20.1.5 LogicalTimeME算法的改进 381
20.2 通用资源分配 383
20.2.1 问题 383
20.2.2 着色算法 384
20.2.3 基于逻辑时间的算法 385
20.2.4 无环有向图算法 385
20.2.5 哲学家饮水* 386
20.3 参考文献注释 390
20.4 题 391
第21章 带进程故障的异步网络
计算 393
21.1 网络模型 393
21.2 有故障环境中一性的
不可能性 394
21.3 随机算法 395
21.4 故障检测器 398
21.5 k一性 401
21.6 近似一性 401
21.7 异步网络的计算* 403
21.8 参考文献注释 403
21.9 题 404
第22章 数据链路协议 406
22.1 问题阐述 406
22.2 Stenning协议 407
22.3 位变换协议 410
22.4 可容忍消息重排序的有界tag
协议 413
22.4.1 关于可容忍消息重排序和
重复的不可能性结论 414
22.4.2 可容忍消息丢失和重排序的
有界tag协议 416
22.4.3 不存在可容忍消息丢失和
重排序的高效协议 419
22.5 可容忍进程崩溃 422
22.5.1 简单的不可能性结论 423
22.5.2 更复杂的不可能性结论 423
22.5.3 实用的协议 426
22.6 参考文献注释 431
22.7 题 431
第三分 分同步算法
第23章 建模V:分同步系统
模型 434
23.1 MMT定时自动机 434
23.1.1 基本定义 434
23.1.2 作 438
23.2 通用定时自动机 440
23.2.1 基本定义 440
23.2.2 将MMT自动机转化为通用
定时自动机 444
23.2.3 动作 446
23.3 属性和证明方法 448
23.3.1 不变式断言 448
23.3.2 定时轨迹属性 450
23.3.3 模拟关系 450
23.4 构造共享存储器和网络系统的
模型 456
23.4.1 共享存储器系统 456
23.4.2 网络 456
23.5 参考文献注释 456
23.6 题 457
第24章 分同步的互斥性 459
24.1 问题 459
24.2 单寄存器算法 460
24.3 对定时故障的恢复性 466
24.4 不可能性结果 469
24.4.1 时间下界 469
24.4.2 时间界限的不可能性
结果* 469
24.5 参考文献注释 470
24.6 题 470
第25章 分同步的一性 473
25.1 问题 473
25.2 故障检测器 474
25.3 基本结论 475
25.3.1 上界 475
25.3.2 下界 476
25.4 有效算法 478
25.4.1 算法 478
25.4.2 属性 479
25.4.3 活性和复杂度 480
25.5 涉及时间不确定性的下界* 483
25.6 其他结果* 487
25.6.1 同步进程、异步通道* 487
25.6.2 异步进程、同步通道* 488
25.6.3 时间界限* 488
25.7 小结 490
25.8 参考文献注释 490
25.9 题 491
参考文献 493