一致性共识算法专栏导览

标签

分布式/共识算法

字数

988 字

阅读时间

5 分钟

本专栏收录经典共识算法：异步与部分同步下的不可能性结果、Paxos 家族、Raft 与 Zab、拜占庭容错的一般理论，以及把这些算法落到工程里的案例。

区块链场景下的共识（公链的 PoW / PoS / DPoS、联盟链的 PBFT / PoA）已收进区块链共识。两者的交点只有 PBFT 与 Raft —— 它们在这里讲算法本身，在那边讲在链里的用法。

01 · 不可能性结果：FLP 与部分同步 —— FLP 的模型与三条引理、它到底禁止了哪个组合；部分同步的两个模型与 GST； $N \geq 2 t + 1$ 与 $N \geq 3 t + 1$ 两条紧界
02 · Paxos —— P1 → P2c 的完整推导（含"不预测未来而是索取承诺"这一步）、两阶段算法与 acceptor 要持久化的两样东西、learner 的三种设计、dueling proposers 与 Multi-Paxos 的空洞
03 · Raft —— 五条性质、选举限制的 up-to-date 判定、为什么不能数副本提交旧任期的条目、Leader Completeness 的九步反证、joint consensus 与时序不等式
04 · Zab 与 ZooKeeper —— znode / watch / 会话、两条顺序保证与 A-linearizability 的区别、zxid 的 epoch + counter、恢复的两条相反保证
05 · 拜占庭容错：口头消息与书面消息 —— 从条件 A/B 化归到 IC1/IC2；三将军无解与 $n > 3 m$ 界的模拟证明；加 A4（不可伪造签名）后 SM(m) 如何让容错界消失
06 · Spinnaker：用 Paxos 建数据存储 —— master-slave 的四步失效序列、2PC 被否掉的三条理由、Paxos 的收益是"可用性只依赖多数副本存活"、实测代价（读持平、写慢 5%–10%）

阅读顺序

01 → 02 → 03 → 04。01 先划出边界（异步下不可能、部分同步下可行），02 与 03 是这条边界内的两个主流方案，04 是同期在工程侧的落地。

05 与 06 可以独立读：05 把故障模型从「崩溃」换成「任意行为」；06 是 02 的工程延伸。

01 · M. J. Fischer, N. A. Lynch, M. S. Paterson. Impossibility of Distributed Consensus with One Faulty Process. Journal of the ACM 32(2), 1985, pp. 374–382.
02 · L. Lamport. Paxos Made Simple. ACM SIGACT News 32(4), 2001.
03 · D. Ongaro, J. Ousterhout. In Search of an Understandable Consensus Algorithm. USENIX Annual Technical Conference (ATC) 2014, pp. 305–319.
04 · Patrick Hunt, Mahadev Konar, Flavio P. Junqueira, Benjamin Reed. ZooKeeper: Wait-free Coordination for Internet-Scale Systems. USENIX Annual Technical Conference (ATC) 2010.
05 · Leslie Lamport, Robert Shostak, Marshall Pease. The Byzantine Generals Problem. ACM Transactions on Programming Languages and Systems, Vol. 4, No. 3, July 1982, pp. 382–401.
06 · Jun Rao, Eugene J. Shekita, Sandeep Tata. Using Paxos to Build a Scalable, Consistent, and Highly Available Datastore. Proceedings of the VLDB Endowment 4(4), 2011, pp. 243–254.

最后编辑于 7 分钟前查看完整历史