故事

一九四二年十一月，大西洋。

HX-229 护航船队离开加拿大哈利法克斯已经八天。队列里有三十七艘商船，装着运往英国的粮食、飞机零件、枪炮弹药和一千二百名士兵。保护这支船队的是皇家海军第七护航舰队——旗舰"诺森布里亚号"驱逐舰，带着四艘 Flower 级护卫舰：海鸥号、桂冠号、鸢尾号和奥德威奇号。

船队指挥官是爱德蒙·海尔中校，四十六岁，参加过第一次世界大战的北海巡逻。他在诺森布里亚号的舰桥上已经站了十九个小时。

此刻他们正在穿越"黑洞"——北大西洋中部那片任何盟军飞机都飞不到的海域，从纽芬兰到冰岛之间的一大块空白。U 艇在这片海域里以狼群战术猎杀。在空中掩护消失之后、下一个空中掩护出现之前的大约五十个小时里，护航舰队只能靠自己。

这是第四十七个小时。

晚间十点零四分，海尔收到一封加密电报，来自利物浦的西部逼近司令部。Ultra 情报显示：HX-229 前方约一百海里处，有一个代号"雷霆狼群"的 U 艇集群，由六到八艘 U 艇组成，正在扇形展开截击阵位。

海尔把电报反复读了三遍。他走到海图桌前。

如果按原航线继续——大约二十小时后进入狼群的截击扇面。彼时天还没亮，能见度会降到一海里以内。三十七艘商船撒在将近十海里的海面上，只有五艘护航舰。数字不对。

如果南偏四十度——增加大约四百海里航程，多烧一天半的油，还会让船队脱离下一个空中掩护的接应点。但是可以避开雷霆狼群的扇面。

"给我叫通讯官。"海尔说。

十点十七分，海尔用 TBS 短程无线电把情况告诉四位护卫舰的舰长。TBS 的功率只够周围几海里范围内通话，不会暴露给远处的 U 艇。他让每位舰长根据自己舰上的雷达和 HF/DF 侦测给出判断：他们各自的仪器有没有任何异常读数？值不值得冒险改航线？

"这是关于全队的决定。"海尔在无线电里说，"我要在十二点之前做出来。各位都回话。"

海鸥号的回话几乎立刻就到：改航线。他们的 HF/DF 在下午三次捕捉到 U 艇之间的短促通信，方向正好在前方扇面内。

桂冠号的回话在十点半到了：改航线。他们没有额外的直接证据，但同意海鸥号的判断。

鸢尾号的回话在十点四十三分到：他们的舰长希望看看天气——如果前方一百海里范围内有风暴，风暴本身会打乱狼群的队形，原航线也许可以保。他请求再等两小时，看最新的气象报告。

三封回话。奥德威奇号没有声音。

海尔在舰桥上来回踱步。他的副官科尔斯中尉站在海图桌边，眼睛没离开过无线电值班员。

"再呼一次。"海尔说。

值班员按下麦克风。"奥德威奇号，奥德威奇号，这里诺森布里亚。请回话。完毕。"

沉默。

"奥德威奇号，奥德威奇号，这里诺森布里亚。请回话。完毕。"

还是沉默。

十一点整。奥德威奇号在船队的左翼后方，离诺森布里亚号大约六海里。此刻海面上起了雾，能见度从下午的六海里降到了一海里多一点。诺森布里亚号的瞭望员从左舷看过去，看到的是一片灰白。雷达屏幕上有很多回波——商船们在自己的位置上，还有一些小的信号可能是浪花，也可能是别的什么。

"长官，雷达上奥德威奇号的位置……"值班员停顿了一下，"其实不太能分清。它本来应该在的那个位置有回波，但旁边七百码以内有两艘商船，影像重在一起。"

海尔沉默。

奥德威奇号没有回话，可能有四种情况。

