一致性共识算法专栏导览

标签

分布式/共识算法

字数

700 字

阅读时间

3 分钟

本专栏收录经典共识算法：异步与部分同步下的不可能性结果、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%）

篇	材料	收什么
07 · PBFT	Practical Byzantine Fault Tolerance（Castro-Liskov, OSDI 1999）	三阶段协议（pre-prepare / prepare / commit）的状态与消息数、 $3 f + 1$ 副本要求、检查点与视图切换；需要外部来源（材料里没有这篇）

阅读顺序

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

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

最后编辑于大约 23 小时前查看完整历史