随机共识与概率一终止

形式陈述

固定 $n\ge2$ 个进程，每个初始输入 $b_p\in\{0,1\}$ ，故障预算为整数 $0\le t<n/2$ 。进程只会崩溃停止，不会伪造身份、篡改状态或向不同接收者报告不同值。点对点信道可靠：发送给正确进程的每条消息最终交付且只交付一次。系统完全异步，没有时延上界；正确进程取得无穷多次执行机会。

本页证明一个Ben-Or式教学版本：每轮无条件消耗一枚私有公平硬币，已经决定的正确进程继续服务。其安全性对所有合法执行成立；概率终止证明则明确限制为在抽取随机位之前固定的、看不到消息内容的调度器。原始协议及强自适应调度器的结论见参考资料，本页不把两种证明混为一谈。[1, §§4–5.1][2]

先固定调度，再对随机位取概率

对固定输入，调度 $S$ 事先确定进程激活次序、崩溃事件及消息交付次序；它可以按发送者、接收者、阶段和轮号识别信封，但不能根据消息值、硬币结果或是否已决定而改动安排。等待中的进程若被激活但尚未收齐规定数量的消息，本次不推进。各次广播视为一次本地步骤，把同一载荷放进发往全体的信道队列；崩溃发生在步骤之间。

协议的控制流程不随bit内容改变：每轮总是两次广播、两次按消息数量等待、一次硬币操作、一次固定形状的本地更新。输出只记录结果，不跳出循环。因此，在固定 $S$ 下，每个阶段何时发生、使用哪些发送者的消息、哪些进程崩溃，都与硬币值无关。可容许的 $S$ 满足上述可靠交付、公平激活和至多 $t$ 次崩溃；相同控制流程使这些条件同时适用于所有硬币表。

令 $\omega=(C_{p,r})_{p,r}$ 为相互独立的公平bit表，其中 $r=1,2,\ldots$ 是逻辑轮号。进程 $p$ 在轮 $r$ 消耗 $C_{p,r}$ ；即使某个进程早已崩溃，概率空间中也保留它永远不会使用的虚拟bit。协议保证

\forall (b_p)_p\;\forall S\text{（固定且可容许）},\qquad \Pr_\omega[\text{每个正确进程最终决定}]=1.

完整性、统一一致性和提议有效性对每一张硬币表成立。概率只用于终止，不能给冲突决定留一个“小概率例外”。

两阶段协议

每个进程维护当前估计 $x$ ，初值为自身输入；维护不可撤销输出 $out$ ，初值为空。消息带阶段、轮号、发送者和值。每次接收集合只计算不同发送者，自己的消息也计入；提前到达的未来轮消息缓冲，过期轮消息可丢弃。

text

x := 自身输入; out := 未决定; r := 1
永久重复（除非崩溃）：
    广播 REPORT(r, x) 给全体进程，包括自己
    等待本轮最先收到的 n-t 个不同发送者的 REPORT，记为 R
    若 R 中某个值 v 的数量 > n/2，则 proposal := v
    否则 proposal := ?
    广播 PROPOSE(r, proposal) 给全体进程，包括自己
    等待本轮最先收到的 n-t 个不同发送者的 PROPOSE，记为 P
    c := 一枚新的私有公平硬币（每轮都抽，即使随后不用）
    若 P 中存在非 ? 的值 v，则 x := v；否则 x := c
    若 out 未决定且 P 中某个非 ? 值 v 的数量 > t：
        out := v，并输出一次 decide(v)
    r := r+1

下面将证明，同轮非问号提议至多有一种值，因此“存在 $v$ ”的分支没有歧义。最后三行条件处理可放在同一次本地更新中；它们不改变下一轮的控制步骤数量。决定后继续循环是协议的一部分，不是实现时可随意省略的注释。

直觉

第一阶段把“当前估计”变成可信的同轮提议：只有看见超过一半的报告，才发送非问号值。两个相反值不能都拿到这种证书。第二阶段把“有人形成证书”传播出去；看见一份非问号提议就继承它，看见至少 $t+1$ 份才决定。

