FLP：完全异步下一次崩溃也能挡住确定性共识

破除误解：不可能，并不等于系统从不决定#

第一层误解把定理听成「共识从来不能工作」。论文禁止的是一种全称承诺：确定性协议在每一个合法调度上都既一致又终止。绝大多数调度里进程仍然可以决定；数据库与协调服务天天在决定。FLP 只断言，对手若被允许任意拖延消息、并在恰好一个进程上安排一次崩溃，就能让任何确定性协议永远停在尚未决定的状态。工程里看到的，往往是偶发的活锁或领导者迟迟选不出，而不是每天卡死。把「没有算法能担保所有执行都结束」读成「算法必然卡死」，把量词读反了。

第二层误解把 FLP 与拜占庭当成同一条不可能。拜占庭将军问题 的口头模型假定送达正确、发送者可知，并且缺席可被察觉：该到而未到的信，本身是一个可观察事件。那已经把同步送进装置。FLP 的故障是崩溃停机，不作恶、不伪造、不对两名听众说两套话。难处在于完全异步里，慢与死没有可检验的分界。把一次迟到读成叛徒，或把口头矛盾证词读成 FLP 的引理，都换了模型。两条不可能性切的前提不同，不能互相当证明步骤。

第三层误解以为「代码里加超时」就能取消定理。超时是程序里的一行；定理问的是模型里有没有延迟上界。完全异步允许任意有限延迟，时钟读数不提供关于对方已死的证据。超时到期时，你仍然不知道对面是崩了还是信还在路上。若超时后强行决定，可能与一个其实活着、只是被拖住的进程冲突；若超时后继续等，对手可以把下一封信再拖过下一次超时。没有上界的超时仍是异步。部分同步后来补的，是终将生效的上界，不是多写几次 sleep。

第四层误解以为加机器、加带宽、换更快的网卡就能绕开。论文对进程数几乎不敏感：在至少两个进程、只允许一个崩溃的设定下，结论已经成立。带宽改变的是经验延迟的分布，不改变「延迟可以任意长」这一许可。对手要的不是塞满信道，而是挑选一个永远让配置停在二值待定的公平调度。启发式可以让坏调度更罕见；罕见不是不存在。能改边界的，只能是改模型：给时间、给随机、或给某种关于谁已停机的额外信息。

模型：完全异步、一次崩溃、确定性#

系统是有限多个进程加一个消息缓冲。进程是确定性自动机：当前状态与收到的消息唯一决定下一状态以及要发出的消息。允许一个进程崩溃停机，崩溃后不再发送。其余进程是正确的，必须继续工作。消息传递没有同步时钟，也没有全局「现在」。缓冲里的消息可被任意拖延，但对正确进程之间的信道，论文要求发出的消息终将被投递——只是没有上界。丢失若被写成永久删除，那是另一类故障；FLP 的对手用延迟，不用把邮路剪断。

进程可以在没有真实来信时仍被允许走一步，论文用空消息表示这种内部动作，以免「没人写信就全体冻结」变成作弊。一次事件是某个进程接收某一条消息（或空消息）并更新状态。配置是全体进程的局部状态加上缓冲里尚未投递的邮件。调度是事件序列。合法执行至多崩溃一个进程，并且发往正确进程的消息终将被投递。公平不是「人人同时迈步」，而是正确进程无限次获得事件、邮件不会被永远扣押。

共识在论文里被写成二值。每个进程有初值 0 或 1，决定一旦写出就不可撤回。一致性要求任意两个作出决定的进程不得写出不同的值。有效性要求：若全体初值都是 \(v\)，则决定必须是 \(v\)，协议不能凭空发明第三种答案。终止性要求每个正确进程在合法执行里最终决定。安全是前两句，活性是第三句。FLP 说的是：不存在确定性协议，使这三句在所有合法执行上同时成立。

