分布式计算 第2版PDF电子书下载

第1章　引言 1

1.1　分布式系统 1

1.2　分布式计算理论 1

1.3　内容概要 2

1.4　理论和实践的关系 3

本章注释 4

第一部分 6

第2章　消息传递系统中的基本算法 6

2.1　消息传递系统的形式化模型 6

2.1.1　系统 6

2.1.2　复杂度度量 8

2.1.3　伪代码惯例 9

2.2　生成树上的广播和敛播 10

2.2.1 广播 10

2.2.2　敛播 12

2.3　洪泛算法及构造生成树 13

2.4　构造指定根的深度-优先搜索生成树 16

2.5　构造不指定根的深度-优先搜索生成树 17

练习 19

本章注释 20

第3章　环中领导者选举算法 22

3.1　领导者选举问题 22

3.2　匿名环 22

3.3　异步环 23

3.3.1　O（n2）算法 24

3.3.2　O（n log n）算法 24

3.3.3　下界Ω（n log n） 26

3.4　同步环 30

3.4.1　上界O（n） 30

3.4.2　受限算法的下界Ω（n log n） 34

练习 40

本章注释 40

第4章　共享存储器中的互斥 42

4.1　共享存储器系统的形式化模型 42

4.1.1　系统 42

4.1.2　复杂度度量 44

4.1.3　伪代码惯例 44

4.2　互斥问题 44

4.3　使用强原语的互斥 46

4.3.1　二进制测试＆设置寄存器 46

4.3.2　读-改-写寄存器 47

4.3.3　存储器状态数的下界 49

4.4　利用读／写寄存器实现互斥 51

4.4.1　面包店（Bakery）算法 51

4.4.2　两处理器的有界互斥算法 53

4.4.3　n处理器的有界互斥算法 56

4.4.4　读／写寄存器个数的下界 58

4.4.5　快速互斥 62

练习 63

本章注释 64

第5章　容错一致性 66

5.1　有损毁故障的同步系统 66

5.1.1　形式化模型 66

5.1.2　一致性问题 67

5.1.3　一个简单的算法 67

5.1.4　轮数下界 68

5.2　有Byzantine故障的同步系统 72

5.2.1　形式化模型 72

5.2.2　再论一致性问题 73

5.2.3　故障处理器比率的下界 73

5.2.4　一个指数级算法 75

5.2.5 一个多项式算法 78

5.3　异步系统中的不可能性 79

5.3.1　共享存储器-无等待情况 80

5.3.2　共享存储器：一般情况 81

5.3.3　消息传递 87

练习 88

本章注释 90

第6章　因果关系和时间 92

6.1　捕获因果关系 92

6.1.1　先于-发生关系 92

6.1.2　逻辑时钟 94

6.1.3　向量时钟 95

6.1.4　共享存储器系统 98

6.2　应用因果关系的例子 98

6.2.1　一致割 99

6.2.2　“先于-发生”关系的局限性：会话问题 101

6.3　时钟同步 103

6.3.1　物理时钟建模 104

6.3.2　时钟同步问题 106

6.3.3　两处理器情形 107

6.3.4　上限 109

6.3.5　下限 110

6.3.6　应用时钟同步：估计时钟差别 111

练习 112

本章注释 113

第二部分 116

第7章　模拟的形式化模型 116

7.1　问题规格说明 116

7.2　通信系统 116

7.2.1　异步的点到点消息传递 117

7.2.2　异步广播 117

7.3　进程 118

7.4　合法性 120

7.5　模拟 121

7.6　伪代码惯例 122

练习 122

本章注释 122

第8章　广播与多播 123

8.1　广播服务规格 123

8.1.1　基本服务规格 123

8.1.2　广播服务质量 124

8.2　广播服务的实现 126

8.2.1　基本广播服务 126

8.2.2　单源FIFO排序 126

8.2.3　完全排序广播 127

8.2.4　因果关系 129

8.2.5　可靠性 131

8.3　分组多播 132

8.3.1　规格说明 133

8.3.2　多播的实现 134

8.4　一个应用：复制 135

8.4.1　数据库复制 135

8.4.2　状态机方法 136

练习 137

本章注释 137

第9章　分布式共享存储器 140

9.1　可线性化的共享存储器 140

9.2　顺序一致的共享存储器 142

9.3　算法 142

9.3.1　可线性化 143

9.3.2　顺序一致性 144

