FLP不可能性定理与分布式共识理论

前言

CAP 定理中的 $P$（分区容忍性）在完全异步系统里其实就是 FLP 的常态：

  • 在 CAP 的世界里：当发生 $P$ 时，如果你追求 $C$（强一致性），节点就必须死等对端恢复，从而被迫放弃 $A$（可用性/终止性）。
  • 在 FLP 的世界里：因为网络完全异步，哪怕没有发生物理分区，仅仅是网络延迟波动，或者节点正在经历 Stop-the-World (STW) 垃圾回收，对于其他节点而言，此时此刻的观测结果与“发生物理分区”或“对端彻底宕机”是绝对不可区分的。

所以，FLP 定理用严格的数学证明阐明了：在完全异步的网络下，由于无法区分“慢”与“死”，CAP 中的 $P$ 是随时、随地、无条件存在的。因此，系统绝对无法同时完美获得 $C$ 和 $A$（即 FLP 中的 Agreement 与 Termination），两者的物理本质完全一致。

“关键信息”与双稳态的死锁

在初始双稳态下，系统状态犹如一杆悬空的平衡秤。失联的节点 $B$ 到底掌握了什么初始输入？或者它失联前有没有处理它手里的关键消息？

  • 如果 $B$ 掌握了走向 $0$ 的关键信息（例如只有它的输入为 $0$），而它此刻因某种原因“失联”了：
  • 若其他节点选择“一直等 $B$”：万一 $B$ 是真的彻底宕机，其他节点将会无限期卡死，直接破坏了终止性（Liveness）。
  • 若其他节点选择“不等 $B$”：直接越过它达成全为 $1$ 的共识，万一 $B$ 仅仅是遭遇了极端的网络延迟或 STW，它其实还活着且保留着决断为 $0$ 的关键信息，等它恢复并带着旧数据醒来时，共识便会被撕裂，直接破坏了一致性（Safety）。

核心洞察：在完全异步系统中，一个节点宕机和一个节点慢到无限久，在其他节点眼里没有本质区别；而只要这种区别无法被确定，共识协议就无法保证在所有情况下都完成决策。

FLP（Fischer–Lynch–Paterson）不可能性定理是分布式一致性理论的核心基石。其核心结论揭示了分布式计算的本质边界：

在完全异步（Asynchronous）系统模型中，即使仅允许一个进程发生崩溃（Crash）故障，也不存在任何确定性（Deterministic）的分布式共识算法，能够同时保证安全性和确定性终止。

这一定理并非宣告了共识在工程上的不可靠性，而是阐明了在**“理想化异步模型”与“确定性算法”**的组合下，强终止性（Termination）与容错性（Fault Tolerance）之间存在不可调和的根本冲突。后续的 Paxos、Raft 等实用共识协议，均是通过放宽异步假设或引入随机化来绕过 FLP 定理的限制。

背景与系统模型

本文采用 FLP 原文及其经典文献中的标准模型描述：

  • 完全异步模型（Fully Asynchronous Model）：

    1. 消息时延无界：网络传输延迟可能任意长，但不存在丢包（消息最终必达）。
    2. 进程速度无界：进程的相对执行速度可任意波动，没有已知的上界与下界。
    3. 无时钟同步：系统缺乏全局时钟或共享的时间步进机制。

  • 故障模型（Fail-Stop Model）：
    任意时刻最多允许 $1$ 个进程发生崩溃终止（Crash-Stop）。崩溃的进程会立即停止运行且不再发送任何消息，但排除发送错误或恶意消息的拜占庭行为（Non-Byzantine）。

在完全异步的语境下，由于缺乏时间边界，进程无法通过“超时”机制区分“对端崩溃”与“网络极端延迟”。这种拓扑和逻辑上的不可区分性，正是 FLP 定理证明的核心切入点。

共识问题的形式化定义

