不可能性结果：FLP 与部分同步

标签

分布式/共识算法

字数

5056 字

阅读时间

20 分钟

共识问题（consensus）的设定是：$N$ 个进程各自持有一个初始值，要求

• 一致性（agreement）：任何两个非故障进程不会决定不同的值；
• 有效性（validity）：决定的值必须是某个进程的初始值；
• 终止性（termination）：每个非故障进程最终都会做出决定。

FLP 与 Dwork-Lynch-Stockmeyer 这两篇回答的是同一个问题的两面：在什么模型下这件事做不到，把模型放宽一档之后边界移到哪里。前者的结论（FLP 不可能性）常被当成「异步系统做不了共识」这一句话记住，但它的证明结构与它所禁止的东西都比这句话精确得多。

FLP：模型与结论

Fischer、Lynch、Paterson 在 1985 年的 Impossibility of Distributed Consensus with One Faulty Process 里给出的模型是：

• 完全异步：进程的执行速率无界，消息的传输延迟无界（消息最终会被投递、不会损坏）；
• 故障模型：进程可能崩溃（stopping failure），重启后不保证恢复状态。

两个关键定义：

术语	定义
可容许执行（admissible run）	至多一个进程故障，且所有发往非故障进程的消息最终都被收到
决定型执行（deciding run）	该执行中有某个进程达到了决定状态
部分正确（partially correct）	不违反一致性（agreement）与有效性（validity）—— 只要求安全性
完全正确（totally correct in spite of one fault）	部分正确 且 每个可容许执行都是决定型执行 —— 还要活性

定理 1：没有任何共识协议在存在一个故障进程的前提下是完全正确的。

这句话的读法是：你可以保住安全性，也可以保住活性，但不能在异步模型下同时保住两者。 下面把证明走一遍 —— 它的结构本身比结论更有价值。

证明分两大步：先证明存在一个"还没被决定"的初始配置，再构造一条永远不走进决定状态的执行。

双价与单价

先定义"还没被决定"这件事。

设 $C$ 是一个配置，$V$ 是从 $C$ 可达的所有配置的决策值集合：

• $|V|=2$：$C$ 是**双价（bivalent）**的 —— 从它出发既可能决定 0，也可能决定 1；
• $|V|=1$：$C$ 是**单价（univalent）**的，进一步按那个唯一的值称为 0-valent 或 1-valent。

由协议的部分正确性与"解总是存在"可知 $V\ne \mathrm{\varnothing }$。双价配置就是"决定权还悬着"的状态 —— 整个证明要做的就是找到它，并且一直待在它里面。

双价与单价的关系画成执行树：

引理 1：不相交的步可以交换

两个不同进程的步，先后施加的结果相同。这条性质在后面两个引理里都要用到，它的成立依赖进程之间只通过消息通信、且消息可能被任意延迟。

引理 2：一定存在双价的初始配置

引理 2：协议 $P$ 一定有一个双价的初始配置。

证明（反证）：假设 $P$ 没有双价初始配置。由部分正确性（有效性要求 0 与 1 都可能被决定），$P$ 必须同时存在 0-valent 与 1-valent 的初始配置。

称两个初始配置相邻（adjacent），如果它们只在某一个进程 $p$ 的初始值上不同。任意两个初始配置都可以由一条相邻链连起来（逐个把不同的位翻过来），因此必然存在一对相邻的初始配置 $C_0$、$C_1$，其中 $C_0$ 是 0-valent、$C_1$ 是 1-valent。设它们在第 $p$ 个进程的初始值上不同。

现在取一条从 $C_0$ 出发的、$p$ 一步都不执行的可容许决定型执行，记其调度（schedule）为 $\sigma$。这一步是引理的关键 —— 而它成立正因为故障模型允许一个进程不执行任何步（把 $p$ 视为那个故障进程，执行仍然是可容许的）。把这个 $\sigma$ 施加到 $C_1$ 上，两条执行的对应配置除了 $p$ 的内部状态之外完全相同，于是它们最终得到相同的决策值。

• 若这个值是 1，则 $C_0$ 可以决定 1，而它本身是 0-valent（可以决定 0）—— $C_0$ 是双价的；
• 否则 $C_1$ 是双价的。

两种情况都与"没有双价初始配置"矛盾。$◼$

引理 3：从双价出发总能保持双价

引理 3：设 $C$ 是 $P$ 的一个双价配置，$e=(p,m)$ 是可用于 $C$ 的一个事件。设 $\mathcal{C}$ 是从 $C$ 出发、不施加 $e$ 能到达的配置集合，$\mathcal{D}=e(\mathcal{C})$。则 $\mathcal{D}$ 中一定含有双价配置。