把终止从全称改成「多数调度上成立」，模型就已经不是这篇论文的对象。把故障从崩溃改成撒谎，对象变成 拜占庭将军问题。把确定性改成抛硬币，对象变成随机化共识。本页不提供如何布置超时、如何选举领导者、如何拆分集群的步骤；那些步骤一旦写进正文，就把不可能性证明误认成运维手册。

证明的脊柱：二值待定与公平调度#

证明不依赖某个具体协议的报文格式。它问：任意确定性协议的状态图里，对手是否总能找到一条合法路径，让决定永远不发生。为此先给配置贴标签。从配置 \(C\) 出发，若所有会作出决定的延伸都决定 0，称 \(C\) 为 0-价；对称地定义 1-价。两者合称单价。若既存在决定 0 的延伸，也存在决定 1 的延伸，称 \(C\) 为二值待定（bivalent）。某个进程一旦写下决定 \(v\)，一致性会强迫所有后续决定同为 \(v\)，配置从此单价。二值待定因此精确等于「还没有人被允许把答案写死」。

第一步证明存在二值待定的初始配置。有效性迫使「全体初值为 0」的配置只能是 0-价，「全体初值为 1」只能是 1-价。在这两极之间，可以逐个翻转单个进程的初值，排出一条相邻链。若链上每个初始配置都单价，则必有一对邻居价相反，而它们只在进程 \(p\) 的初值上不同。令 \(p\) 从一开始就崩溃、不再发言。剩下的正确进程在两个邻居里看见的消息历史可以完全相同，因而必须决定同一个值。那个值却被要求同时充当 0-价与 1-价的证据。矛盾。所以链上至少有一个初始配置是二值待定的：世界还没开始跑，两种未来已经都合法。

第二步证明二值待定可以一步一步延续。设当前配置 \(C\) 二值待定，事件 \(e\) 适用于 \(C\)，例如把某封信交给进程 \(q\)。若 \(e(C)\) 仍二值待定，对手就走这一步。若 \(e(C)\) 变成单价，则因为 \(C\) 本身二值待定，必另有一条有限延伸走向相反的价。关键几何是不同进程上的事件可以交换次序：先给甲再给乙，与先给乙再给甲，得到同一配置。若两个相反价的邻居只差「某封信是否已经交给 \(q\)」，对手可以让 \(q\) 看起来像崩溃，迫使其余进程在看不见那封信的情况下决定；他们的决定无法同时尊重两条价。若相反价来自两个不同进程上的事件，交换次序会把 0-价与 1-价叠成同一个后继，同样不可能。因此总存在一种走法，让指定的待投递事件最终被算进去，而落地配置仍二值待定。这里没有需要背诵的引理编号，只有一件事：确定性协议无法自己选出那步「锁死答案」的棋，因为对手还能改投递顺序。

第三步把局部延续接成无限合法执行。对手从那个二值待定的初始配置出发，每次都选让后继仍二值待定的事件，同时照顾公平：每个正确进程无限次得到事件，缓冲里发给他们的信终被投递，只是时刻由对手挑选。得到的调度不是把网络永久关机——关机不是合法执行——而是一封信总是「再晚一点点」。因为任何已经决定的配置都是单价的，这条无限路径上没有人写下决定。终止性失败，一致性与有效性从未被违反：它们只约束已经写出的值，而这里什么也没写出。这就是活性被单独剪断的方式。

精确含义现在可以收紧。论文没有证明「存在一个协议，它在某些调度上会卡住」——那几乎是平凡的。它证明「对每一个确定性协议，都存在合法调度使正确进程永不决定」。对偶地，它也不证明拜占庭口头模型里的人数下界，也不证明 兼职议会与 Paxos 的相交多数会选出两个值。Paxos 把安全写成始终成立的不变量；它从不在完全异步里承诺终止。把 FLP 读成 Paxos 的实现缺陷，等于把活性边界误认成安全漏洞。

它证明了什么，后来的逃逸改了什么#

