分布式算法PDF|Epub|txt|kindle电子书版本网盘下载

分布式算法PDF格式电子书版下载

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

目录1

出版者的话1

专家指导委员会1

译者序1

前言1

第1章 引言1

1.1 相关主题1

1.2 我们的观点2

1.3 本书内容综述3

1.5 标记7

1.4 参考文献注释7

第一部分 同步网络算法10

第2章 建模Ⅰ：同步网络模型10

2.1 同步网络系统10

2.2 故障11

2.3 输入和输出11

2.4 运行11

2.5 证明方法12

2.6 复杂度度量12

2.7 随机化12

2.8 参考文献注释13

3.1 问题14

3.2 相同进程的不可能性结果14

第3章 同步环中的领导者选择14

3.3 基本算法15

3.4 通信复杂度为O（n log n）的算法17

3.5 非基于比较的算法19

3.5.1 时间片算法20

3.5.2 变速算法20

3.6 基于比较的算法的下界21

3.7 非基于比较的算法的下界＊25

3.8 参考文献注释26

3.9 习题27

4.1.1 问题29

4.1.2 简单的洪泛算法29

4.1 一般网络中的领导者选举29

第4章 一般同步网络中的算法29

4.1.3 降低通信复杂度31

4.2 广度优先搜索32

4.2.1 问题32

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 算法37

4.5 最大独立集39

4.5.2 随机化算法40

4.5.1 问题40

4.5.3 分析＊42

4.6 参考文献注释43

4.7 习题43

第5章 链路故障时的分布式一致性46

5.1 协同攻击问题——确定性版本46

5.2 协同攻击问题——随机化版本48

5.2.1 形式化模型49

5.2.2 算法49

5.2.3 不一致的下限52

5.4 习题54

5.3 参考文献注释54

第6章 进程故障下的分布式一致性56

6.1 问题56

6.2 针对停止故障的算法58

6.2.1 基本算法58

6.2.2 减少通信59

6.2.3 指数信息收集算法61

6.2.4 带鉴别的Byzantine一致性66

6.3 针对Byzantine故障的算法66

6.3.1 举例66

6.3.2 Byzantine一致性问题的EIG算法68

6.3.3 使用二元Byzantine一致的一般的Byzantine一致性问题71

6.3.4 减少通信开销72

6.4 Byzantine一致性问题中进程的个数74

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 算法93

7.1.3 下界＊95

7.2 近似一致性102

7.3 提交问题105

7.3.1 问题105

7.3.2 两阶段提交106

7.3.3 三阶段提交107

7.3.4 消息数的下界109

7.4 参考文献注释111

7.5 习题111

第二部分 异步算法114

第8章 建模Ⅱ：异步系统模型114

8.1 输入／输出自动机114

8.2.1 合成118

8.2 自动机的操作118

8.2.2 隐藏121

8.3 公平性121

8.4 问题的输入和输出123

8.5 属性与证明方法124

8.5.1 不变式断言124

8.5.2 轨迹属性124

8.5.3 安全与活性属性125

8.5.4 合成推理126

8.5.5 层次化证明128

8.6 复杂度衡量130

8.9 参考文献注释131

8.8 随机化131

8.7 不可区分运行131

8.10 习题132

第二部分A 异步共享存储器算法136

第9章 建模Ⅲ：异步共享存储器模型136

9.1 共享存储器系统136

9.2 环境模型138

9.3 不可区分状态140

9.4 共享变量类型140

9.5 复杂度衡量144

9.6 故障144

9.9 习题145

9.8 参考文献注释145

9.7 随机化145

第10章 互斥146

10.1 异步共享存储器模型146

10.2 问题148

10.3 Dijkstra的互斥算法151

10.3.1 算法151

10.3.2 正确性证明154

10.3.3 互斥条件的一个断言证明156

10.3.4 运行时间157

10.4 互斥算法的更强条件158

10.5.1 双进程算法159

10.5 锁定权互斥算法159

10.5.2 n进程算法163

10.5.3 锦标赛算法167

10.6 使用单写者共享存储器的算法170

10.7 Bakery算法171

10.8 寄存器数量的下界173

10.8.1 基本事实174

10.8.2 单写者共享变量175

10.8.3 多写者共享变量175