证明（反证）：由于 $e$ 可用于 $C$，且消息可以被任意延迟，$e$ 可用于 $\mathcal{C}$ 中的每一个配置。假设 $\mathcal{D}$ 中没有双价配置，即 $\mathcal{D}$ 里全是单价的。

因为 $C$ 双价，存在从 $C$ 可达的 $i$-valent 配置 $E_i$（$i=0,1$）。

• 若 $E_i\in \mathcal{C}$，令 $F_i=e(E_i)\in \mathcal{D}$；
• 否则 $e$ 在到达 $E_i$ 的过程中已经被施加过，于是存在 $F_i\in \mathcal{D}$，使 $E_i$ 从 $F_i$ 可达。

两种情况下 $F_i$ 都是 $i$-valent（它不是双价，而 $E_i$ 与 $F_i$ 中必有一个从另一个可达）。所以 $\mathcal{D}$ 里同时含 0-valent 与 1-valent 的配置。

称两个配置相邻（neighbors），如果其中一个由另一个经单步得到。由简单归纳，存在相邻的 $C_0,C_1\in \mathcal{C}$，使 $D_i=e(C_i)$ 是 $i$-valent。不失一般性，$C_1=e^{\prime }(C_0)$，其中 $e^{\prime }=(p^{\prime },m^{\prime })$。分两种情形：

情形一：$p^{\prime }\ne p$。 这两个步属于不同进程，由引理 1 可交换，于是 $D_1=e^{\prime }(D_0)$。但这是不可能的 —— $D_0$ 是 0-valent 的，0-valent 配置的任何后继都还是 0-valent，不可能变成 1-valent。

情形二：$p^{\prime }=p$。 取一条从 $C_0$ 出发的、$p$ 不执行任何步的有限决定型执行，调度为 $\sigma$，令 $A=\sigma (C_0)$。由引理 1，$\sigma$ 也可施加于 $D_i$，得到 $i$-valent 的 $E_i=\sigma (D_i)$；同样由引理 1，$e(A)=A_0$ 且 $e(e^{\prime }(A))=A_1$。于是 $A$ 同时可达 0-valent 与 1-valent 的配置，即 $A$ 是双价的。但 $A$ 来自一条决定型执行（$\sigma$ 是决定型执行的调度），所以 $A$ 必须是单价的 —— 矛盾。

两种情形都推出矛盾，故 $\mathcal{D}$ 中必有双价配置。$◼$

情形二里"取一条 $p$ 不执行任何步的决定型执行"这一步用到的正是引理 2 里同一个技巧：把 $p$ 当作唯一的故障进程。

引理 3 的两种情形各是一张交换图。

情形一：p′ ≠ p —— 两个步属于不同进程，由引理 1 可以交换

      C₀ ──e′──▶ C₁ = D₀
      │             │
    e │           e │
      ▼             ▼
      D₀ ──e′──▶ D₁

      D₀ 是 0-valent ⇒ 它的任何后继（含 D₁）都还是 0-valent；
      而 D₁ 是 1-valent。矛盾。


情形二：p′ = p —— 取一条 p 不执行任何步的有限决定型执行，调度为 σ

      C₀ ──e′──▶ C₁
      │             │
    σ │           σ │
      ▼             ▼
      A  ──e′──▶ A₁
      │
    e │
      ▼
      A₀

      A 同时可达 A₀（0-valent）与 A₁（1-valent）⇒ A 是双价；
      而 σ 来自一条决定型执行 ⇒ A 必须是单价。矛盾。

把引理拼起来

从引理 2 得到的结论里还能再挤出一条：从双价配置出发的任何决定型执行都会走向单价配置，因此必然存在某一步，它从双价走向单价。 这样的一步确定了最终的决策值。

要证明定理 1，只需说明总能让系统避开这样的步。

构造一条可容许但不做决定的执行：

• 维护一个进程队列（初始顺序任意）；
• 消息缓冲按消息发送时间排序，最早的在前；
• 每个**阶段（stage）**包含一步或多步进程步，阶段在满足下面条件时结束：**队首进程执行一步，且如果它在阶段开始时消息队列非空，则在这一步里接收它最早的那条消息。**该进程随后被移到队尾。

在这套规则下，任意无限长的阶段序列中每个进程都会执行无穷多步、并收到所有发给它的消息，所以构造出的执行是可容许的。

剩下的问题是怎么让它同时不做决定：