第一种：它已经被击沉了。雷霆狼群的先头 U 艇比情报估计的前出得更远，从左翼外围潜伏上来，在 TBS 呼叫之前就一枚鱼雷打穿了它的弹药库。六海里外诺森布里亚号的瞭望员在雾里不会看到火光。爆炸的声音会被风和浪盖住。雷达上它的回波和旁边两艘商船混在一起，暂时看不出来差别。如果是这种情况，狼群已经比预计的更近，留给海尔的时间远远不到二十小时。

第二种：它的无线电坏了。TBS 是个脆弱的设备——一个真空管烧了，或者天线被浪打歪了，就会让整个通话系统哑掉。舰长手头没有备用方案。他可以用灯光信号，但雾里面看不见。如果是这种情况，奥德威奇号还在，航线上的数字照旧，狼群还是二十小时后的事。

第三种：它的舰长在犹豫。改航线意味着额外一天半的海上时间，烧油、人员疲劳、晚到利物浦一天半的战略物资。坚持原航线意味着 Ultra 情报判断的二十小时之后的一次遭遇。舰长可能正在权衡——也许他想多等一点雷达数据，就像鸢尾号那样，但还没想好怎么开口。

第四种：他回话了，但信号没到。TBS 在雾里衰减严重，浪涌会间歇性地把天线挡住。他可能在十点二十分就按了麦克风说"同意改航线"，只是那几秒钟正好赶上一个浪头，诺森布里亚号什么也没收到。他现在坐在他自己的舰桥上，等着海尔的下一步命令，想着自己已经尽了职责。

海尔没有办法分辨这四种情况。

科尔斯中尉轻声说："长官，我们可以派海鸥号过去看看。"

海尔摇头。"海鸥号离奥德威奇号有八海里，来回两小时。这两小时里船队要么散开要么停着等它。停着等就是给 U 艇递鱼雷。散开——"他没说完。

"要么假设奥德威奇号还在，继续。"科尔斯说。"要么假设它已经没了，把它从队形里去掉。"

"如果假设它还在但其实没了，我的左翼就是空的，我还以为自己有四艘护卫舰在保护三十七艘商船，实际上只有三艘。狼群从左翼切入，我反应不过来。"海尔说。

"如果假设它没了但其实还在，我就等于主动把左翼的一艘护卫舰从计算里删掉。它会继续在那个位置上走，但我不会把任何任务分给它，因为我以为它不存在。等于我自己让自己少一艘船。"

海尔望着雾。

他想起一位老海军——第一次世界大战时他在北海学到的一条规矩——任何时候如果你不知道一艘友舰的状态，你必须同时做两件矛盾的事。一件是按它还在的假设去调度，另一件是按它没了的假设去备案。两件事同时做，成本是巨大的，常常要用更多的燃料、更多的哨兵、更多的眼睛。但海尔回忆，那位老海军说——这是因为海上的真相要等到靠港之后才揭晓，而战斗不能等。

但是。他现在已经没有时间同时做两件事了。他必须在十二点之前给船队发出一个信号：要么继续，要么转向。整个队形都在等。

十一点二十二分。他转向值班员。

"再呼一次。这是最后一次。"

"奥德威奇号，奥德威奇号，这里诺森布里亚。请回话。这是最后一次呼叫。完毕。"

沉默。

十一点四十九分，鸢尾号的气象报告到了：前方一百海里内没有显著风暴系统，只有一片低压槽，对海况影响有限。鸢尾号的舰长更新了自己的判断——改航线。

十二点整。海尔在海图桌前站了几分钟，然后对科尔斯说：

"发信号：全队右转四十度，切入南偏航线。奥德威奇号仍在编队内，位置保留。任何舰艇接到奥德威奇号的信号，立即转发给我。"

科尔斯敬了个礼，转身去发命令。

海尔留在舰桥上。他知道他做了一个赌。如果奥德威奇号其实已经沉了，他的编队信号毫无意义——那个位置上没有人能收到。如果奥德威奇号在但无线电坏了，它会看到身边的船都在转向，它会跟着转。如果奥德威奇号的舰长在犹豫，这个命令会替他做决定。如果它的回话没到——那他的舰长此刻正在等一个永远不会来的确认。