10.9 使用读-改-写共享变量的互斥179

10.9.1 基本问题179

10.9.2 有界绕过次数180

10.9.3 锁定权185

10.9.4 模拟证明187

10.10 参考文献注释189

10.11 习题190

第11章 资源分配194

11.1 问题194

11.1.1 显式资源说明和互斥说明194

11.1.2 资源分配问题195

11.1.3 哲学家用餐问题196

11.1.4 解法的受限形式197

11.2 对称哲学家用餐算法的不存在性197

11.3.1 等待链199

11.3 右-左哲学家用餐算法199

11.3.2 基本算法200

11.3.3 扩展202

11..4 哲学家用餐随机算法＊204

11.4.1 算法＊205

11.4.2 正确性＊207

11.5 参考文献注释212

11.6 习题213

第12章 一致性215

12.1 问题215

12.2 使用读／写共享存储器的一致性217

12.2.3 双价初始化218

12.2.2 术语218

12.2.1 限制218

12.2.4 无等待终止的不可能性219

12.2.5 单故障终止的不可能性结果221

12.3 读／改／写共享存储器上的一致性问题223

12.4 其他共享存储器类型224

12.5 异步共享存储器系统中的可计算性＊224

12.6 参考文献注释225

12.7 习题226

第13章 原子对象229

13.1 定义和基本结论229

13.1.1 原子对象的定义229

13.1.2 规范无等待原子对象自动机235

13.1.3 原子对象的合成237

13.1.4 原子对象和共享变量237

13.1.5 显示原子性的一个充分条件241

13.2 用读／写变量实现读-改-写原子对象242

13.3 共享存储器的原子快照243

13.3.1 问题243

13.3.2 带无界变量的一个算法244

13.3.3 带有界变量的一个算法＊247

13.4 读／写原子对象250

13.4.1 问题250

13.4.2 证明原子性的其他引理250

13.4.3 带无界变量的一个算法251

13.4.4 两个写者的有界算法254

13.4.5 使用快照的算法258

13.5 参考文献注释259

13.6 习题260

第二部分B 异步网络算法264

第14章 建模Ⅳ：异步网络模型264

14.1 发送／接收系统264

14.1.1 进程264

14.1.2 发送／接收通道264

14.1.4 使用可靠FIFO通道的发送／268

接收系统的特征268

14.1.3 异步发送／接收系统268

14.1.5 复杂度度量269

14.2 广播系统269

14.2.1 进程269

14.2.2 广播通道270

14.2.3 异步广播系统270

14.2.4 采用可靠广播通道的广播系统的特征270

14.2.5 复杂度度量271

14.3 多播系统271

14.3.1 进程271

14.3.2 多播通道271

14.5 习题272

14.3.3 异步多播系统272

14.4 参考文献注释272

第15章 基本异步网络算法274

15.1 环中的领导者选举274

15.1.1 LCR算法275

15.1.2 HS算法278

15.1.3 Peterson Leader算法278

15.1.4 通信复杂度的下界281

15.2 任意网络中的领导者选举286

15.3 生成树的构造、广播和敛播287

15.4 广度优先搜索和最短路径290

15.5.1 问题描述295

15.5 最小生成树295

15.5.2 同步算法：回顾296

15.5.3 GHS算法：概要296

15.5.4 更详细的算法297

15.5.5 特殊消息299

15.5.6 复杂度分析301

15.5.7 GHS算法的正确性证明301

15.5.8 简单“同步”策略302

15.5.9 应用到领导者选举算法中302

15.6 参考文献注释303

15.7 习题303

16.1 问题307

第16章 同步器307

16.2 局部同步器309

16.3 安全同步器313

16.3.1 前端自动机314

16.3.2 通道自动机315

16.3.3 安全同步器315

16.3.4 正确性315

16.4 安全同步器的实现316

16.4.1 同步器Alpha316

16.4.3 同步器Gamma317

16.4.2 同步器Beta317

16.5 应用320

16.5.1 领导者选举321

16.5.2 深度优先搜索321

16.5.3 最短路径321

16.5.4 广播与确认321

16.5.5 最大独立集321

16.6 时间下界321

16.7 参考文献注释324

16.8 习题324

的转换326