两个阈值作用不同。 $>n/2$ 防止同一轮出现相反提议； $>t$ 保证任何大小为 $n-t$ 的第二阶段接收集合都会碰到决定证据。于是决定一旦出现，该轮其余进程离开时也会携带同一个估计，后续轮次不会翻转。

没有看到证书的进程用私有随机位换一个估计。随机化的任务是让某一轮终于汇合；它没有承担防止两个冲突决定的职责。汇合后安全规则接管后续行为。

三进程首轮得到问号、问号和1，硬币使估计全部变为1；C随后崩溃，A和B在第二轮用两票决定1 — 两阶段证据与一次随机汇合

例子与边界

三进程、一次崩溃的完整两轮

取 $n=3,t=1$ ，输入 $(b_A,b_B,b_C)=(0,1,1)$ 。每阶段等2个发送者；第一阶段需要2个同值报告才提议bit，第二阶段需要2个同值提议才决定。

下表给出一个合法交付次序下，各进程首轮取用的消息。先让三人都发送报告，再按表中的接收集合形成提议；随后按第二个集合交付提议即可实现，不要求协议有全局轮次屏障。

进程	首轮报告集合	自己的提议	首轮提议集合	本轮硬币	下一估计	是否决定
$A$	$A:0,B:1$	$?$	$A:?,B: ?$	$1$	$1$	否
$B$	$A:0,B:1$	$?$	$A:?,B: ?$	$1$	$1$	否
$C$	$B:1,C:1$	$1$	$B:?,C:1$	$1$ （未使用）	$1$	否

随后 $C$ 崩溃， $A,B$ 在第二轮互相交付消息。两人都收到报告 $A:1,B:1$ ，故都提议1；又都收到提议 $A:1,B:1$ ，其数量 $2>t$ ，于是决定1。第一轮迟到的消息仍须最终交付给正确进程，但可以因轮号过期而不参与新一轮。

这条示例调度在硬币抽取前就规定： $C$ 完成第一轮后崩溃；不是看到三枚1才选择令它崩溃。表中展示的是该固定调度下的一张硬币表。三枚都为1的概率是 $1/8$ ；实际上 $C$ 的硬币被忽略，所以这条轨迹只需 $A,B$ 两枚为1，概率为 $1/4$ 。后面的统一分析宁可使用保守的 $2^{-n}$ 。

为什么决定后不能立即退出

若某正确进程决定后不再发送任何消息，其他尚未决定者可能还在等待 $n-t$ 个发送者。协议的故障预算只允许至多 $t$ 个进程停止；不能把每个已经决定者再当作一个预算外故障。本页让正确进程输出后继续服务，终止指共识调用得到决定值，不指整个服务循环停机。若要释放协议实例，必须另加可靠的决定传播和退出证明；这里没有把它作为隐藏前提。

阈值和消息标签不能替换成口头的“多数”

当 $n=5,t=2$ 时，每阶段等待3人，REPORT门槛为3，PROPOSE决定门槛也为3；但当 $n=5,t=1$ 时，要等待4人，REPORT门槛仍为3，决定门槛则为2。三个数不能合并成同一个常量。

同一发送者的重复消息不能增加票数，上一轮的提议不能计入当前轮。轮号是证据的索引，不表示进程在现实时间上同步。任意进程都可能在别人还处于轮 $r$ 时进入轮 $r+1$ 。

推论与应用

安全性一：每轮只有一种非问号提议

若某进程在轮 $r$ 提议0，它看到了超过 $n/2$ 个不同发送者报告0；若另一个提议1，也有超过 $n/2$ 个发送者报告1。这两个发送者集合必相交，但一个未作恶的发送者在同一轮只广播一个估计，不能同时报告0和1，矛盾。因此每轮所有非问号提议取同一值，记为该轮的证书值（如果存在）。