海尔不知道哪种是真的。他永远不会仅凭这一夜的信息就知道。

天亮以前的四个小时里没有再出任何事。船队整齐地完成了转向。雾在凌晨三点散开，能见度回到了四海里，奥德威奇号赫然还在原来的位置上，跟着队形转了下来，在左翼的正确位置。

海尔在拂晓时通过灯光信号联系上奥德威奇号。对方回话：TBS 在十点零七分损坏，发射机电路被一个浪打进来的海水短路，舰员花了四小时修好。他们收到了转向命令——看到诺森布里亚号在雾散那一刻用灯光发出的队形更新信号，就跟着转了。

奥德威奇号舰长的灯光信号最后还问了一句："我的十点二十分的回话你们收到了吗？我当时用灯光发了'同意改航线'。"

诺森布里亚号没有人在十点二十分看到任何灯光信号。雾的关系。

海尔坐在舰桥后面的值班室里喝了第一口热茶。科尔斯在旁边。

"这次运气不错。"科尔斯说。

海尔看着茶杯。"这次，奥德威奇号没沉，它的回话我们没收到，它看到了我们的信号。这是四种情况里侥幸最好的一种。"

"下次。"他放下杯子。"下次可能是最坏的那一种。"

他望着天——东方开始发白，云层很厚。再过几个小时，皇家空军的解放者式巡逻机就会飞到他们头上。他们会进入有空中掩护的水域。这一关过去了。

但海尔知道他自己从那一夜的经验里带下来的，远不止是庆幸——有一种更沉的东西：在雾里和无线电静默里指挥一支船队，你永远不可能同时满足两个要求——保证所有船都听到命令，又保证命令及时发出。这两件事在海上从来不能同时做到。你只能选一个，然后为另一个的失败准备好代价。

那位第一次世界大战时的老海军曾经说过的话，海尔想，其实是一句没有解法的话。"你必须同时做两件矛盾的事"——他当年以为那是一句关于谨慎的教导，到了一九四二年这个晚上他才明白，那是一句关于绝望的承认。

概念解析

这则故事讲的是分布式系统理论里最著名、也最反直觉的一个结论——FLP 不可能性定理（FLP Impossibility Theorem），由 Michael Fischer、Nancy Lynch 和 Michael Paterson 于 1985 年发表在《Journal of the ACM》上，题为 Impossibility of Distributed Consensus with One Faulty Process。这篇八页的论文是分布式系统理论的基石之一，和前面第十三则《两位将军》中的两军问题并列，构成这个领域最根本的两条不可能性边界。

问题

在一个由多个节点组成的分布式系统里，各节点需要就某一件事达成一致——例如都同意某个值、都决定是否执行某个操作、都选出同一个领导者。这个问题叫做共识（Consensus）。形式化地说，一个正确的共识协议必须满足三个条件：

  1. 一致性（Agreement）：所有诚实节点最终决定的值必须相同。
  2. 有效性（Validity）：最终决定的值必须是某个节点最初提出过的。
  3. 终止性（Termination）：所有诚实节点最终都必须做出决定（不能永远悬着）。

这三条看起来都很合理。问题是——在异步网络里，如果哪怕只有一个节点可能崩溃，就不存在任何一个确定性协议能同时满足这三条。这就是 FLP 不可能性定理。

"异步网络" 和 "崩溃" 的具体含义

"异步"（asynchronous）有严格的技术含义：对消息传递延迟没有任何上界假设，对节点处理速度也没有任何上界假设。消息最终会送达，但可能花任意长的时间；节点不会永远停顿，但处理一条消息可能花任意长的时间。