17.1.1 问题326

17.1 从共享存储器模型到网络模型326

第17章 共享存储器与网络326

17.1.2 无故障时的策略327

17.1.3 容忍进程故障的算法332

17.1.4 对于n/2故障的不可能性结果335

17.2 从网络模型转换到共享存储器模型336

17.2.1 发送／接收系统336

17.2.2 广播系统338

17.2.3 异步网络中一致性的不可能性338

17.3 参考文献注释339

17.4 习题339

18.1.1 发送／接收系统341

18.1 异步网络的逻辑时间341

第18章 逻辑时间341

18.1.2 广播系统343

18.2 使用逻辑时间的异步算法344

18.2.1 时钟的走动344

18.2.2 延迟未来事件345

18.3 应用346

18.3.1 银行系统346

18.3.2 全局快照348

18.3.3 模拟一台单状态机器349

18.4 从实际时间算法到逻辑时间算法的变换＊352

18.5 参考文献注释352

18.6 习题353

19.1 发散算法的终止检测355

19.1.1 问题355

第19章 一致全局快照和稳定属性检测355

19.1.2 DijkstraScholten算法356

19.2 一致全局快照360

19.2.1 问题360

19.2.2 ChandyLamport算法361

19.2.3 应用364

19.3 参考文献注释366

19.4 习题367

第20章 网络资源分配369

20.1 互斥369

20.1.1 问题369

20.1.3 循环令牌算法370

20.1.2 模拟共享存储器370

20.1.4 基于逻辑时间的算法372

20.1.5 LogicalTimeME算法的改进374

20.2 通用资源分配376

20.2.1 问题376

20.2.2 着色算法377

20.2.3 基于逻辑时间的算法377

20.2.4 无环有向图算法378

20.2.5 哲学家饮水＊379

20.3 参考文献注释383

20.4 习题383

21.1 网络模型386

第21章 带进程故障的异步网络计算386

21.2 有故障环境中一致性的不可能性387

21.3 随机算法388

21.4 故障检测器390

21.5 k一致性393

21.6 近似一致性394

21.7 异步网络的计算能力＊395

21.8 参考文献注释396

21.9 习题396

第22章 数据链路协议399

22.1 问题阐述399

22.2 Stenning协议400

22.3 位变换协议403

22.4 可重排序的有界标志协议406

22.4.1 关于重排序和复制的不可能407

性结论407

22.4.2 容许丢失和重排序的有界标408

志协议408

22.4.3 不存在容许消息丢失和重排序的高效协议412

22.5 容许进程崩溃414

22.5.1 简单的不可能性结论415

22.5.2 更复杂的不可能性结论415

22.5.3 实用的协议418

22.7 习题423

22.6 参考文献注释423

第三部分 部分同步算法428

第23章 建模Ⅴ：部分同步系统模型428

23.1 MMT定时自动机428

23.1.1 基本定义428

23.1.2 操作432

23.2 通用定时自动机434

23.2.1 基本定义434

23.2.2 将MMT自动机转化为通用定时437

自动机437

23.2.3 操作440

23.3.1 不变式441

23.3 属性和证明方法441

23.3.2 定时轨迹属性443

23.3.3 模拟444

23.4 构造共享存储器和网络系统的模型449

23.4.1 共享存储器系统449

23.4.2 网络449

23.5 参考文献注释449

23.6 习题450

第24章 部分同步的互斥452

24.1 问题452

24.2 单寄存器算法453

24.3 对时间故障的回复性459

24.4 不可能性结果461

24.4.1 时间下界462

24.4.2 最终时间界限的不可能性结果＊462

24.5 参考文献注释463

24.6 习题463

第25章 部分同步的一致性466

25.1 问题466

25.2 故障检测器467

25.3 基本结论468

25.3.1 上界468

25.3.2 下界469

25.4 有效算法470

25.4.1 算法471

25.4.2 安全属性472

25.4.3 活性和复杂度473

25.5 涉及时间不确定性的下界＊475

25.6 其他结果＊480

25.6.1 同步进程、异步通道＊480

25.6.2 异步进程、同步通道＊481

25.6.3 最终时间界限＊481

25.7 小结483

25.8 参考文献注释483

25.9 习题483

参考文献486

索引512