它证明了：完全异步、确定性、消息传递、一次崩溃停机，这四条叠在一起时，共识的安全与终止不能在所有合法执行上同时被担保。它把「慢」从工程烦恼改写成模型里的许可，并把许可用到极限。它没有给出任何可运行协议，没有比较哪种超时毫秒更好，也没有讨论开放成员网络里一票如何定义。对象停在这条全称不可能。2001 年 Dijkstra 奖授予这篇论文，不是因为它让共识从世界上消失，而是因为它迫使后续工作必须写明自己放松了哪一条。

后来的逃逸都改模型，不改证明。部分同步把「延迟可以永远任意长」改成「存在某个未知时刻之后，延迟被未知上界管住」。1988 年，德沃克、林奇与斯托克迈尔在 Journal of the ACM 证明，这种最终同步下共识可以终止。超时与视图更换之所以重新合法，是因为模型终于允许「等足够久就该当对面已死」成为一种终将正确的推断。细节与德沃克把定义写成合同的习惯，见 辛西娅·德沃克；本页只借用 1988 年那条共识结果，不把人物传记搬过来。部分同步不是「实践中网络还不错」的观感，它是一句可检验的假设。假设不成立时，FLP 的对手调度可以再次出现。

随机化改的是确定性。1983 年，本-奥尔给出完全异步下的随机共识：进程用抛硬币打破对称，终止变成概率 1 的事件，而不是每一条调度上的必然。FLP 的对手靠事先看穿下一步局部状态来挑选延迟；硬币尚未落下时，那种看穿不再免费。这与 随机化算法 用随机性绕开确定性下界是同一类交换：你交出最坏情况的全称保证，换回几乎必然的进展。交换是显式的。把「我们加了抖动」说成推翻了 FLP，等于既要随机化的好处，又要确定性的措辞。

故障检测器改的是进程能获得的信息。1996 年，钱德拉（Tushar Chandra）与图埃格（Sam Toueg）把「谁可能已经停机」抽象成可查询的预言，并刻画解决共识所需的最弱一类不可靠检测器。检测器可以误怀疑活着的进程，也可以暂时漏掉真的崩溃；关键是怀疑终将稳定到足以选出进展所需的那一点信息。完全异步模型禁止的，正是这一点信息。检测器不是教人如何写心跳报文的配方，它是把 FLP 改写成一句关于知识的话：若你不能最终知道谁还在说话，你就不能既安全又终止。

这三扇门互不吞并。部分同步给时间，随机化给硬币，故障检测器给关于停机的信念。兼职议会与 Paxos 走的是安全始终成立、活性依赖额外假设的那条路，与部分同步、领导者最终独占一轮是亲戚，不是对 FLP 的反例。拜占庭口头模型从一开始就有可察缺席，走的是另一条轴。把三扇门画成一张「如何让集群永远可写」的操作清单，会离开对象。概念证据到此为止。

跨域连接#

