IT 论文精读 · PAPER 73
Fischer, Lynch & Paterson · PODS 1983 / JACM 1985
1985 年，三位理论学者 Fischer、Lynch、Paterson 证明了一件让整个分布式领域安静了一下的事：在互联网这样的网络里，只要有一台机器可能宕机，就不存在任何一套规则，能保证所有机器最后一定都选出同一个答案。要害在「保证」二字。今天的 Paxos、Raft 和区块链共识，都是在绕开这个结论活着。
想象五台机器要就一件事表态，比如「这笔转账算成功还是失败」。它们只能互发消息商量，规矩三条：① 最后大家必须选同一个答案；② 两种答案都得有可能被选出来（否则把「永远选失败」写死也算达成一致，那是耍赖）；③ 没坏的机器最后都得真的选出来，不能永远举棋不定。只要消息可能慢得没有上限，而且哪怕只有一台机器可能中途宕机，这三条就凑不齐。
要害只有一句：在没有时间上限的网络里，一台不吭声的机器，和一台已经发了话、消息还在路上的机器，看起来一模一样。
现实里我们靠超时判断——等十秒没回就当它死了，可这背后有个前提：「正常不会超过十秒」。这里恰恰没有这个前提。于是只剩两条路：一直等（可能永远等下去，违反 ③）；或者当它死了往下走——万一它只是慢，醒来时手里已有另一个答案，① 就破了。
这不是「还没人想出来」，而是证明了谁都想不出来。思路很漂亮：先给系统的每个瞬间状态贴标签。有的大局已定——不管后面怎么走，结果必然是「成功」，或必然是「失败」；还有一种两边都有可能，姑且叫「悬着」。
论文接着证两件事：开局就必然存在一个「悬着」的状态；而且只要系统还悬着，总能挑一条消息把送达往后挪一挪，让它走完这一步之后仍然悬着。把这招无限用下去，系统就永远在「悬着」里打转。
这个刁难一点不赖皮：它不扣押任何消息，也不弄坏任何一台机器，只是排了个特别别扭的送信顺序。算法之所以露出这个洞，仅仅因为它必须事先准备好容忍一台机器宕机——这份准备本身就是那条缝。
三条凑不齐，就得主动放掉一条，放哪条很有讲究。Paxos、Raft 这类真在用的算法死守前两条：绝不给出两个互相矛盾的答案；让掉的是 ③ 里的「保证」——不承诺多久之内一定出结果。网络正常时几乎总能飞快定下来，一团糟时宁可卡住也不出错。另一条路是掷骰子：拿不定主意时随机选，「永远卡住」的概率就趋近于零。
也说句诚实的：这个结论说的是最坏情况下可能永远拖着，不是「实践中办不到」——真实网络不会永远配合那种刁钻的顺序，这正是 Paxos 们照样好用的原因。
在消息可能任意慢的网络里，「宕机」和「很慢」长得一模一样；于是只要允许一台机器出事，就没有算法能同时保证「不出两个答案」和「一定出得了答案」。能用的共识算法都在这两者间做了取舍——保住不出错，让掉「一定多快出结果」。
想看双价配置、菱形交换引理与四条绕行路线？ → 切到精读版
FLP 给共识（consensus）划了一条天花板：在异步消息传递系统里，只要允许一个进程崩溃，就不存在任何确定性算法能同时保证「所有人决定同一个值」「两个值都可能被决定」和「最终真的决定出来」。换句话说，异步世界里安全性可以保住、活性无法被保证——这句话此后成了每个共识系统的设计起点。
作者是 Michael J. Fischer、Nancy Lynch、Michael S. Paterson，会议版 1983 年发于 PODS，定稿 1985 年刊于 JACM。它上承 Lamport 等人 1982 年的拜占庭将军问题——那篇在同步回合模型里解决了容错一致，于是「异步能不能行」成了自然的下一问。下启的更多：Ben-Or 的随机化共识（1983）、Dwork-Lynch-Stockmeyer 的部分同步模型（1988）、Chandra-Toueg 的失效检测器（1996），以及 Paxos 与 Raft 的整个设计取向。2001 年获 Dijkstra 分布式计算奖。
1980 年代初，分布式事务、可靠广播、副本一致已有一大堆协议在跑，但它们的正确性论证里普遍藏着一个心照不宣的前提：超时是可信的——等够久还没回话就当对方死了。工程上实用，理论上却站不住，因为没人能给出「绝对不会被超过」的延迟上界。抽掉它，两阶段提交（协调者先问「都准备好了吗」、再宣布提交或回滚）的老毛病就露出来：协调者在关键时刻失联，其余节点不敢提交也不敢回滚，只能无限阻塞。
于是真问题变成：完全不做时间假设，容错的一致性还能不能做出来？FLP 把它写成一个极干净的设定：N 个确定性进程只靠消息通信，消息可任意延迟、任意乱序，但不丢不伪造、最终必达；最多一个进程崩溃，崩溃即永久停止。要求三条——一致性（不存在两个不同的决定值）、非平凡性（0 和 1 都有可能被决定）、终止性（每个不崩溃的进程最终都决定）。中间那条比通常的「有效性」更弱，而要求越弱、不可能性越强。
证明的第一个关键动作，是把执行过程看成在配置（configuration）之间的移动：一个配置 = 所有进程的内部状态 + 消息缓冲里还没送达的消息；一次事件就是「某进程收下某条消息、改状态、再发出若干新消息」。
然后给配置贴标签，叫价（valence）：从这个配置出发，后续所有可能的执行中还能出现哪些决定值。只能出现 0 的叫 0-价、只能出现 1 的叫 1-价，统称单价（大局已定）；两个都还可能的叫双价（bivalent），即「还悬着」。
用这套语言，「算法能终止」就等价于系统不可能永远停在双价里；要推翻它，只需造出一条永远双价的无限执行。
把所有可能的初始配置排成一排：最左是「所有人初始值都是 0」，最右是「都是 1」，相邻两个只差一个进程的初始值。若没有一个初始配置是双价的，那这排里必然存在相邻的一对：左边 0-价、右边 1-价，而它们只在进程 p 的初始值上不同。
现在用上「允许一个进程崩溃」：让 p 从一开始就崩溃。剩下的进程必须自己决定出来，而它们手里的信息在这两个配置里完全相同——p 一个字也没发过。于是同一段执行必然给出同一个决定值，可左边注定 0、右边注定 1。矛盾。双价初始配置一定存在。
剩下要证：从任一双价配置出发，对任何一条待送达的消息 e，总能先走一段路再送 e，落地时系统仍然双价。这保证对手能一直把系统留在悬而未决里，同时不永久扣押任何消息。
反证：假设无论先怎么走，送 e 之后都必变单价。沿这条假设摸下去，一定能找到两个只差一步的配置——在 C 上送 e 注定 0，先走一步 e′ 再送 e 则注定 1。只有两种情况：
两种情况都不成立，所以那个「送 e 之后仍然双价」的走法一定存在。
对手的策略于是成形：从双价初始配置出发，每轮盯住消息缓冲里等得最久的那条，按第三步找出一段「送完它仍然双价」的走法走过去，再盯下一条最老的，如此反复。这样构造出的无限执行完全合法——每条消息最终都被送达、每个进程都无限次执行了步骤，可系统始终双价，从头到尾没有任何进程做出决定。
还有一处常被忽略的锋利：这条运行里其实没有任何进程真的崩溃。算法露出破绽，仅仅因为它必须事先为一次可能的崩溃留好退路，而这份准备逼它在某些局面里不敢再等。
这是一篇没有实验的论文，它的「结果」就是定理本身，以及边界被划得有多紧：
它把共识从「怎么做」变成了「让掉什么」：此后任何共识系统都得回答——你的活性挂在什么假设上？由此长出四条绕行路线，至今仍是共识设计的全部地图：
还有一条至今好用的硬经验：任何号称「在任意网络条件下都保证快速达成一致」的系统，要么偷偷藏了时间假设，要么就是错的。
① 一句话：异步网络中只要允许一个进程崩溃，就没有确定性算法能同时保证一致、非平凡与终止。
② 痛点：协议普遍默认「超时可信」，真实网络却给不出延迟上界；2PC 在协调者失联时无限阻塞即是症状。
③ 核心直觉：崩溃与极慢在旁人眼中完全相同——一直等可能不终止，不等则可能出两个答案。
④ 机制一：给配置贴「价」——单价（大局已定）与双价（还悬着）；终止等价于「不可能永远双价」。
⑤ 机制二：双价的初始配置必然存在——相邻初始配置只差一个进程的值，把它杀掉即得矛盾。
⑥ 机制三：双价可无限维持——不同进程上的两事件可换序走到同一配置（菱形交换），同一进程上的则按住它、让其余人先决定；两路都出矛盾。
⑦ 拼出的无限运行完全合法：消息都送达、进程都在动，却永不决定；其中没有进程真的崩溃——洞来自算法必须为崩溃留退路。
⑧ 边界极紧：最温和的崩溃、消息保证送达、只要求「两值都有可能」，甚至只要一个进程决定也不行；反之故障进程若一开始就死、活者过半则可解。
⑨ 影响与局限：共识设计从此以「安全无条件、活性靠假设」为纲，四条绕路是部分同步（Paxos / Raft）、随机化、失效检测器、弱化问题；但模型极端、只管确定性算法，也常被误引为「异步不能达成共识」或与 CAP 混为一谈。