原子广播

可靠广播只保证正确进程最终看到同一批消息，却允许它们以不同次序看到；而副本状态一般依赖操作先后——“存入 100 再翻倍”与“翻倍再存入 100”结果不同。原子广播让每个副本沿同一消息序列前进。副本在现实时间上可以快慢不同，但从相同初始状态出发的确定性状态机，只要交付到同一前缀就处于相同状态。

把每次全序交付追加到下一个索引，就得到复制日志公理库复制日志Replicated log · Replicated command log · Distributed log让多个副本维护一致已提交前缀并按索引应用命令的追加序列抽象。的 committed 序列；反过来，按索引交付日志新提交条目也可提供全序广播。两者是同一排序能力的不同接口面，日志另暴露索引、提交与应用位置。本页仍只规定消息交付性质，不吸收日志的本地尾部和恢复语义。

正例：节点 A 广播 $x$、节点 B 并发广播 $y$。合法的结果是所有正确节点都先交付 $x$ 后交付 $y$，或都先 $y$ 后 $x$；系统可任选其一。非法的结果是 A 按 $x,y$ 交付而 B 按 $y,x$ 交付——若两副本据此更新一个不可交换的对象（如追加日志），状态立即分叉。这个反例同时说明为什么仅有可靠广播不足以实现复制：消息集合相同而顺序不同，对有序敏感的状态机就是不同的执行。

边界在于，全序只承诺“大家采用同一个顺序”，不承诺顺序从何而来。它既不自动尊重实时先后，也不自动尊重 FIFO 或因果先后：即使同一发送者先广播 $m$、再广播 $m^{\prime }$，只要所有进程都先交付 $m^{\prime }$，普通全序规格仍然成立。因而原子广播与 FIFO、因果广播公理库因果广播Causal broadcast保证所有进程按因果先后顺序交付消息的广播抽象。约束不同维度；要既统一并发消息的顺序，又保留因果先后，必须额外采用因果全序广播规格。

原子广播也不等于“一次选一个值”。广播接口面对任意长消息流，需要为每条合法消息提供不饿死的交付保证；一个 one-shot 决定只能确定共同序列的第一个位置。

原子广播是状态机复制公理库状态机复制State machine replication · SMR让多个副本按同一确定顺序执行命令，从而实现容错服务。的直接排序手段。它与分布式共识公理库分布式共识Distributed consensus · Consensus problem多个进程在可能故障和通信延迟下对一个值达成一致的任务。在固定成员、可靠传播及匹配的 crash/termination 规格下可相互归约（见共识与原子广播等价性公理库共识与原子广播等价性Equivalence of consensus and atomic broadcast在固定成员、可靠信道与同一崩溃故障及活性版本下，共识和原子广播可相互归约。）。

从原子广播到 one-shot 共识：每个进程广播自己的提议，并决定它交付的第一条消息。完整性保证决定值确曾被提议，前缀全序保证所有决定者看到相同首条消息，有效性与一致性保证正确进程最终取得首条消息并决定。

从共识到原子广播：先可靠传播待排序消息；对槽位 $1,2,\dots$ 依次运行共识，让每个实例决定一批尚未交付的消息，再按消息标识的确定性顺序交付决定批次并过滤重复。一个实例的一致性给出一个槽位的共同内容，连续实例给出共同序列。交付活性还依赖明确的反饥饿条件：可靠传播最终让正确进程获知消息，正确进程持续启动后续实例，每个实例终止，而且提案规则包含所有 pending 消息或以公平批处理保证旧消息最终入选。缺少这些条件，反复共识可以保持全序安全，却永久跳过某条消息。

这一等价性把FLP 不可能性公理库FLP 不可能性定理FLP impossibility · Fischer–Lynch–Paterson theorem完全异步系统中即使只允许一个进程崩溃，也不存在保证所有可容许执行终止的确定性共识协议。传导过来——纯异步崩溃模型中不存在保证终止的确定性原子广播，实用协议需借部分同步公理库部分同步模型Partial synchrony · Partially synchronous system时间界存在但其数值或开始生效时刻不为算法预先掌握的分布式系统模型。、故障检测器或随机化取得活性。