• 时间哲学：完全异步拒绝一个全局共享的「此刻」。事件的先后由消息因果给出，不由墙上时钟给出。缺席在这个模型里不是可观察的现在，而是一种可能仍在未来才到达的延迟。拜占庭口头模型把「该到而未到」写成已经发生的事件，等于把一种可检测的现在偷运进装置。FLP 证明，拿掉这层可检测的现在之后，连一次安静的停机都能挡住确定性终止。日常时间观假定人人共用薄薄一层现在；分布式里没有那一层，只有已被投递的信与尚未投递的信。把超时读成校准误差范围内的同时性，会把模型改回同步，定理不再适用。
• 认识论：正确进程必须在没有上帝视角时决定。证据是自己收到的消息，不是关于「谁已死亡」的现成知识。延迟与崩溃产生形状相同的证据：长时间沉默。在这种证据下仍要求必然终止，等于要求从欠定的现象推出一个不可撤回的判断。论文的结论是：确定性程序做不到这一点而不破坏一致性。这不是怀疑主义练习，而是把「真」与「知」拆开——某个进程也许已经停机（真），但其余进程没有可公开核验的记号来知道这件事（知）。工程事故常发生在把本地超时当成已经共享的公共知识。
• 知识：单价配置是系统已经把答案写成公共事实的状态；二值待定是两种知识状态仍都可及。决定是一次不可撤回的知识承诺：写下 \(v\) 之后，协议禁止任何人再声称自己知道 \(\neg v\)。FLP 说，在完全异步里，你无法设计一种确定性规则，让所有正确进程都终将作出这一承诺。学习者尚未收到足够邮件时，正确动作是不宣称已知，而不是猜一个值。把「集群里有人已经提交」与「我已经知道有人提交」混成同一个时刻，会把活性失败误诊成数据分叉。活性失败是知识迟迟不能闭合；分叉才是安全被打破。
• 概率：本-奥尔把终止从全称调度改写为几乎必然事件，用的正是随机性对对称的打破。硬币不是把不可能定理「证伪」，而是退出定理的前提。对手若必须在硬币落下之前选定延迟，他就不再拥有对确定性后继的完全控制。这与「超时抖动让系统看起来更快」不是同一句话：没有概率空间上的终止陈述，抖动只是另一种确定性启发式。部分同步不需要硬币，它需要时间上界终将出现；随机化不需要上界，它需要真正的随机源。两条逃逸走的是不同的测度。
• 集合论：配置、事件与价是外延对象。价是从某点出发的可达决定值集合：单元素即单价，两元素即二值待定。证明的交换步骤依赖不同进程上的事件作为可交换的函数，作用在同一配置上得到同一后继。对手调度是一条无限路径，路径上每个有限前缀的价集合都仍是 \(\{0,1\}\)。把这些集合画成机柜拓扑或可用区名单，会把外延对象误认成布线图。拓扑可以改变哪些消息暂时到得了；到得了与否改变经验频率，不改变「存在一条公平路径永远待定」这句存在量化。

参考文献#

• Michael J. Fischer, Nancy A. Lynch & Michael S. Paterson, "Impossibility of Distributed Consensus with One Faulty Process", Journal of the ACM 32(2), 1985, pp. 374–382. DOI: 10.1145/3149.214121. —— 本文对象：完全异步下一次崩溃对确定性共识的不可能性。
• Cynthia Dwork, Nancy A. Lynch & Larry Stockmeyer, "Consensus in the Presence of Partial Synchrony", Journal of the ACM 35(2), 1988, pp. 288–323. DOI: 10.1145/42282.42283. —— 部分同步下共识可终止，用以标明 FLP 放松哪一条假设之后可以逃逸。
• Michael Ben-Or, "Another Advantage of Free Choice: Completely Asynchronous Agreement Protocols", PODC, 1983, pp. 27–30. DOI: 10.1145/800221.806707. —— 随机化共识，用以标明确定性这一前提被拿掉之后发生什么。
• Tushar Deepak Chandra & Sam Toueg, "Unreliable Failure Detectors for Reliable Distributed Systems", Journal of the ACM 43(2), 1996, pp. 225–267. DOI: 10.1145/226643.226647. —— 不可靠故障检测器，用以把活性所需的额外信息写成抽象预言。

延伸阅读#

• 与 分布式计算理论 对读：总览里的 FLP 段落是路标，本页才是定理对象，不要把总览再织长。
• 与 兼职议会与 Paxos 对读：安全不变量可以在完全异步里成立，终止需要另写假设。
• 与 拜占庭将军问题 对读：先分清可察缺席与不可分的延迟，再看 \(3m+1\) 与「一次崩溃」各从哪一条前提长出来。
• 与 辛西娅·德沃克 对读：1988 年部分同步是逃逸之一，人物页里的差分隐私是另一条立法，不要收成同一个故事。