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

分布式计算 第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　模拟等同Byzantine190

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故障之上模拟异步等同Byzantine201

12.7.1　异步等同Byzantine的定义201

12.7.2　异步Byzantine的定义202

12.7.3　模拟异步等同Byzantine202

练习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