1. 取引理 2 保证存在的双价初始配置 $C_0$ 作为起点；
2. 保证每个阶段都从一个双价配置开始（归纳地做）。设当前配置 $C$ 是双价的、$p$ 在队首；
3. 令 $m$ 是 $C$ 的消息缓冲里发给 $p$ 的最早消息（没有则记 $0$），令 $e=(p,m)$；
4. 由引理 3，存在一个双价配置 $C^{\prime }$，它从 $C$ 经一条「以 $e$ 为最后一个事件」的调度可达 —— 这个调度就构成一个阶段。

每一步归纳都成立，于是无限长的调度可以一直构造下去。得到的执行可容许，且永远不会做出决定。因此 $P$ 不是完全正确的。 $◼$

FLP 到底禁止了什么

三条引理合起来说明的是：在异步模型下，决定权悬着的状态是不稳定的 —— 任何一个"最后一步"都能被推迟，使得系统继续保持悬置。禁止的是下面这个组合：

完全异步的通信 + 至少一个崩溃故障 + 保证终止。

把任意一项拿掉，共识就变得可能。这条判据解释了后面所有共识算法为什么长成那个样子：

拿掉哪一项	结果
不允许任何故障	有一个正面结果：只要多数进程非故障且执行期间不会有进程死亡（即死亡只发生在开始之前），共识可解
假设通信不会一直异步	部分同步模型 —— 见下一节，也是 Paxos / Raft 的立足点
放弃终止性（只保安全）	Paxos 的做法：任何时候都保持一致，只在网络"安静得够久"时才达成决定
放弃确定性（引入随机）	随机化共识算法，以概率 1 终止

FLP 的定理 2 值得单独记一下，因为它给出了 FLP 边界的一个具体位置：协议分两阶段 —— 第一阶段每个进程广播自己的编号，然后监听另外 $L-1$ 个进程的消息（$L=\lceil (N+1)/2\rceil$），据此构造一个有向图 $G$：$i\to j$ 当且仅当 $j$ 收到了 $i$ 的消息，所以 $G$ 的入度是 $L-1$；第二阶段各进程计算 $G$ 的传递闭包 $G^{+}$，从而知道所有与自己相关的边以及这些节点的初始值。

部分同步：把模型放宽一档

FLP 之后，Dwork、Lynch、Stockmeyer 在 1988 年问的是：模型放宽到什么程度，共识就变得可能？ 他们给了两种"部分同步"的定义，两者的区别在"上界知不知道"。

模型一：上界存在，但进程不知道

消息投递时间存在一个固定上界 $\mathrm{\Delta }$，但进程事先不知道 $\mathrm{\Delta }$ 是多少。

这个模型里 FLP 的不可能性结论不适用（通信实际上是同步的），但现成的共识协议用不上 —— 因为它们需要知道 $\mathrm{\Delta }$ 才能决定每一轮等多久。有一种"图省事"的做法被专门否掉：

随便挑一个 $\mathrm{\Delta }$ 内建进协议，然后规定"超过 $\mathrm{\Delta }$ 就认为发送方或接收方故障"。

这不可接受，理由是：$\mathrm{\Delta }$ 挑小了，可能过一会儿所有进程都被判成故障，而按定义故障进程的决定不需要与其他任何进程一致 —— 一致性就此失守。

需要的是一个不把 $\mathrm{\Delta }$ 内建的协议：在任何"存在某个固定上界"的系统里都正确。另外它明确不假设消息传输时间有概率分布 —— 也就是说，不允许靠实验去估 $\mathrm{\Delta }$。

模型二：上界已知，但只在 GST 之后成立

$\mathrm{\Delta }$ 已知，但消息系统有时不可靠（迟到或不投递）。若不加额外约束，这种"不可靠"消息系统至少和纯异步一样糟，FLP 的结果直接适用。 所以必须补一条约束：

全局稳定时间（GST, global stabilization time）：每次执行存在一个进程不知道的时刻 GST，从 GST 起消息系统遵守上界 $\mathrm{\Delta }$。

这条约束看起来过强（现实中上界不可能永远成立），但有一个化解：任何好的协议都会有一个量 $L$，表示 GST 之后还需要多久才能达成共识。 那么 $\mathrm{\Delta }$ 其实不必永远成立，只需保持到 GST + $L$ 为止。模型里因此不提 $L$，改为在给出每个算法时给出它自己的时间上界。

安全性 / 终止性的拆分，以及它与 GST 的等价

一个更好用的表述方式：把正确性拆成两块要求 ——

