共识与原子广播等价性

形式陈述 ​

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

固定进程集合 $\mathrm{\Pi }$ 与崩溃上界 $f$，采用可靠点对点信道和公平异步执行，并让两侧使用同一种 crash-stop 故障模型。本页固定分布式共识理路分布式共识Distributed consensus · Consensus problem多个进程在可能故障和通信延迟下对一个值达成一致的任务。的 uniform 一致性，以及原子广播理路原子广播Atomic broadcast · Total-order broadcast所有正确进程以同一总序交付广播消息。的统一前缀规格：后来崩溃进程已经作出的决定或交付也受安全条件约束，终止性则要求正确进程最终完成。在这组固定参数下，任一原语的实现都能用作黑盒构造出另一个。

辅助可靠广播理路可靠广播Reliable broadcast保证有效性、一致性和完整性的广播抽象。采用本库的普通 crash 版本：正确发送者的消息最终到达所有正确进程，正确进程一旦可靠交付，其他正确进程也最终可靠交付，且任何进程都不交付伪造或重复消息。这里不额外要求 uniform reliable agreement。每条待排序消息包含全局唯一的 ID 与完整 payload；crash-stop 进程停止前遵守协议，不会为同一 ID 伪造不同内容。

用原子广播实现共识：每个进程广播自己的提议值，并决定自己交付的第一条消息所含的值。统一前缀保证任何两个已决定进程，即使后来崩溃，也取得同一首条消息。

用共识实现原子广播时，先可靠传播完整消息，再依次运行编号为 $1,2,3,\dots$ 的共识实例。每个进程把自己已经可靠交付、尚未原子交付的完整消息组成有限提案集合。所有正确进程持续参加每个编号实例；本地集合为空时也提议空集，不能等到本地有待排消息才启动该槽位。第 $k$ 个决定值本身包含整批消息的 ID 与 payload；进程过滤已交付 ID，按固定 ID 次序交付其余消息，然后进入第 $k+1$ 个实例。这沿用 Chandra–Toueg Figure 7 的“决定消息集合后直接交付”步骤；持续空提案在这里明确保证 uniform 前缀版本不会漏掉仅由后来崩溃进程先参与的槽位。

决定已经给出了完整内容，因此不再等待本地另一次可靠交付。例如一个进程独自可靠交付 $m$、将其提议后崩溃，普通可靠广播可能不再把 $m$ 交给任何正确进程；若该提案被共识选中，正确进程仍直接从同一决定集合取得 $m$。多加一个“等本地可靠交付”的条件反而可能永久阻塞。若提案只含 ID、摘要或存储地址，就不具备这个保证，需要另证 payload 可取回。

安全性按槽位归纳：uniform 共识使所有决定该槽位的进程取得同一消息集合，固定批内排序和 ID 去重再给出共同交付前缀。决定值来自真实提案，每个提案又只含可靠交付过的消息，因此没有伪造；后来崩溃进程交付过的批次，也会随正确进程完成同一槽位而被交付。

还须排除消息饥饿。对正确进程广播的 $m$，普通可靠传播最终使所有正确进程取得它。若 $m$ 尚未被先前槽位排定，每个进程便把它保留在此后每个提案中。有限个崩溃结束、所有正确进程获知 $m$ 以后，再越过此前已经提交提案的有限个槽位，剩余提案都包含 $m$；共识的提案有效性迫使对应决定包含它。每个实例终止，正确进程持续参加，所以必会到达这样的槽位。这个论证依赖持续重提和实例进展，不是仅凭“一直调用共识”就自动成立。

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