Ben-Or 1983：抛硬币怎样把异步共识的终止改成几乎必然

破除误解：几乎必然，并不是每一条调度都结束#

第一层误解把这篇短文听成「FLP 被推翻了」。费希尔、林奇与帕特森证明的是：完全异步、一次崩溃、确定性协议，三者叠在一起时，不存在能在所有合法执行上同时保住一致、有效与终止的算法。本-奥尔的进程在对称僵局里抛硬币，下一步局部状态不再由当前配置唯一决定。对手若想像 FLP 那样预先看穿后继、再挑选永远二值待定的投递顺序，必须在硬币落下之前就选定延迟；硬币尚未落下时，那种看穿不再免费。同一年的 PODC 上，不可能性与随机化协议并排出现——会议版 FLP 与本-奥尔都在 1983 年蒙特利尔的那本论文集里。期刊版 FLP 迟到 1985 年的 Journal of the ACM，并不改变概念关系：随机化退出的是确定性前提，不是给定理找了一个反模型里的反例。把「我们加了随机」说成证伪 FLP，等于既要硬币的好处，又要确定性的全称措辞。

第二层误解把「以概率 1 终止」读成「每一个无穷执行都会决定」。概率 1 是测度语句。把全体正确进程在各轮抛出的硬币看成一个无穷乘积空间，那些永远达不成多数、因而永远不决定的执行可以写出来——例如每一轮硬币都精确地拆成两半——但它们在这个空间里的测度为零。几乎必然不等于必然。FLP 给出的是存在量词：对每个确定性协议，都存在一条公平调度使正确进程永不决定。本-奥尔给出的是测度语句：对这个随机化协议，不终止的执行集合概率为零。量词不同，协议类也不同。把几乎必然听成「坏调度不存在」，会把零测集误认成空集。

第三层误解以为工程里常见的超时抖动就是这篇论文。抖动是确定性程序里的一段启发式：同一个种子、同一串到达时刻，行为可以完全重放。论文要的是真正进入概率空间的随机源，以及一句关于该空间的终止陈述。没有这句陈述，延迟被打散只改变经验频率，不改变「对手仍可挑选一条永不决定的公平路径」这一存在事实。本页也不把毫秒、重试曲线或随机退避写成可执行配方。对象是概念证据：随机性能够把活性从全称调度改写到几乎必然；它不是运维清单。

第四层误解把本-奥尔与 拜占庭将军问题 收成同一份人数表。口头拜占庭模型假定送达正确、发送者可知，并且缺席可被察觉；难处是叛徒可以对两名听众说两套话。本页的核心故障是崩溃停机：进程安静地不再发送，不作恶、不伪造。完全异步里，慢与死仍然没有可检验的分界，随机化解决的是对称僵局，不是口头矛盾证词。论文确实另写了拜占庭变体，容错份额更苛刻；那是另一条轴上的存在性结果。本页不展开伪造、双花或配额计算，以免把容错界限误认成攻击菜谱。

协议观念：提议、选票、硬币#

模型与 FLP 共用完全异步：没有全局时钟，消息可被任意有限延迟，但对正确进程之间的信道，发出的消息终将被投递。允许至多 \(t\) 个进程崩溃停机，其余为正确进程。二进制输入，决定一旦写出就不可撤回。一致性禁止两个已决定的进程写出不同的值；有效性禁止在全体初值都是 \(v\) 时决定别的东西；终止不再要求每一条合法调度上都发生，而要求对硬币测度几乎必然发生。崩溃份额的经典门槛是 \(n \ge 2t+1\)：正确进程始终占多数，这是安全论证要用的计数，不是集群容量规划。

进程带着一个局部偏好进入协议，初始即自己的输入。时间被切成编号递增的轮，每一轮只有两步消息交换，没有第三种秘密指令。第一步是提议。每个仍在运行的进程把自己当前的偏好广播出去，然后等待 \(n-t\) 条同轮提议——崩溃的那些人可以永远不来，所以不能傻等到 \(n\)。若在这批提议里看见严格超过半数写着同一个值 \(v\)，它在第二步广播一张写着 \(v\) 的选票；若没有这样的多数，它广播一张空白票。超过半数是不可并存的：同一个有限集合里不能同时藏着两个大于 \(n/2\) 的、值相异的子集。因此一轮之内，非空选票至多指向一个值。这一步不抛硬币。硬币只在对称尚未被多数打破时才出场。

