摘要

  • Fischer、Lynch 与 Paterson 证明：在其完全异步的消息传递模型中，任何确定且部分正确的共识协议，只要允许一个进程崩溃，就存在一条始终不能决定的可容许执行。
  • 证明通过推迟关键事件来保持全局配置的二价性；不同进程上的独立事件可以交换次序，因此调度器能够在公平安排进程与消息的同时，让决定一直留在未来。
  • 部分同步、故障检测器和随机化改变了前提。超时可以是有效的工程控制，但它不能证明进程已经故障，更不能把普通网络事故自动变成“FLP 事件”。

一个协调者沉默了。对运维人员来说，最自然的动作是启动计时器，然后把超时当成故障。但在没有时延上界的世界里，沉默只证明此刻还没有收到消息：发送方可能崩溃，也可能运行得很慢，消息还可能正在一条终会交付的路径上。

1985 年，Michael J. Fischer、Nancy A. Lynch 与 Michael S. Paterson 在《一个故障进程下分布式共识的不可能性》中，把这种认识写成了严格的边界。后来人们常用“FLP 证明共识不可能”概括它，却抹掉了定理最重要的限定词。它否定的不是现实世界里每一次决定，而是在特定模型中对每一条合法执行都承诺终止的可能性。

消息可靠，时间却没有承诺

FLP 模型中的进程是确定性的；同一状态接收同一消息，下一步也相同。进程之间通过消息通信。系统没有同步时钟，没有进程速度上界，也没有消息传输时延上界，因此算法不能凭等待时间区分“已崩溃”和“只是慢”。

这并不是一个随意丢包的网络。论文要求消息正确且只交付一次；只要非故障进程不断尝试接收，发给它的消息最终必须到达。交付可以任意晚，也可以乱序。所谓可容许执行，至多包含一个故障进程，并最终向所有非故障进程交付其消息。非故障进程本身要无限次取得步骤。

这一点击中了常见误读：证明不是靠永久吞掉一封关键消息取胜。作者构造的无限执行可以公平轮转进程，也可以逐一交付队列里的消息，却始终不让系统跨过决定边界。

二价性不是犹豫，而是未来仍有两种结果

论文用“配置”描述一个时刻：每个进程的内部状态，加上尚未交付的消息。若从某个配置继续运行，只可能决定 0，它就是 0 价；只可能决定 1，就是 1 价；若两种决定都仍可到达，则为二价。

二价性不是某台机器里的一个“未决定”变量，而是整个状态空间的性质。它表示现实尚未被已有事件压缩成唯一结局。一旦配置成为单价，协议的安全性就不允许它在另一条合法后继中改判。

证明首先说明，某个初始配置必须是二价的。否则，把各进程输入逐个从一种初值改成另一种初值，总能找到两个只相差一个进程输入、却分别只能决定 0 和 1 的相邻配置。如果那个进程一开始就崩溃，其余进程无法分辨自己身处哪个配置，却被要求给出相反结果，矛盾由此产生。

随后出现真正精妙的关键事件论证。取一个当前可执行的事件，例如某进程接收一封待处理消息。假设无论怎样推迟它，只要最终执行，就一定让配置变成单价，那么沿着推迟路径必然存在一个临界点：一次事件把结果从尚未确定推向唯一值。

可是不同进程上的独立步骤可以交换。先执行事件 A 再执行事件 B，与先 B 后 A 会到达相同配置。这个“交换方格”迫使本应拥有不同价性的两条路径汇合，从而与假设冲突。于是，总能先安排一段有限执行，再在仍为二价的节点执行那个被推迟的事件。

调度器重复这一操作：公平选择下一进程或下一封消息，让它最终得到服务，同时把系统留在二价区域。极限是一条合法、可靠、公平而永不决定的执行。

存在一条坏路径，不等于所有路径都坏

FLP 的量词决定了它的含义。定理说“存在”一条不决定的可容许执行，而不是“每一条”执行都不决定。现实协议可以在绝大多数运行中迅速完成，也可以在运行环境比模型更友好时稳定工作。失去的是无条件保证，不是成功运行的能力。

同理，一次选主停顿也不是 FLP 的现场照片。丢包、磁盘拥塞、配置错误、相关故障、成员变更漏洞和不安全重试都可能造成停顿。只有先说明实际系统使用了什么时序假设、哪些步骤因安全性被禁止、以及延迟与崩溃为何不可区分，FLP 才是分析边界，而不是事故报告里的装饰性名词。

绕开边界，就是公开增加假设

Dwork、Lynch 与 Stockmeyer 后来形式化了部分同步：可能存在未知的时延界限，或者已知界限要到某个未知的全局稳定时刻后才成立。协议可以等待环境进入这个较强阶段，再获得进展。

Chandra 与 Toueg 的故障检测器以完备性和准确性描述一个额外信息源。它不是从沉默中推出确定事实，而是把“最终会提供何种可依赖怀疑”写进新契约。

随机化协议则修改“确定性”前提。Ben-Or 等工作让进程使用概率选择，令对手无法永远沿同一确定状态结构操纵执行；相应地，终止承诺也成为概率性的。

这些方法没有反驳 FLP。它们证明了 FLP 最有生产力的贡献：一旦边界清楚，工程师就能准确说出自己新增了哪种能力，以及保证依赖什么。

应当怎样记住 Nancy Lynch

Lynch 的回忆保留了共同作者关系：她与 Fischer 在 1982 年开始追索这个问题，Paterson 随后加入并促成最终论证。成果的力量不在一句悲观口号，而在于用很少的形式工具，把全球性的终止问题压缩到关键事件的次序，以及一个进程缺席时其余系统能否分辨两种历史。

因此，成熟的共识设计不应该承诺“永不停止”，而应披露：容忍什么故障，时钟和故障检测器提供什么性质，何时安全性优先于可用性，以及活性预期在哪些条件下成立。FLP 不是工程的终点，而是保证开始诚实的地方。

来源