共识问题与 FLP 不可能定理

本文基于模型知识整理（生成时未联网核对），关键结论建议对照经典文献复核。

一句话定义

共识要求一组节点对"某个值"达成一致且该值是某节点真正提议过的；FLP 定理证明在纯异步模型中哪怕只有一个节点崩溃，也不存在必然终止的确定性共识算法——现实系统用超时/随机化换活性来绕过它。

为什么重要

共识是分布式系统"皇冠上的宝石"：分布式锁、选主、全序日志、状态机复制、配置管理，底层全是共识。FLP 则划定了理论边界，解释了为什么所有共识协议都"不完美"——要么靠超时假设，要么靠随机化，要么牺牲终止性。

前置知识

kp-005（故障模型）、kp-013（一致性语义）。

核心概念

• 共识三性质：

- 一致性（agreement）：没有两个非故障节点决定不同的值； - 有效性（validity）：决定值必须来自某个节点的提议； - 终止性（termination）：非故障节点最终做出决定（活性，最易被牺牲）。

• 同步/异步模型：同步=消息延迟有已知上界；异步=无上界。部分同步（partial synchrony）介于其间——"最终同步"，是 Paxos/Raft 实际工作的模型。
• FLP 定理（Fischer, Lynch, Paterson, 1985）：异步模型 + 哪怕一个崩溃故障 ⇒ 不存在保证终止的确定性共识算法。
• 等价问题：共识 ≈ 全序广播（所有节点以相同顺序收到所有消息）≈ 可线性化的"compare-and-set 寄存器"——能解其一即能解其余。

原理与机制

FLP 的直观含义：算法必须对"是否等待某个消息"做决定，而异步网络中永远存在一种消息延迟模式恰好让算法僵持在两个可能决定之间（构造性证明：把关键消息延迟即可冻结任何确定性算法）。它不是说共识不可能，而是说不可能既有确定性又有无条件终止。

三条现实出路：

1. 超时/部分同步假设（Paxos、Raft）：承认消息延迟"最终"有界（工程上总归成立），leader 超时换主推进——牺牲"纯异步"假设。
2. 随机化（Ben-Or、Nakamoto 类）：用随机数打破 FLP 证明所依赖的确定性僵局——以概率 1 终止。
3. 放弃终止（异步重配置类研究）：保确定性与安全，终止性弱化。

为什么 Paxos/Raft 的安全性不靠超时：超时只影响活性（选不出主就卡住）与性能；安全性（不出现两个决定/两条冲突日志）由多数派交集与任期规则保证——这是共识工程与 kp-006"超时不可靠"的和解方式。

图示

提议 → 提议 → 提议
  │      │      │
  └─多数派接受同一值─┘ → 决定 v (一致性+有效性)
终止性: 异步+崩溃 ⇒ 无确定性算法保证 (FLP)
出路:   超时(PartSync) / 随机化 / 弱化终止

直观类比

几个人必须就"今晚吃什么"达成一致，但大家只能传纸条、纸条会迟到任意久。FLP 说：存在一种"纸条全部迟到"的坏运气让任何"按部就班"的规则僵持。现实解法：设个闹钟，超时就换主持人重新提议（Paxos/Raft）；或干脆掷骰子提议（随机化）。

实例或案例

• etcd/Raft：部分同步 + leader 换届；分区时少数派拒绝服务（安全），分区恢复后收敛（活性恢复）。
• Bitcoin/Nakamoto 共识：随机化（PoW 概率竞选）+ 最长链规则，在开放成员（无固定多数派）下近似共识，是 FLP 出路第二条的巨型应用。
• ZooKeeper/ZAB：epoch（任期）+ 多数派，同样绕开 FLP 的方式是"最终同步"假设。

常见误区

• 误区一："FLP 说明共识不可能实现"。它只排除"异步 + 确定性 + 必然终止"三者并存；工程系统通过超时或随机化放弃其一。
• 误区二："共识保证线性一致读"。共识日志保写序，读是否线性一致取决于读路径实现（读 leader 是否确认过任期、是否走 quorum，见 kp-013）。
• 误区三："多数派越大越安全"。安全性由"任意两多数派相交"结构保证，固定 2f+1 容 f；扩大多数派参数只会降低可用性。

与其他知识点的关系

• kp-009：选举是共识的前置阶段。
• kp-018/019：Paxos 与 Raft 是绕过 FLP 的两大工程谱系。
• kp-021：共识系统上构建锁与 fencing 的正确姿势。
• kp-022：把故障模型升级为拜占庭后的共识。

自测题

1. 共识的三性质是什么？实践中最常被牺牲哪条、怎么牺牲？

答：一致性、有效性、终止性；牺牲（无条件）终止性——分区时少数派停服等待，或以超时换"最终"终止。

1. FLP 定理的条件与结论？

答：纯异步（消息延迟无上界）+ 至少一个崩溃故障 ⇒ 不存在保证终止的确定性共识算法。

1. 共识与全序广播为什么等价？

答：全序广播 = 所有消息被所有节点按同一顺序投递；对"下一条消息取什么"达成共识即得全序，反之共识可用全序广播实现。

延伸阅读

• Fischer, Lynch & Paterson, "Impossibility of Distributed Consensus with One Faulty Process"（JACM 1985）。
• Dwork, Lynch & Stockwell, "Consensus in the Presence of Partial Synchrony"（1988）。
• Kleppmann《DDIA》第 9 章。