第二步是收票。进程再等 \(n-t\) 张同轮选票。若至少 \(t+1\) 张非空票写着同一个 \(v\)，它决定 \(v\)。\(t+1\) 不是随便挑的整数：看见这么多张 \(v\) 票，意味着即使再减去全部 \(t\) 个可能的崩溃，仍至少有一张 \(v\) 票来自正确进程；而任何其他正确进程在等待 \(n-t\) 张票时，必须与这 \(t+1\) 张相交——两批加起来超过 \(n\)，鸽笼迫使重叠。于是：有人决定 \(v\) 的那一轮，所有尚未决定的正确进程至少看见一张非空的 \(v\)，从而把偏好改成 \(v\)。下一轮他们带着同一个偏好出发，提议阶段会再次形成多数，决定在随后的轮次里扩散。安全在每一条执行上都成立，包括那些碰巧永不终止的零测执行：协议从不在证据不足时写下第二个值。

若第二步既凑不够 \(t+1\) 张同值票、又至少看见一张非空的 \(v\)，进程不决定，只把偏好改成 \(v\)，进入下一轮。若第二步收到的全是空白票，对称仍在：没有多数、没有可继承的候选。此时它才抛一枚公平硬币，把偏好随机改成 0 或 1。这枚硬币是局部的、私有的，不是全员共享的公共随机串。随机化算法 里拉斯维加斯算法从不撒谎、只让运行时间成为随机变量；这里的安全同样从不撒谎，随机性只买活性。全体初值都是 \(v\) 时，提议阶段一开始就有多数，空白票不会成为正确进程的稳态，硬币甚至不会被用到——有效性因此是确定性的，不靠运气。

观念上的几何到此已经够用。本-奥尔没有给出可粘贴进代码库的实现，也没有比较哪种伪随机发生器更合适。局部硬币的代价写在期望里：正确进程必须「碰巧」抛成够一边，才能在提议阶段凑出超过半数；这个正概率可以随 \(n\) 指数变小，于是期望轮数可以大得没有服务指标的意义。后来的工作引入共享硬币，让全体正确进程在一轮里看见同一枚随机比特，期望轮数才被压到多项式。那是另一份对象。本页停在 1983 年那两步：多数用来锁安全，各自的硬币用来打破「人人看见的都是平局」。把这两步写成带超时的重试循环，或写成如何在机房里布置随机延迟，会离开证明，走进本页明确拒绝的配方。

论文里的拜占庭变体只改变故障种类与可容忍份额，不改变「安全靠计数、活性靠硬币」这条交换。叛徒可以撒谎，计数必须更保守，于是 \(n\) 相对于 \(t\) 的倍数更苛刻。本页不写出那一套计数，也不讨论如何编造两套证词。承认变体存在，是为了标明对象边界：读者若要走口头矛盾那一条轴，应去 拜占庭将军问题，而不是把本页的崩溃协议加一层伪装。

概率 1：测度语句，不是全称调度#

终止陈述必须说清楚概率空间是什么。一轮里，每个正确进程在需要时独立抛出一枚公平硬币；无穷多轮给出一个无穷乘积。公平调度仍然要求：发给正确进程的消息终被投递，正确进程无限次获得事件。对手可以挑选延迟，甚至可以在看见本轮已经抛出的硬币之后再决定先投递哪一封——只要他不能把正确进程的信永远扣押。在这种公平性下，若某一轮正确进程的硬币碰巧足够一致，提议阶段就会出现超过半数的同一值，随后的选票阶段就会锁住决定。每一轮出现这种「足够一致」的概率有一个与 \(n\) 有关的正下界；下界可以很小，甚至随进程数指数衰减，但它严格大于零，且各轮相互独立。无穷多次独立试验中，成功一次的概率是 1。期望轮数可以很大：局部硬币要靠「碰巧大家抛成一边」来形成多数，这是存在性结果的代价，不是把指数期望写成可接受的服务指标。

这句话与「所有调度都终止」差一个量词。存在硬币序列使协议永远在平局里摇摆，正如存在无穷次抛硬币永远不出现连续十个正面。测度论允许零测的坏事件；FLP 不允许你用「坏调度很少见」来代替「坏调度不存在」。本-奥尔接受前者，拒绝用它冒充后者。对手被允许挑选延迟，甚至被允许在看见本轮已经抛出的硬币之后再决定先投递哪一封，只要发给正确进程的信不会被永久删除。永久删除是另一类故障；公平异步用的是任意有限延迟。在这个许可下，正概率的「足够一致」不会被拖延本身消灭，只会被推迟。推迟可以很长，概率 1 仍然只保证有限步内几乎必然决定，不保证步数有一个与硬币无关的上界。这也是为什么随机化不是部分同步的别名。部分同步给时间：存在某个未知时刻之后，延迟被未知上界管住，超时终将变成关于停机的正确推断。随机化给硬币：不需要上界出现，需要随机源与公平投递。兼职议会与 Paxos 走的是安全始终成立、活性依赖领导者最终独占一轮的那条路，与部分同步是亲戚，与局部硬币不是同一扇门。三扇门互不吞并。把它们画成一张「给集群加点随机就会永远可写」的操作清单，会把证据装置误认成配方。