一个可行的分布式共识算法必须在任意合法的异步调度下，严格满足以下三个形式化性质：

  1. 一致性（Agreement / Safety）：所有非故障进程最终决定（Decide）的达成值必须完全相同。
  2. 有效性（Validity / Non-triviality）：决定的输出值必须源于某个进程的初始输入值，防止算法输出无意义的预设值。
  3. 终止性（Termination / Liveness）：所有非故障进程最终都能在有限步内做出决定。

FLP 定理证明的核心，在于证实确定性算法无法在最坏的异步调度（Message Delivery Order）和进程速率下，同时完美兼顾这三者。

FLP 定理（非正式表述）

在至少包含两个进程的完全异步系统中，只要允许发生单点崩溃故障，就不存在任何确定性共识算法，能够保证在所有可能的执行序列中皆满足一致性、有效性与终止性。

证明概要与核心逻辑

FLP 的证明极其精巧，主要利用了**配置价性（Configuration Valency）与事件调度（Event Schedules）**的分析技巧。其核心思想分为以下几个关键步骤：

1. 配置与事件系统

  • 配置（Configuration）：代表系统在某一时刻的全局快照，包含所有进程的本地状态以及网络中尚未送达的消息集合（Message Buffer）。
  • 事件（Event）：定义为一个原子步 $e = (p, m)$，即进程 $p$ 接收并处理网络中的一条消息 $m$，随后更新自身状态并可能广播新消息。配置通过事件的驱动发生状态转移。

2. 价性的形式化定义

  • $0$-单稳态（$0$-univalent）：从当前配置出发，无论后续的事件如何调度，系统最终达成的共识值只能是 $0$。
  • $1$-单稳态（$1$-univalent）：从当前配置出发，无论后续的执行路径如何，系统最终达成的共识值只能是 $1$。
  • 双稳态（Bivalent）：从当前配置出发，系统的最终命运尚未决断。通过某些调度路径可以走向 $0$-单稳态，而通过另一些调度路径则可以走向 $1$-单稳态。

3. 引理一：初始双稳态配置的存在性

  • 根据有效性约束，全 $0$ 输入的配置必为 $0$-单稳态，全 $1$ 输入的配置必为 $1$-单稳态。
  • 构造一条“平行宇宙链条（Neighboring Chain）”，每次仅改变一个进程的初始输入。在此链条中，必然存在两个相邻的初始配置 $X$ 和 $Y$，它们仅在进程 $P$ 的输入上不同，且分别属于 $0$-单稳态和 $1$-单稳态。
  • 此时若进程 $P$ 遭遇网络分区或延迟而无法与其他节点通信，剩余的 $N-1$ 个进程在 $X$ 和 $Y$ 两种配置下观测到的局部世界完全相同。由于无法区分，它们在处理相同的消息序列后必然做出相同的决策，这与 $X$ 和 $Y$ 互为不同单稳态的前提产生理论矛盾。

严密反证过程

利用反证法。假设系统不存在任何初始双稳态配置，即所有初始配置要么是 $0$-单稳态，要么是 $1$-单稳态。

构造一个初始输入全为 $[0,0,0,…,0]$ 的配置，根据有效性，其必然属于 $0$-单稳态。随后我们逐位翻转进程的初始输入，构建一组平行初始配置：

  • $[1,0,0,0,…,0]$
  • $[1,1,0,0,…,0]$
  • $[1,1,1,0,…,0]$
  • …
  • $[1,1,1,1,…,1]$ （此配置必然属于 $1$-单稳态）

在这条从全 $0$ 到全 $1$ 的初始配置链条中，由于起点命运为 $0$，终点命运为 $1$，且中间不存在任何双稳态，则中间必然存在某一对相邻的初始配置 $X_i$ 和 $X_{i+1}$，分别代表 $0$-单稳态和 $1$-单稳态，并且两者的输入有且仅差了一个进程 $p$：

  • $X_i = [1,1,…,1,\mathbf{0},0,…,0]$
  • $X_{i+1} = [1,1,…,1,\mathbf{1},0,…,0]$

