江峰，教授级高工，中国电信集团云计算专业首席专家，中国计算机学会信息存储专委会委员。长期在分布式存储领域从事理论研究和工程实践工作。

受内容分发网络(CDN)的启发，在业内首次提出和设计了“为写而生”的内容存储网络(CSN)——CTOOS。CTOOS实现了广域分布式海量数据存储服务的高可用、低时延和强一致，达到了单命名空间跨池数十个、实存容量过EB的规模，并长期稳定运行，为企业创造了可观的收益，技术水平达到了国内领先。

以第一作者在国际期刊会议上发表论文多篇，以第一发明人申请专利十多件，以第一完成人获得省部级、中国电信集团科技进步奖多次。

1 初识分布式 1
1．1 什么是分布式系统1
1．2 分布式算法的意义  3
1．3 “两将军”问题3
1．4 设计分布式算法的主要挑战8
1．4．1 并发执行 8
1．4．2 进程失败  9
1．4．3 链路失败 10

2 算法模型 12
2．1 I/O 自动机 12
2．1．1 基本模型 13
2．1．2 组合模型15
2．1．3 隐藏操作 16
2．1．4 与业务逻辑的关系18
2．1．5 小结 19
2．2 编程模型  20
2．2．1 调用关系 ． 21
2．2．2 事件和事件处理器 ． 23
2．2．3 抽象和实现 ． 25

3 系统模型 30
3．1 进程  30
3．2 消息  31
3．3 进程启动  32
3．4 进程失败  33
3．4．1 崩溃式失败 ． 33
3．4．2 遗漏式失败 ． 34
3．4．3 恢复后崩溃失败 ． 35
3．4．4 拜占庭失败 ． 36
3．4．5 各种失败的关系 ． 37
3．5 时钟  37
3．5．1 本地时钟和全局时钟 ． 37
3．5．2 因果顺序不变 ． 38
3．5．3 逻辑时钟 ． 41
3．5．4 时钟偏移 ． 42
3．6 时间假设  43
3．6．1 异步系统 ． 44
3．6．2 同步系统 ． 45
3．6．3 部分同步系统 ． 46
3．7 安全性和活性  47
3．8 组合模型  48
3．9 多数派  50
3．10 性能度量  51

4 链路 52
4．1 公平丢包链路  53
4．1．1 定义 ． 53
4．1．2 消息系统 ． 54
4．2 顽固链路  57
4．2．1 定义 ． 57
4．2．2 静音型失败算法 ． 57
4．3 可靠链路  60
4．3．1 定义 ． 61
4．3．2 静音型失败算法 ． 61
4．4 先进先出可靠链路  63
4．4．1 定义 ． 63
4．4．2 静音型失败算法 ． 63
4．5 日志可靠链路  65
4．5．1 定义 ． 65
4．5．2 恢复型失败算法 ． 66
4．6 其他说明  69

5 失败检测和选主 70
5．1 失败检测  70
5．2 完美失败检测  71
5．2．1 定义 ． 71
5．2．2 停止型失败算法 ． 71
5．3 最终完美失败检测  73
5．3．1 定义 ． 73
5．3．2 噪音型失败算法 ． 74
5．4 选主  76
5．4．1 定义 ． 76
5．4．2 停止型失败算法 ． 77
5．5 最终选主  78
5．5．1 定义 ． 79
5．5．2 噪音型失败算法 ． 79
5．5．3 恢复失败型算法 ． 81

6 可靠广播 85
6．1 尽力广播  85
6．1．1 定义 ． 86
6．1．2 静音型失败算法 ． 86
6．2 正则可靠广播  87
6．2．1 定义 ． 87
6．2．2 停止型失败算法 ． 88
6．2．3 静音型失败算法 ． 90
6．3 统一可靠广播  91
6．3．1 定义 ． 92
6．3．2 停止型失败算法 ． 92
6．3．3 静音型失败算法 ． 94
6．4 顽固广播  97
6．4．1 定义 ． 97
6．4．2 恢复型失败算法 ． 97
6．5 概率广播  98
6．5．1 定义 ． 99
6．5．2 随机化算法：尽力推送 ． 100
6．5．3 随机化算法：推拉结合 ． 106
6．6 先进先出广播  112
6．6．1 定义 ． 113
6．6．2 静音型失败算法 ． 113
6．7 因果可靠广播  115
6．7．1 定义 ． 115
6．7．2 静音型失败算法 ． 116
6．7．3 停止型失败算法 ． 118
?6．7．4 静音型失败算法：基于向量时间  120