它证明了什么，也就同时划出了它没有证明什么。它证明：完全异步加崩溃，只要允许局部随机选择，二进制共识的安全可以是全称的，终止可以是几乎必然的。它没有证明拜占庭口头模型里的人数下界，没有证明确定性协议在同一模型里突然可以终止，也没有给出生产系统里该把哪一个超时设成多少毫秒。1983 年这篇四页短文的力量在于把「自由选择」写成一条可检验的交换：你交出最坏情况的全称活性，换回概率 1 的进展。交换是显式的。后来的共享硬币、故障检测器与部分同步，都是在别的前提上另写合同；它们不把本-奥尔变成过时的反例，正如本-奥尔不把 FLP 变成过时的定理。

跨域连接#

• 概率论：几乎必然是测度为一，不是「每一个样本点都发生」。把各轮硬币看成无穷乘积空间，永不形成多数的执行对应于一个零测集：可以写出来，但不负担概率质量。大数定律在这里以最粗的形式出现——不是样本均值收敛，而是独立正概率事件无穷次重复后几乎必然至少成功一次。期望轮数可以随 \(n\) 变坏，与概率 1 并不打架：随机变量可以几乎必然有限而期望无穷，或期望有穷但大得没有工程意义。把「概率 1」听成「实际上总会很快结束」，是把测度语句偷偷换成了关于均值的愿望。论文提供的是前一句。
• 贝叶斯定理：异步里的沉默不是关于「对面已死」的似然证据，因为延迟与崩溃产生形状相同的观察。用超时去更新「他已经停机」的信念，等于在模型禁止的地方塞进一条似然比。本-奥尔不走这条更新：进程不推断谁死了，只根据已收到的提议与选票计数，证据不足就抛硬币改偏好。硬币不是对停机事件的后验，而是在观察欠定的时候主动给配置加一点外源随机性，好让下一轮的计数不再对称。把随机化听成「用贝叶斯方法猜谁崩了」，会把决策规则误认成停机诊断。
• 集合论：一轮的安全靠的是集合相交，不是机柜拓扑。大于 \(n/2\) 的子集不能有两个值相异的副本同时存在，所以非空选票至多指向一个值。\(t+1\) 与 \(n-t\) 的相交保证决定可以传播：两批消息的基数之和超过全集，交非空。配置的价——从该点出发仍可及的决定值集合——在随机化协议里变成了随机变量的支撑：安全要求支撑永远不能同时含有两个已写下的不同值；活性要求支撑几乎必然在有限步内变成单元素。把这些集合画成可用区名单，会把外延对象误认成布线图。
• 时间哲学：完全异步仍然拒绝一个全局共享的「此刻」。轮次编号是协议自己数的逻辑节拍，不是墙上时钟。缺席不是可观察的现在，而是可能仍在未来才到达的延迟。本-奥尔没有把「该到而未到」写成已经发生的事件，因此没有偷运同步。硬币插入的是逻辑时间里的一次分支，不是物理时间里的一次等待。把抛硬币理解成「再等一会儿碰运气」，会把随机性还原成超时，模型退回 FLP 的确定性自动机加启发式延迟。
• 认识论：正确进程必须在没有上帝视角时决定。证据是自己收到的那 \(n-t\) 条消息，不是关于「谁已死亡」的现成知识。确定性协议在这种证据下无法既保证一致又保证必然终止，这是 FLP 的认识论含量。本-奥尔改的是认知主体被允许使用的手段：在公共证据不足、两种未来仍都可及时，允许一次不由证据决定的选择。选择不是声称自己已经知道答案，而是承认尚未知道、同时拒绝永远停在尚未知道。写下决定仍然是一次不可撤回的知识承诺；随机性只出现在承诺之前。工程事故常发生在把本地超时当成已经共享的公共知识——那是把「我等够了」误认成「我们都知道他死了」。

参考文献#

• Michael Ben-Or, "Another Advantage of Free Choice: Completely Asynchronous Agreement Protocols", Proceedings of the 2nd Annual ACM Symposium on Principles of Distributed Computing (PODC), 1983, pp. 27–30. DOI: 10.1145/800221.806707. —— 本文对象：完全异步下用局部硬币达到几乎必然终止的二进制共识。
• 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. —— 部分同步下共识可终止，用以对照「给时间」与「给硬币」是两扇不同的门。
• 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. —— 不可靠故障检测器，用以标明第三扇门：给关于停机的信念，而不是给硬币。