9.4　下界 147

9.4.1　向分层模型加入时间和时钟 147

9.4.2　顺序一致性 147

9.4.3　可线性化 148

练习 151

本章注释 151

第10章　读／写对象的容错模拟 154

10.1　容错共享存储器模拟 154

10.2　简单的读／写寄存器模拟 155

10.2.1　使用二值寄存器模拟多值寄存器 156

10.2.2　使用单读者寄存器模拟多读者寄存器 160

10.2.3　使用单写者寄存器模拟多写者寄存器 164

10.3　原子快照对象 166

10.3.1　握手过程 167

10.3.2　容量有限的存储器模拟 168

10.4　在消息传递系统中模拟共享寄存器 171

练习 176

本章注释 176

第11章　模拟同步 178

11.1　同步消息传递规格说明 178

11.2　模拟同步处理器 179

11.3　模拟同步处理器与同步通信 181

11.3.1　一个简单的同步器 181

11.3.2　应用：构建宽度优先搜索树 184

11.4　局部模拟与全局模拟 184

练习 185

本章注释 185

第12章　改进算法的容错性 187

12.1　概述 187

12.2　同步处理器和Byzantine故障的建模 188

12.3　在Byzantine故障之上模拟等同Byzantine故障 190

12.3.1 等同Byzantine的定义 190

12.3.2　模拟等同Byzantine 190

12.4　在等同Byzantine故障之上模拟疏漏故障 193

12.4.1　疏漏的定义 193

12.4.2　模拟疏漏 193

12.5　在疏漏故障之上模拟损毁故障 197

12.5.1　损毁的定义 197

12.5.2　模拟损毁 198

12.6　应用：Byzantine故障下的一致性 200

12.7　在Byzantine故障之上模拟异步等同Byzantine 201

12.7.1　异步等同Byzantine的定义 201

12.7.2　异步Byzantine的定义 202

12.7.3　模拟异步等同Byzantine 202

练习 204

本章注释 205

第13章　容错的时钟同步 206

13.1　问题定义 206

13.2　故障处理器的比率 207

13.3　一个时钟同步算法 211

13.3.1　定时故障 211

13.3.2　Byzantine故障 216

13.4　实际时钟同步：识别故障时钟 217

练习 217

本章注释 218

第三部分 222

第14章　随机化 222

14.1　领导者选举：案例研究 222

14.1.1　问题定义的弱化 222

14.1.2　同步的一次性（one-shot）算法 223

14.1.3　同步迭代算法和期望 224

14.1.4　异步系统与对手 225

14.1.5　统一的算法的不可能性 226

14.1.6　概率定义的总结 227

14.2　带有少量共享变量的互斥 227

14.3　一致性 230

14.3.1　一般的算法方案 231

14.3.2　具有常数偏差的公共投币 235

14.3.3　容忍Byzantine故障 236

14.3.4　共享存储器系统 237

练习 237

本章注释 238

第15章　任意对象的无等待模拟 240

15.1　例子：一个FIFO队列 240

15.2　无等待层次 244

15.3　通用性 244

15.3.1　利用比较＆交换实现的非阻塞模拟 245

15.3.2　使用一致性对象的非阻塞算法 246

15.3.3　利用一致性对象实现的无等待算法 248

15.3.4　界定存储需求 250

15.3.5　处理不确定性 252

15.3.6　利用随机化一致性 252

练习 252

本章注释 253

第16章　异步系统中的可解问题 255

16.1　k-set一致性 255

16.2　近似一致性 261

16.2.1　已知输入值范围 262

16.2.2　输入值范围未知 264

16.3　重命名 265

16.3.1　无等待情况 266

16.3.2　一般情况 268

16.3.3　长生存期重命名 268

16.4　k-排斥与k-指派问题 270

16.4.1　解决k-排斥问题的一个算法 271

16.4.2　解决k-指派问题的算法 272

练习 272

本章注释 274

第17章　解决最终稳定系统的一致性问题 276

17.1　在共享存储器系统中保持安全性 276

17.2　故障检测器 278

17.3　利用故障检测器解决一致性 279

17.3.1　利用◇S解决一致性 279

17.3.2　利用◇S解决一致性问题 281

17.3.3　利用Ω解决一致性 281

17.4　故障检测器的实现 282

17.5　使用故障检测器实现状态机复制 283

练习 283

本章注释 284

参考文献 286