7 共享内存 124
7．1 介绍  124
7．1．1 前提假设 ． 125
7．1．2 操作顺序 ． 126
7．1．3 操作失败 ． 127
7．2 (1-N)正则注册器 ． 128
7．2．1 定义 ． 128
7．2．2 停止型失败算法 ． 130
7．2．3 静音型失败算法 ． 132
7．3 (1-N)原子注册器 ． 135
7．3．1 定义 ． 136
7．3．2 停止型失败算法 ． 137
7．3．3 静音型失败算法 ． 140
7．4 (N-N)原子注册器  144
7．4．1 定义 ． 144
7．4．2 停止型失败算法 ． 147
7．4．3 静音型失败算法 ． 149
7．5 (1-N)日志正则注册器 ． 152
7．5．1 操作顺序 ． 153
7．5．2 定义 ． 153
7．5．3 恢复型失败算法 ． 155
7．6 (N-N)顺序注册器  158
7．6．1 定义 ． 159
7．6．2 正则、顺序与原子注册器的比较  160
7．6．3 叠加性 ． 163
7．6．4 静音型失败算法 ． 164
7．7 因果注册器和先进先出注册器  169
7．8 CAP 理论 ． 170

8 共识 173
8．1 正则共识  174
8．1．1 定义 ． 174
8．1．2 停止型失败算法：泛洪共识  175
8．1．3 停止型失败算法：等级共识  178
8．2 统一共识  180
8．2．1 定义 ． 180
8．2．2 停止型失败算法：泛洪统一共识  181
8．2．3 停止型失败算法：等级统一共识  184
8．3 适用于噪音型失败模型的统一共识  188
8．3．1 概述 ． 188
8．3．2 代次变更 ． 189
8．3．3 代次共识 ． 195
8．3．4 噪音型失败算法 ． 200
8．3．5 Paxos 协议 ． 204
8．4 日志统一共识  206
8．4．1 定义 ． 206
8．4．2 日志代次变更 ． 207
8．4．3 日志代次共识 ． 209
8．4．4 恢复型失败算法 ． 213
8．5 随机共识  215
8．5．1 定义 ． 216
8．5．2 共币 ． 217
8．5．3 静音型失败算法：随机二值正则共识  222
8．5．4 静音型失败算法：随机多值正则共识  229
8．6 统一快速共识  231
8．6．1 定义 ． 231
8．6．2 静音型失败算法 ． 232
8．7 统一序列共识  236
8．7．1 概述 ． 236
8．7．2 定义 ． 237
8．7．3 基于单值共识的算法 ． 239
8．8 适用于噪音型失败模型的统一序列共识  240
8．8．1 概述 ． 241
8．8．2 代次序列共识 ． 241
8．8．3 噪音型失败算法 ． 252
8．8．4 Multi-Paxos 和Raft 协议  254

9 共识的应用 256
9．1 全序广播  256
9．1．1 定义 ． 258
9．1．2 算法：基于共识的全序广播  259
9．2 复制状态机  263
9．2．1 定义 ． 263
9．2．2 算法：基于全序广播的状态复制  264
9．3 信号量  265
9．3．1 定义 ． 265
9．3．2 算法：基于全序广播的信号量  267
9．4 原子提交  270
9．4．1 介绍 ． 271
9．4．2 定义 ． 272
9．4．3 停止型失败算法：基于共识的非阻塞式原子提交  273
9．5 组成员关系  276
9．5．1 定义 ． 277
9．5．2 停止型失败算法：基于共识的组成员关系  278
9．6 可停止全序广播  280
9．6．1 定义 ． 281
9．6．2 停止型失败算法：基于共识的可停止全序广播  283
9．7 可重配复制状态机  287
9．7．1 进程的加入和离开 ． 288
9．7．2 定义 ． 289
9．7．3 停止型失败算法：基于可停止全序广播  291

10 基于时钟的算法 295
10．1 包含时钟的时间假设  295
10．2 基于时钟同步的失败检测  297
10．2．1 完美失败检测 ． 297
10．2．2 最终完美失败检测 ． 299
10．3 基于网络同步的虚拟时钟  301
10．3．1 定义 ． 302
10．3．2 停止型失败算法 ． 302
10．4 时钟同步与网络同步的等价性  303
10．5 实时操作系统的意义  305

11 结束语 306
参考文献 307