此时进行反证反击：我们故意让进程 $p$ 在系统启动的瞬间发生崩溃（Crash）或者遭遇极端的网络分区/STW。这意味着进程 $p$ 保持绝对的沉默，既不发送消息，也不处理消息。

对于集群中除了 $p$ 以外的其余 $n-1$ 个非故障进程而言：

  1. 在宇宙 $X_i$ 中：它们收不到来自进程 $p$ 的任何消息。由于 $X_i$ 是 $0$-单稳态，为了满足容错下的终止性，其余 $n-1$ 个进程即使在缺失 $p$ 的情况下，最终也必须终止并决定 $0$。
  2. 在宇宙 $X_{i+1}$ 中：它们同样无法从进程 $p$ 获得任何消息。由于 $X_{i+1}$ 是 $1$-单稳态，同理，其余 $n-1$ 个进程在缺失 $p$ 的情况下，最终也必须终止并决定 $1$。

关键矛盾爆发：由于 $X_i$ 和 $X_{i+1}$ 的唯一区别只在于进程 $p$ 的输入，现在进程 $p$ 彻底沉默了。对于其余 $n-1$ 个进程来说，它们在宇宙 $X_i$ 和宇宙 $X_{i+1}$ 中所看到的初始状态、收到的网络消息序列以及它们自身的局部状态变迁完全是一模一样的。这 $n-1$ 个节点在两个宇宙中处于完全等价的观测状态，根本无法判断自己究竟置身于哪一个宇宙。

既然从可观测角度完全无法区分，根据确定性算法的代码必然性，这 $n-1$ 个进程在宇宙 $X_i$ 中做出什么决策，就必然在宇宙 $X_{i+1}$ 中做出完全相同的决策：

  • 如果它们最终都决定了 $0$，那么在宇宙 $X_{i+1}$ 里，算法就打破了“从 $1$-单稳态出发只能决定 $1$”的绝对定义；

  • 如果它们最终都决定了 $1$，那么在宇宙 $X_i$ 里，算法就打破了“从 $0$-单稳态出发只能决定 $0$”的绝对定义。

  • 结论：反证假设破产，系统在初始时，必然存在至少一个双稳态配置。

4. 引理二：双稳态配置的无限保持

核心引理陈述：从任一双稳态（Bivalent）配置出发，总能找到一个特定的下一步事件，使得系统转移后的新配置依然保持双稳态。

证明方法：反证法。

反证假设：假设从双稳态配置 $C$ 出发，所有可能的单步事件都会导致系统立刻落入单稳态（要么进入 $0$-单稳态，要么进入 $1$-单稳态），即系统必定会从双稳态中“逃逸”。

设 $e = (p, m)$ 是在配置 $C$ 中一个合法且待处理的临界事件（进程 $p$ 接收消息 $m$）。令 $\mathcal{E}$ 为从 $C$ 出发、不包含事件 $e$ 的所有可达后继配置的集合。由于网络异步模型允许消息被无限期延迟，在走向最终决策的路径上，我们总可以先扣下事件 $e$ 暂不投递。

步骤一：构建单稳态相邻边界

根据双稳态的定义，从 $C$ 出发必然存在两条命运分叉的决断路径：

  1. 一条最终决定 $0$，由于消息最终必须送达，事件 $e$ 终究会被应用。因此在走向 $0$ 的路径上，必然能找到一个配置 $D_0 \in \mathcal{E}$，使得 $e(D_0)$ 属于 $0$-单稳态。
  2. 另一条最终决定 $1$，同理能找到一个配置 $D_1 \in \mathcal{E}$，使得 $e(D_1)$ 属于 $1$-单稳态。