这证明更新规则有定义，也证明安全性并未依赖硬币“碰巧一致”。崩溃可以使某些消息来不及发送，却不会制造一份相反报告。

安全性二：一次决定锁定下一轮

若某进程在轮 $r$ 决定 $v$ ，则存在至少 $t+1$ 个不同发送者曾在该轮提议 $v$ ，记此集合为 $D$ 。任意完成轮 $r$ 的进程都使用一个大小为 $n-t$ 的提议发送者集合 $Q$ 。因为

|D|+|Q|\ge(t+1)+(n-t)=n+1,

必有 $D\cap Q\ne\varnothing$ 。它至少看见一个 $v$ ，又不可能看见相反非问号值，所以离开该轮时把估计设为 $v$ 。

这一论证也覆盖现实时间上先于决定者完成轮 $r$ 的快进程：其既有集合 $Q$ 仍与后来决定所用的实际发送者集合 $D$ 相交。我们比较的是同轮真实证据，不是假设其他进程等到决定后才动作。

所以所有进入轮 $r+1$ 的进程都报告 $v$ 。每个完成该轮的进程收到 $n-t>n/2$ 个 $v$ 报告，继而收到 $n-t>t$ 个 $v$ 提议，因而决定或保留 $v$ ，并继续携带 $v$ 。归纳后所有后续轮只会决定 $v$ 。

若两个决定同轮，第一条引理排除不同值；若不同轮，取逻辑轮号较小的决定，用上述锁定排除较大轮的相反决定。这里不必取现实时间最早的决定。于是连稍后会崩溃的决定者也满足统一一致性。 $out$ 只写一次给出完整性。

有效性与每轮进展

若全部输入为 $v$ ，第一轮所有报告为 $v$ ，所有实际提议也为 $v$ ，每个完成者决定 $v$ ，后续保持。若二值输入并非全相同，0和1都确为某进程输入，而协议只可能决定0或1。因此所有输入情形都满足提议有效性。这个简短论证依赖二值域；把硬币输出替换成任意新值会破坏它。

至少有 $n-t$ 个正确进程。归纳假设它们都最终进入轮 $r$ ，则它们都广播REPORT，可靠交付和公平激活使各自收齐 $n-t$ 份；随后它们都广播PROPOSE，也都最终收齐。因此每个正确进程完成轮 $r$ 并进入下一轮。轮1从初始化成立，所以所有正确进程完成每一个有限轮号。这里使用决定者仍参与，并未要求任何延迟上界。

固定调度器下的概率证明

剩下的问题是：无限多轮中，是否以概率1有一轮汇合？不能简单把异步轮次当成互相独立的现实时间区间。令

\mathcal F_{r-1}=\sigma\bigl(C_{p,s}:p\in\Pi,\ 1\le s<r\bigr)

表示按逻辑轮号暴露的随机信息。它包含所有较小轮号的虚拟bit，不管它们在实际执行中何时才被使用；它不一定等于某个现实时间前缀的已知信息。

固定调度和不看值的控制流程决定了轮 $r$ 各阶段取用的发送者集合。该轮报告只依赖之前各轮产生的估计，所以全部REPORT与PROPOSE载荷都是 $\mathcal F_{r-1}$ 的函数。定义 $V_r$ 为轮 $r$ 中任何地方出现的唯一非问号提议值；如果整轮没有非问号提议，定义 $V_r=0$ 。同轮唯一性使其有定义，上述依赖关系使 $V_r$ 对 $\mathcal F_{r-1}$ 可测。进程本身不必知道这个全局变量。

考虑充分成功事件

E_r=\{C_{p,r}=V_r\text{ 对所有 }p\in\Pi\}.

给定所有较小轮号的bit， $V_r$ 已经固定，当前 $n$ 枚私有bit仍相互独立且公平，故

\Pr(E_r\mid\mathcal F_{r-1})=2^{-n}.

