共识与原子广播等价性

形式陈述 ​

本库的分布式主线可按“可靠广播公理库可靠广播Reliable broadcast保证有效性、一致性和完整性的广播抽象。 → 共识公理库分布式共识Distributed consensus · Consensus problem多个进程在可能故障和通信延迟下对一个值达成一致的任务。 → 原子广播公理库原子广播Atomic broadcast · Total-order broadcast所有正确进程以同一总序交付广播消息。及其等价定理 → 状态机复制公理库状态机复制State machine replication · SMR让多个副本按同一确定顺序执行命令，从而实现容错服务。”阅读：可靠广播先固定消息传播与去重责任，共识决定一个值或一个日志位置，本页证明连续共识与全序交付可以互相构造，状态机复制再消费这条一致日志。本页只承担中间的等价定理，不重复定义四个相邻抽象。

固定进程集合 $\mathrm{\Pi }$ 与崩溃上界 $f$，采用可靠点对点信道和公平异步执行，并让两侧使用同一种 crash-stop 故障模型。还要成对选定 uniform 或 nonuniform 版本：一致性、完整性与全序是否约束崩溃前已经决定或交付的故障进程，以及终止性只要求正确进程还是采用更强范围，都必须在分布式共识公理库分布式共识Distributed consensus · Consensus problem多个进程在可能故障和通信延迟下对一个值达成一致的任务。和原子广播公理库原子广播Atomic broadcast · Total-order broadcast所有正确进程以同一总序交付广播消息。两侧保持一致。在这组固定参数下，任一原语的实现都能用作黑盒构造出另一个。

从共识构造原子广播时，还假设可靠广播公理库可靠广播Reliable broadcast保证有效性、一致性和完整性的广播抽象。在同一故障范围内提供匹配的 validity、agreement 与 integrity：正确发送者的消息最终由所有正确进程交付，消息不被伪造或重复交付，所选 uniform 版本若约束故障进程也须同步加强。公平执行则保证正确进程持续获得步骤、信道中的相关消息最终送达、连续共识实例不会停在某一槽位之外。

两个方向的归约构造如下。用原子广播实现共识：每个进程把自己的提议值全序广播，并决定自己交付的第一条消息所含的值。用共识实现原子广播：进程先用可靠广播公理库可靠广播Reliable broadcast保证有效性、一致性和完整性的广播抽象。传播消息，然后运行编号为 $1,2,3,\dots$ 的一系列共识实例，第 $k$ 个实例对"下一批待排序消息的集合"达成一致，各进程把第 $k$ 批消息按某个确定性规则（如消息标识排序）内部定序后依批次交付；若决定集合含有本地尚未可靠交付的消息，进程先等待该消息到达，再交付整个批次。构造还必须排除消息饥饿：每个进程都把已经可靠交付而尚未排序的消息放入此后每一轮提案。对一条由正确进程广播的消息 $m$，可靠广播保证所有正确进程最终都把 $m$ 放入待排序集合；在有限个崩溃都发生、尚存正确进程也都收到 $m$ 之后，每个后续共识提案都会包含 $m$，于是共识的有效性——决定值必须来自某个提案——迫使决定批次包含 $m$。若不加入这项公平性机制，仅有逐槽共识仍可能永远略过某条消息，违反原子广播的有效性；若收到决定后不等待缺失消息，则不同进程还可能无法按同一批次顺序交付。

这一定理不覆盖动态成员或成员重配置，也不把 crash-stop 归约自动提升为拜占庭版本。后两类模型需要重新定义合法消息、认证、法定人数和活性条件，再分别证明归约。

直觉

原子广播的实质是维护一本所有人一致的日志，而日志无非是"接连不断地回答'下一项是什么'"；每一次回答恰好是一个共识问题，所以无穷次共识拼出原子广播。反方向更轻：全序交付的第一条消息本身就是一次全体一致、来源合法且人人可得的决定。这个等价把两个表面不同的抽象钉在同一难度等级上——一个是"就一个值达成一致"的一次性任务，一个是"永远保持同序"的持续性服务，理论上却互为改写。由此得到的方法论收益是双向搬运：关于共识的任何可能性、不可能性或最弱假设刻画，都自动成为关于原子广播的同类结论，反之亦然。

例子与边界

把"原子广播实现共识"的方向走一遍即可看到各性质如何对号入座：设进程 $p$ 提议 $v_p$ 并全序广播。由广播的有效性与一致交付，每个正确进程最终会交付某条第一消息，故共识的终止性成立；由全序性质，所有正确进程交付的第一条消息相同，故一致性成立；又因交付的消息必是某进程实际广播的提议，有效性成立。三条性质分别恰好由广播规格的三个组成部分兑现，这种一一对应正是"等价"的直观内容。

边界方面：仅有可靠广播不足以替代原子广播——它保证消息集合一致却不统一顺序，不同副本按不同交错写日志立即分叉。单独一次共识也不够——一个实例只能决定有限信息，为无穷多条消息定序需要无穷多个实例（或改用多决策的共识变体）。若两侧采用不同的 uniform 范围或终止性量词，即使仍叫“共识”和“原子广播”，前述性质也不再逐项对应，不能继续引用同一版本的等价定理。

推论与应用

这一等价性让可能性与不可能性在两个抽象间迁移。FLP 不可能性公理库FLP 不可能性定理FLP impossibility · Fischer–Lynch–Paterson theorem完全异步系统中即使只允许一个进程崩溃，也不存在保证所有可容许执行终止的确定性共识协议。说异步崩溃模型中确定性共识无法保证终止，等价性立即推出确定性原子广播同样不可能；Chandra–Toueg 用故障检测器公理库故障检测器Failure detector按故障模式为进程提供受约束的怀疑集合、领导者等抽象输出。刻画共识可解性的结果，也可转用于原子广播。

工程上，反复运行共识为序列位置填值，可实现复制日志公理库复制日志Replicated log · Replicated command log · Distributed log让多个副本维护一致已提交前缀并按索引应用命令的追加序列抽象。的 committed 前缀；把日志条目按序送入确定性状态机，便得到状态机复制公理库状态机复制State machine replication · SMR让多个副本按同一确定顺序执行命令，从而实现容错服务。。日志的本地尾部、提交与应用接口属于这两个应用抽象，不改变本页归约的 requires，也不应反向成为等价定理的理解前置。

参考资料

• Nancy A. Lynch, Distributed Algorithms, Morgan Kaufmann, 1996，Chs. 14–17, consensus and total-order broadcast reductions。
• Tushar D. Chandra and Sam Toueg, “Unreliable Failure Detectors for Reliable Distributed Systems,” Journal of the ACM 43(2), 1996，atomic broadcast and consensus transformations。