由于 $\mathcal{E}$ 是一个连通的离散状态空间，从指向 $0$ 的区域走向指向 $1$ 的区域，在思想实验的链条中必有一个交界点。也就是说，在 $\mathcal{E}$ 中必然存在两个相邻的配置 $F_0$ 和 $F_1$，它们经由某个单步事件 $e’ = (p’, m’)$ 相连（即 $F_1 = e’(F_0)$），且满足：

  • $e(F_0)$ 是 $0$-单稳态。
  • $e(F_1) = e(e’(F_0))$ 是 $1$-单稳态。

(注：此处意味着 $F_0$ 处于一个极其微妙的平衡点，如果直接让 $p$ 接收 $m$（执行 $e$），系统锁定为 $0$；如果系统先多走一步让 $p’$ 处理 $m’$（执行 $e’$ 到达 $F_1$），在这个新状态下让 $p$ 再接收 $m$，系统则会戏剧性地骤变成 $1$-单稳态。)

现在，我们通过分析事件 $e$ 与 $e’$ 的拓扑关系（利用独立事件的可交换性引理）来推导矛盾。

步骤二：分情况讨论与矛盾推导

Case 1: $p \neq p’$（$e$ 和 $e’$ 作用于不同的进程）

当两个事件作用于不同的进程时，它们在空间上相互独立，执行顺序在物理上完全可交换（Commutativity）。

  • 路径一：从 $F_0$ 出发先执行 $e’$ 再执行 $e$，到达的配置为 $e(e’(F_0)) = e(F_1)$。根据前文边界选择，该配置为 $1$-单稳态。
  • 路径二：从 $F_0$ 出发先执行 $e$ 再执行 $e’$，到达的配置为 $e’(e(F_0))$。由于 $e(F_0)$ 已被确认为 $0$-单稳态，根据单稳态的不可逆性（一旦锁定，后续任意扩展皆保持同价），$e’(e(F_0))$ 必然仍是 $0$-单稳态。

矛盾：由于 $p \neq p’$，在拓扑上 $e(e’(F_0))$ 与 $e’(e(F_0))$ 在物理上是完全一模一样的同一个全局配置。同一个全局配置不可能既是 $0$-单稳态又是 $1$-单稳态，此情况矛盾！

Case 2: $p = p’$（$e$ 和 $e’$ 作用于同一进程 $p$）

当两封消息都堆在同一个进程 $p$ 面前时，事件顺序不再可交换。此时我们引入“网络分区/幽灵节点”的思想来制造不可区分性：

  1. 在宇宙 A 中：系统处于配置 $e(F_0)$（已知为 $0$-单稳态）。此时让进程 $p$ 立即崩溃（或陷入严重网络分区而彻底沉默）。由于共识协议必须满足终止性（Termination），其余 $N-1$ 个非故障进程在无法与 $p$ 通信的情况下，最终必须达成某个决定值 $v_0$。因为起点是 $0$-单稳态，这个决定值 $v_0$ 必然等于 $0$。整个决策过程仅依赖于其余进程的状态、非 $p$ 的消息流通以及“$p$ 已沉默”的事实。
  2. 在宇宙 B 中：系统处于配置 $e(F_1) = e(e’(F_0))$（已知为 $1$-单稳态）。同样在此时让进程 $p$ 立即崩溃并保持沉默。其余 $N-1$ 个进程在不知情的情况下继续运行并尝试达成共识。

终极矛盾：对比宇宙 A 和宇宙 B，进程 $p$ 无论是在宇宙 B 里先后悄悄处理了 $m’$ 和 $m$，还是在宇宙 A 里只处理了 $m$，由于它处理完后就立刻遭遇分区并闭嘴，它更新后的局部状态根本无法通过网络传递出去。对于其余 $N-1$ 个进程而言，它们看到的初始状态、网络中剩余的消息、以及非 $p$ 节点的局部行为在两个宇宙中完全相同。

既然观测视角完全无法区分，根据确定性算法的必然性，其余节点在宇宙 B 中也必须做出和宇宙 A 一模一样的决定——即决定 $0$。但这与 $e(F_1)$ 属于 $1$-单稳态（最终必须决定 $1$）的定义产生了不可调和的理论破产！

