FLP 不可能性定理

证明反设协议同时满足三项性质，并把某一时刻所有进程的本地状态和在途消息合称为一个分布式配置公理库分布式配置Distributed configuration · Global configuration全部进程局部状态与通信介质状态组成的系统全局状态。。若从配置 $C$ 出发的可容许延伸只能决定 $0$，称它为 $0$-单价；只能决定 $1$ 则为 $1$-单价；两种决定仍可由不同合法调度到达，则称为双价。决定一旦发生，一致性会使配置永久保持相应单价，所以任何从双价进入单价的事件都像跨过一条不可逆边界。

第一步证明至少有一个双价初始配置。全 $0$ 输入按有效性是 $0$-单价，全 $1$ 输入是 $1$-单价。沿着逐个翻转进程输入的初始配置链，若每个配置都单价，就必有两个只相差进程 $p$ 输入、价态却不同的相邻配置。让 $p$ 在开始时停止，其余进程看不到 $p$ 的初值，因而无法区分两次执行，却被迫得到不同决定，矛盾。

第二步是核心事件引理。对双价配置 $C$ 和一个可应用事件 $e$，总能先执行一段不含 $e$ 的有限调度，再执行 $e$，并让结果仍为双价。反设所有这样的结果都已单价；沿不含 $e$ 的可达配置寻找执行 $e$ 后价态改变的边界，会得到两种次序产生不同价态。发往不同进程的事件彼此不可见，交换次序应到达同一配置，不可能改变价态；原论文再用“允许一个进程停止”处理事件集中在同一进程的剩余情形，从而排除反设。

有了事件引理，调度者不必永久扣住某一条特定消息。它公平枚举待交付消息与进程步骤，每轮先走有限条旁路，再履行当前义务，同时让新配置继续双价。于是每个正确进程仍不断取得步骤，发给它的每条消息也最终送达；但执行永远留在双价区，因此不含决定。不可区分性提供初始双价，事件可交换性则让调度者在不破坏可容许性的前提下反复绕开决定边界。

两进程协议中，进程 $p$ 收不到 $q$ 的消息时，无法仅凭等待时长判断 $q$ 已崩溃还是消息仍在网络中。如果协议为了活性允许 $p$ 独自决定，它必须在另一条执行中面对“$q$ 只是很慢且持有相反输入”的可能；如果永远等待，又不能满足一次真实崩溃下的终止要求。FLP 的证明把这种直觉推广到任意进程数和任意确定性协议，并用价态论证避免依赖某个具体超时算法。

一个持续竞争的 Paxos公理库PaxosPaxos consensus通过相交 quorum、递增 ballot 与已接受值继承规则，在崩溃故障下为单个共识实例选择唯一值。 执行可以不断提高 ballot 而长期不决定，这为“安全但未必活”提供了具体图像；但它不是 FLP 证明本身。Paxos 一旦选定值仍保持一致性，其工程化活性通常依赖最终稳定的领导者和足够长的稳定通信期。FLP 允许协议在许多正常执行中迅速结束，只否定覆盖所有可容许执行的确定性终止保证。

改变任一关键假设都会进入不同问题。部分同步公理库部分同步模型Partial synchrony · Partially synchronous system时间界存在但其数值或开始生效时刻不为算法预先掌握的分布式系统模型。在未知时刻后提供时延界，故障检测器增加关于崩溃的信息，随机化协议把保证改为对随机选择以概率 $1$ 终止，同步模型则直接限制调度。这些结果绕开了“确定性且完全异步”的前提，并非驳倒定理。拜占庭故障、消息丢失和网络分区又是更强的故障模型，不能把 FLP 的“一次 crash-stop”原样当作它们的完整可解性边界。

FLP 把安全性与活性之间的差别变成了系统设计的硬边界。实现可以让一致性在任意异步时序下成立，却只能在额外的时序、领导权或随机性条件下承诺进展；超时器本身只是产生怀疑，若没有最终稳定假设，并不会把完全异步系统变成同步系统。

引用该定理时必须同时写明二元共识任务、完全异步、确定性协议、可靠信道、至多一个crash-stop公理库崩溃故障Crash failure进程停止执行且此后不再采取步骤的故障。，以及“协议对所有可容许执行终止”的被否定量词。故障检测器公理库故障检测器Failure detector按故障模式为进程提供受约束的怀疑集合、领导者等抽象输出。理论进一步追问：需要补充多强的、可能暂时犯错的信息，才足以恢复共识活性。这比把结论缩成“分布式共识不可能”更准确，也更能解释实际协议为何既尊重 FLP 又能在常见网络条件下工作。