第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