步骤三：最终推论

无论是 Case 1 还是 Case 2，反证假设都会推导出逻辑层面的彻底崩溃。

  • 结论：反证假设不成立，在双稳态配置的可达集合中，必然存在至少一个后继配置，在其上应用事件 $e$ 后系统依然保持双稳态。这意味着，一个拥有最高网络调度权限的恶意攻击者（Adversary），总能通过精准控制关键消息的延迟与送达顺序，无限期地将系统滞留在没有决断力的双稳态中，使其永远无法达成最终共识。

5. 最终推论

因为系统存在一条能够无限保持双稳态的合法调度路径，导致任何确定性共识算法在最坏执行序列下都会陷入无限循环，无法在有限步内“一锤定音”地做出决定（破坏了 Termination 活性）。至此，FLP 不可能性定理成立。

影响

尽管理论封死了完全异步下的绝对共识，但现代分布式系统通过放宽模型假设或弱化性质保证，在实际工程中成功实现了高可用的共识：

  • 部分同步模型（Partial Synchrony）：引入全局稳定时间（GST, Global Stabilization Time）的概念。在此时间之后，网络时延恢复有界，例如 PBFT、Tendermint 协议。
  • 随机化机制（Randomization）：通过引入不确定性来打破恶劣调度器的死锁。例如 Raft 协议采用的随机选举超时机制，以及 Paxos 在冲突时的随机退避重试，利用概率性终止绕过 FLP。
  • 弱化终止性约束：经典 Paxos 保证了绝对的安全性（Safety），但其活性（Liveness）仅在“网络相对稳定的周期内（Stable Periods）”得到保证，允许在极端冲突下出现活锁。
  • 概率共识与最终一致性：如部分区块链协议（POW、POS）允许在短期内存在分叉，通过工作量证明或权重累积实现概率性的最终一致，从而在追求可用性与分区容忍性的同时弱化即时终止性。

经典共识协议中的双稳态与活锁表现

根据 FLP 不可能性定理，任何确定性的分布式共识协议在完全异步的网络下，都无法同时保证安全性（Safety）与终止性（Termination）。在实际工程设计中，这些协议为了死守安全性，在遭遇极端恶劣的网络调度（Adversary Schedule）时，都会表现出被无限期滞留在“双稳态（Bivalent）”而无法收敛的现象。

1. Paxos 中的“双稳态”：提案竞争导致的活锁（Duelling Proposers）

在 Multi-Paxos / Basic Paxos 中，所谓“双稳态”并不是协议定义的状态，而是指一种系统长期无法收敛的活锁现象：多个提案者不断互相覆盖提案编号，导致决议始终无法进入稳定的 Accept 阶段。

竞争机制如何导致活锁：

  1. 系统中存在两个活跃提案者 $Proposer_1$ 与 $Proposer_2$。
  2. $Proposer_1$ 发起 Prepare(n_1) 并成功获得多数派（Quorum）的 Promise，此时其提案值（例如 0）具有潜在决议基础。
  3. 在 $Proposer_1$ 进入 Accept(n_1, v) 阶段之前，$Proposer_2$ 发起更高编号的 Prepare(n_2)（$n_2 > n_1$），并同样获得 Quorum Promise。
  4. $Acceptor$ 更新承诺，拒绝所有小于 $n_2$ 的提案编号。
  5. $Proposer_1$ 迟到的 Accept(n_1, v) 被全部拒绝，原本可能形成的决议被打断。
  6. $Proposer_1$ 被迫发起更高编号提案 $n_3 > n_2$ 以重新争夺主导权。

调度导致的无限竞争：

在异步调度下，如果网络持续交错延迟两个提案者的 Prepare / Accept 阶段：

  • 提案编号不断递增
  • 每一轮都有人“抢先一步”
  • 没有任何一个提案能稳定进入 quorum accept

系统表现为在不同提案值之间不断摇摆，但始终无法完成一次稳定决议。