"崩溃"（crash fault）指一个节点可能停止工作——不再发消息、不再响应。它不会发出错误的消息、不会恶意欺骗（那是拜占庭故障，由 [✓#3 守夜人誓约] 处理）——它只是突然停下，像被关了电源。

在这个模型里，关键的观察是：一个"已经崩溃的节点"和"一个正在极慢运行的节点"从外部看完全不可区分。前者永远不会再回应，后者迟早会回应——但你没有超时这个工具可以用，因为"任意长"的延迟是合法的。

这正是故事里海尔指挥官面对的困境。奥德威奇号的沉默可能意味着它已经沉没（崩溃），也可能意味着它的无线电坏了、信号被雾挡住、或者舰长还在犹豫——任何可能的故障在时间上的表现都和"还在工作但很慢"一模一样。海尔没有办法区分。他等得再久也没用——等得再久都还是有可能对方其实还在，只是更慢了。

定理的核心直觉：双价状态

FLP 的证明不长，但极其巧妙。核心概念叫做双价状态（bivalent state），定义如下：

  • 一个状态叫做 1-价（1-valent），如果从这个状态出发，无论后续消息以什么顺序送达，所有合法的执行序列都会决定值 1。
  • 类似地定义 0-价。
  • 一个状态叫做双价，如果从它出发既存在最终决定 0 的执行，也存在最终决定 1 的执行。

论文的论证分三步：

  1. 初始状态可能是双价的。如果每个节点初始提案值不同（一些提 0，一些提 1），那么取决于哪些节点先崩溃、哪些消息先到，系统最终可能决定任何一方。所以初始状态是双价的。

  2. 从任何双价状态出发，存在一种消息调度方式，使得下一步转移后依然是双价的。这是证明最精彩的部分——论文证明，总能找到一条"延迟关键消息"的路径，让系统保持悬在双价状态。

  3. 因此可以构造一个无限长的执行，使系统永远停留在双价状态，永远不做决定。这个执行违反了终止性——意味着这个协议不满足共识要求。

这个论证对任何确定性共识协议都成立。不管你设计多精妙，总存在一个消息调度让你的协议不能终止。

为什么这个结论令人震惊

在 FLP 发表之前，共识被广泛认为是分布式系统的核心问题——分布式数据库、分布式锁服务、副本选主——都依赖它。1985 年之前的工程师们假设，只要协议设计得足够好，就能在异步网络里达成共识。FLP 说：你们错了。工程上再精巧也够不到它，这道墙来自逻辑本身。

这个结论对实践产生了深远的影响——后续所有的共识算法（Paxos、Raft、Viewstamped Replication 等）都必须绕开 FLP，没有谁能直接解决它。具体的绕法有几种：

绕墙的办法

  1. 假设部分同步（Partial Synchrony, Dwork–Lynch–Stockmeyer 1988）：假设网络"最终"会变得同步——消息延迟最终会降到某个已知上界以下。Paxos 和 Raft 都在这个模型里证明的安全性。现实中这个假设通常成立——网络大多数时候是正常的，只在少数时候出现严重拥塞。

  2. 引入随机性（Ben-Or 1983、Rabin 1983）：协议决策里加入抛硬币的步骤，这样"对手"无法构造一个确定的坏消息调度来让协议陷入永久的悬置。代价是协议只能在概率意义上终止——可能在某次运行里花很长时间，但期望时间是有限的。

  3. 使用故障检测器（Failure Detectors, Chandra–Toueg 1996）：给系统配一个额外的模块，它可能误判但至少能给出"某节点似乎崩溃了"的猜测。有了这种不完美但存在的判断，FLP 的证明就不再适用。故事里海尔用到的那种"假定对方还在"的决定逻辑，本质上就是一个最原始的故障检测器——他猜奥德威奇号还在，尽管他并不确定。

  4. 放弃终止性：某些系统接受"在极端情况下协议可能永远不终止"这个代价，只保证安全性（不会出错）。这在关键场景下是可以接受的——宁可卡住也不要出错。

故事到概念的对应

  • 海尔指挥官面临的困境对应 FLP 的核心：有故障可能存在时，异步通信下无法保证共识的终止。
  • 奥德威奇号的沉默代表了 FLP 证明里那个无法区分的关键消息——你不知道它是"永远不会来的回话"还是"正在路上的回话"。
  • 故事里的雾、无线电静默、TBS 的功率限制，共同构成了一个"异步网络"的真实物理类比——这些约束全是战争条件下的真实代价，没有一条是刻意为难。
  • 海尔最终的决定——假定奥德威奇号还在、继续执行——对应实践中的"部分同步假设"或"故障检测器"。他在没有完美信息的情况下做了一个带赌博性质的选择。幸运的是，这一次他赌对了。
  • 老海军的那句话——"必须同时做两件矛盾的事"——对应 FLP 证明里那个不可能性的本质：任何协议都不能同时保证安全性、有效性和终止性。如果坚持同时满足三个，就必然有一种输入序列让你失败。
  • 结尾海尔意识到的"这是一句关于绝望的承认"，对应分布式系统工程师在理解 FLP 之后的那种心情——有些墙不是可以绕过的，只能学会在墙内生活。

FLP 和两军问题的关系

细心的读者可能会问：FLP 和第十三则的《两位将军》看起来讲的是同一件事——都是说共识不可能。它们的区别在哪里？

  1. 两军问题讲的是信道不可靠下的两人协同：消息可能丢失，双方无法达成共同知识（common knowledge）。这是一个关于信道的不可能性。
  2. FLP 讲的是节点可能崩溃下的异步系统的共识：消息最终会送达，但节点的状态不可判断。这是一个关于节点的不可能性。

两者都是不可能性，但针对的是分布式系统的不同方面。两军问题关注两方之间的通信，FLP 关注多方之间的决策过程。两者合起来，构成了分布式系统理论里两堵最根本的墙——一堵是"消息可能丢"，一堵是"节点可能挂"。后面所有的协议设计，都是在这两堵墙之间的空间里寻找可行的构造。

现实意义

FLP 的影响在现代分布式系统里无处不在——

  • Paxos（Lamport 1998）通过假设部分同步和多数派 quorum 绕开 FLP，是 Google Chubby、Apache ZooKeeper、etcd 等系统的核心。
  • Raft（Ongaro–Ousterhout 2014）在同样的模型下做了更清晰的协议，被 CockroachDB、Consul、TiKV 等系统采用。
  • HotStuff（Yin et al. 2019）在拜占庭环境下延续了同样的思路。
  • 区块链共识——无论是 PoW 还是 PoS——本质上都是用不同的方式给协议引入一个"同步假设"或"随机性"来绕开 FLP。

每一次你看到一个分布式系统"选举出一个领导者"、"提交一个事务"、"就某个值达成一致"，你看到的都是一个精心设计的协议在 FLP 的墙根底下找到的一条路。

哲学启示

FLP 最深的启示，和《两位将军》是一对——

绝对的协同，在分布式环境里是不可能的。

你不可能同时知道"远方的人还活着"和"远方的人在及时回应"。这不是信息量不够，是信息本身的限度。

这条原则超越了计算机科学。人类一切协作——家庭、合同、外交、国家——都受 FLP 和两军问题的共同阴影。我们之所以能在这两堵墙的阴影下生活，正是因为我们学会了"绕墙"的办法：超时、重试、假设、信任、惩罚、长期关系。这些"绕法"都不是完美的——每一种都有可能失败——但它们让协同从"不可能"变成了"大多数时候可以"。

海尔指挥官在那个冬夜里做的事，正是每一个分布式系统设计者每天在做的事——在没有完美信息的情况下做出决定，并为决定失败的那一种情况准备好代价。这是分布式系统工程师最深的一课，也是人类协作的最古老的一课。

就像那位第一次世界大战时的老海军说的那样——你必须同时做两件矛盾的事。你做不到，但你必须做。分布式系统，从 1985 年起，就一直在这句话的阴影下生活。