在 $E_r$ 上，每个完成轮 $r$ 的进程若看见非问号提议，就采用 $V_r$ ；若只见问号，则采用同为 $V_r$ 的硬币。所有进入 $r+1$ 的进程于是报告同一个值，前面的安全与进展证明保证每个正确进程至迟在完成轮 $r+1$ 时决定。

令 $q=2^{-n}$ 。事件 $E_1^c\cap\cdots\cap E_{k-1}^c$ 对 $\mathcal F_{k-1}$ 可测，所以反复使用条件期望得到

\begin{aligned} \Pr(E_1^c\cap\cdots\cap E_k^c) &=\mathbb E\!\left[ \mathbf1_{E_1^c\cap\cdots\cap E_{k-1}^c} \Pr(E_k^c\mid\mathcal F_{k-1})\right]\\ &=(1-q)^k\longrightarrow0. \end{aligned}

这里没有先假设 $E_r$ 彼此独立；条件概率已经足够。正确进程又都会完成每个有限轮号，故概率一的有限成功轮带来每个正确进程在有限执行前缀决定。

尾界、量词和强调度器的边界

令 $D$ 为所有正确进程首次决定的逻辑轮号之最大值。若前 $k$ 轮至少一次发生 $E_r$ ，则 $D\le k+1$ ，因此

\Pr(D>k+1)\le(1-2^{-n})^k,\qquad \mathbb E D\le1+2^n.

期望界来自首次成功轮的几何尾和；例如 $n=3$ 时为 $\mathbb ED\le9$ 。它是保守的逻辑轮数界，不是秒数、激活次数或总工作量界。公平异步调度可以让一轮等待任意久，决定后的服务还会永久继续。

FLP排除确定性协议对所有可容许执行的终止保证。本页改为“对每个规定的固定调度器，以概率1终止”；概率零的无限坏硬币序列仍被允许，所以没有推出逐硬币表的终止，也没有推翻FLP。[1, §§3–4]

若调度器可观察已经出现的硬币，再改变落后进程的报告交付顺序，轮 $r$ 的证书值就可能受同轮某些硬币影响。此时 $V_r$ 对 $\mathcal F_{r-1}$ 可测的关键论证失效，不能原封不动写下上述 $2^{-n}$ 条件概率。Ben-Or在强自适应调度器下的完整论证需要进一步处理交叠轮次；Aguilera–Toueg的证明使用相邻两轮的结构。[2, §5] 本页的有限终点是固定调度器模型下全部证明闭合，而不是用一句“总有一次所有硬币相同”跨过该困难。

参考资料

[1] James Aspnes, “Randomized Protocols for Asynchronous Consensus”, Distributed Computing16, 2003, pp.165–175：§4区分调度器观察能力与随机终止量词；§5.1给出Ben-Or两阶段协议并指出弱／强调度器的证明差别。本文为使调度骨架与值无关，明确采用每轮总抽一次硬币、决定后继续参与的教学版本。

[2] Marcos K. Aguilera, Sam Toueg, “The Correctness Proof of Ben-Or’s Randomized Consensus Algorithm”, Distributed Computing25, 2012, pp.371–381，DOI 10.1007/s00446-012-0162-z：§§2–4固定强对手模型与协议，§5处理正确性。本页核对其模型差异，未复现强对手的完整终止证明。

[3] Michael Ben-Or, “Another Advantage of Free Choice: Completely Asynchronous Agreement Protocols,” PODC, 1983, pp.27–30，DOI 10.1145/800221.806707，原始论文。此处具体算法与模型以资料[1][2]为核验依据。

形式陈述 ​

先固定调度，再对随机位取概率 ​

两阶段协议 ​

三进程、一次崩溃的完整两轮 ​

为什么决定后不能立即退出 ​

阈值和消息标签不能替换成口头的“多数” ​

安全性一：每轮只有一种非问号提议 ​

安全性二：一次决定锁定下一轮 ​

有效性与每轮进展 ​

固定调度器下的概率证明 ​

尾界、量词和强调度器的边界 ​

反向链接