2. Raft 中的“双稳态”：Split Vote 导致的选举空转

Raft 中更常见的“类双稳态现象”发生在Leader 选举阶段的 split vote（票数均分），表现为系统无法产生领导者，从而无法推进日志复制。

选举卡住的机制：

  1. 系统初始无 Leader，所有节点处于 Follower 状态。
  2. 多个节点同时发生 election timeout，进入 Candidate 状态，并各自递增 currentTerm。
  3. Candidate 同时广播 RequestVote 请求。
  4. 在节点数较小或网络调度对称的情况下，投票结果可能被均匀分割。
  5. 没有任何 Candidate 获得多数票（$\lfloor N/2 \rfloor + 1$），选举失败。
  6. 当前 Term 内无法产生 Leader，日志复制停止，系统无法前进。

无限选举循环：

在完全异步模型下，如果调度持续保持“近似同步”：

  • 各节点定时器几乎同时触发
  • 投票持续被平均分割
  • Term 不断递增（$T \rightarrow T+1 \rightarrow T+2$ …）
  • 每一轮都没有 Leader 产生

系统表现为持续选举但永远无 Leader 的空转状态。

3. PBFT 中的“双稳态”：View Change 震荡

在 PBFT 中，“双稳态”表现为系统在多个视图之间不断切换，但始终无法稳定进入共识完成阶段。

机制链条：

  1. 系统在 View $v$ 下由 Primary 提议 Pre-prepare 消息。
  2. 网络延迟或恶意节点干扰导致 Prepare / Commit 阶段无法达成法定人数（$\frac{2}{3}N + 1$）。
  3. 副本节点触发超时，发起 View-Change，认为主节点失效。
  4. 系统切换到 View $v+1$，产生新的 Primary。
  5. 新 Primary 再次遭遇同样的延迟或调度干扰。
  6. View Change 被再次触发，进入 View $v+2$。

无限视图切换：

在强异步调度下，如果网络延迟始终大于超时阈值：

  • View Change 不断触发
  • 共识始终停留在准备阶段之前
  • 系统无法进入稳定的 Commit 阶段

最终表现为视图在不断变化，但没有任何一个视图能够完成共识。

4. PoW 中的“双稳态”：等长分叉的持续竞争

在 PoW（如比特币）中，共识是概率性的，但在最坏异步调度下仍可能出现“类双稳态”：等长链分叉的长期竞争状态。

分叉竞争机制：

  1. 系统出现两条等长链 $C_0$ 与 $C_1$。
  2. 网络被恶意或自然分区为两个算力相当的子集 $A$ 与 $B$。
  3. $A$ 在 $C_0$ 上挖出新区块，使其长度变为 $H+1$。
  4. 调度器延迟该区块传播，使 $B$ 不可见。
  5. $B$ 同时在 $C_1$ 上挖出新区块，使其也变为 $H+1$。
  6. 当消息最终交叉传播时，两条链长度再次对齐。

无限对称增长：

如果调度器持续维持对称性：

  • 两边轮流挖出新区块
  • 区块传播始终被延迟到“刚好同步”
  • 两条链长期保持等长竞争

尽管现实中 PoW 会快速收敛，但在理论最坏异步模型中，分叉可以被无限维持。

参考资料

  • Fischer, M. J., Lynch, N. A., & Paterson, M. S. (1985). Impossibility of distributed consensus with one faulty process. Journal of the ACM (JACM), 32(2), 374–382.
  • Leslie Lamport. Paxos made simple. 2001.
  • Diego Ongaro, John Ousterhout. In Search of an Understandable Consensus Algorithm (Raft). 2014.
分布式 > 理论基础
#分布式系统 #一致性理论 #FLP不可能性
FLP不可能性定理与分布式共识理论
https://yicizhang00.github.io/posts/分布式/理论基础/FLP不可能性/
作者
Yici Zhang
发布于
2026年5月28日
许可协议