• 安全性：任何两个正确进程都不会分歧，任何正确进程都不会做出违反有效性条件的决定。无论消息系统多异步都必须满足；
• 终止性：每个正确进程最终都会做出决定。只要求在 $\mathrm{\Delta }$ 最终成立时满足。

这两个条件与 GST 条件等价。 论证很关键，值得记住：如果算法在「$\mathrm{\Delta }$ 从 GST 起成立」的前提下解决了共识，那么这个算法在完全异步下也不可能违反安全性 —— 因为安全性的违反必然发生在某个有限时刻，而那条违反执行的某个延续里 $\mathrm{\Delta }$ 终将成立，于是它也会在 GST 模型下违反安全性。

这条等价关系是 Paxos 与 Raft 那类协议的许可证：它们在任何时候都保证安全，只在网络好起来之后才保证终止。

部分同步下的容错能力

这些结果可以直接当判据用（$t$ 是允许的故障进程数，$N$ 是总数）：

故障模型	完全同步（$\mathrm{\Delta }$ 与时钟速率上界 $\mathrm{\Phi }$ 都已知）	部分同步
fail-stop / omission	$N\ge 2t+1$	$N\ge 2t+1$（可行当且仅当）
拜占庭（带认证）	$N$-resilient：可容忍任意数量故障	$N\ge 3t+1$（可行当且仅当）
拜占庭（不带认证）	$N\ge 3t+1$	$N\ge 3t+1$（可行当且仅当）

几点值得注意：

• 通信与处理器的同步上界 $(\mathrm{\Delta },\mathrm{\Phi })$ 的存在是"有任何容错能力"的必要条件 —— 这一点由 Dolev 等人（建立在 Fischer 等人之上）证明：只要消息投递时间上界或时钟速率上界之一不存在，就连最弱的容错都做不到。这是 FLP 之外的另一半不可能性。
• 带认证时"可容忍任意数量故障"与部分同步下"$N\ge 3t+1$"的差别在于认证能防伪造：签名让一个拜占庭进程无法冒充别人发送消息。
• 有下界证明：多数情形下其协议在容错数上是最优的，且下界是紧的。

另一个产物：容错的分布式时钟

为了让部分同步的处理器能达成"近似公共的时间概念"，有两个容错的分布式时钟（是 Lamport 那套逻辑时钟的容错变体）：

• 一个用 $2t+1$ 个处理器，容忍 $t$ 个 fail-stop、omission 或带认证的拜占庭故障；
• 一个用 $3t+1$ 个处理器，容忍 $t$ 个不带认证的拜占庭故障。

配套的决策规则也分两档：fail-stop / omission 情形下（Algorithm 1）收到任意一条 Decide v 消息即可决定；拜占庭情形下（Algorithm 2、3）必须收到来自 $t+1$ 个不同来源的 Decide v 消息才能决定 —— 后者正是"一个拜占庭节点不足以单独骗到决定"的界。

两篇合起来看

• FLP 划边界：完全异步 + 一个故障 + 保证终止，三者不可兼得；
• 部分同步说边界在哪：把"终止性"限定在 GST 之后（或等价地说，把安全性无条件要求、终止性有条件要求），共识就可行，容错数由故障模型决定。

后续的 Paxos 与 Raft 都落在这个区间里：它们没有绕开 FLP，而是把"终止性"降级成了有条件的。判断一个共识实现是否"真的做到了 FLP 说的不可能"，只需问一句：它在网络持续抖动时的行为是保持安全但不做决定，还是给出了互相矛盾的答案？ 前者是正确实现，后者才是违反 FLP 的尝试。

相关

• 一致性共识算法 —— 专栏导览，后续 Paxos / Raft / Zab / 拜占庭各篇排在本篇之后
• 01-CAP 定理 —— Gilbert-Lynch 在异步模型下证明 CAP 的不可满足性时，用的正是本篇的 FLP 结论作为前提
• 01-分布式事务 —— 2PC 的"安全但不活"就是本篇安全性与终止性拆分的一个具体例子

参考

• 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.
• C. Dwork, N. Lynch, L. Stockmeyer. Consensus in the Presence of Partial Synchrony. Journal of the ACM 35(2), 1988, pp. 288–323.
• D. Dolev, C. Dwork, L. Stockmeyer. On the Minimal Synchronism Needed for Distributed Consensus. Journal of the ACM 34(1), 1987, pp. 77–97.

贡献者

YJ

文件历史

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

e7758-累累累，我的token qaq

ae1ee-docs：内容完善

5f958-docs：不知道