原子广播

可靠广播只保证正确进程最终看到同一批消息，却允许它们以不同次序看到；而副本状态一般依赖操作先后——“存入 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保证所有进程按因果先后顺序交付消息的广播抽象。约束不同维度；要既统一并发消息的顺序，又保留因果先后，必须额外采用因果全序广播规格。

统一前缀条件还约束故障节点。例如 A 已交付 [x] 后崩溃，B 先交付 [y]，即使 B 后来再交付 x，也已违反本页规格，因为 [x] 与 [y] 当时互不为前缀。仅要求“两个节点都交付两条消息时顺序相同”的较弱条件，会漏掉 A 永远不交付 y 的情况；因此本页的前缀版本不能在证明中偷偷换成仅比较共同消息的版本。

原子广播也不等于“一次选一个值”。广播接口面对任意长消息流，需要为每条合法消息提供不饿死的交付保证；一个 one-shot 决定只能确定共同序列的第一个位置。若系统允许崩溃恢复，还必须持久保存交付位置或由等效恢复协议重建；按进程生命期计的一次交付，并不自动保证跨重启只执行一次业务效果。

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

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

从共识到原子广播：可靠传播带唯一 ID 和完整 payload 的消息，对槽位 $1,2,\dots$ 依次运行 uniform 共识，决定有限消息集合。正确进程持续参加每个槽位，本地无 pending 消息时也提议空集。决定本身提供 payload，按固定 ID 次序去重交付，无需另等本地可靠交付；因而后来崩溃提议者已经入选的消息也不会卡在取回内容这一步。逐槽 uniform 一致性给出共同前缀。活性还要求每个实例终止，并在尚未排定时持续重提所有 pending 消息，使正确广播的消息最终入选。若改成只决定摘要或地址，就必须另证内容可用性，不能直接沿用这里的归约。

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