异步系统

异步调度者可以把任何关键事件推到更晚，却不能违反另行承诺的最终交付与公平性。协议观察到的只是一个有限前缀；在这个前缀之后，沉默节点既可能已经崩溃，也可能下一步就恢复运行。两条执行对观察者不可区分，因此超时只能产生怀疑，不能成为无条件的故障证明。

异步模型中的安全证明通常更稳健：消息再慢也不能制造两个决定。活性却需要排除对手永远在关键点改变领导者或延迟消息的能力，往往必须引入最终领导、部分同步或随机化。

进程 $p$ 向 $q$ 发送心跳后等待十秒。执行 $\alpha$ 中，$q$ 已 crash-stop；执行 $\beta$ 中，$q$ 正确，但心跳响应延迟十一秒。在十秒处，$p$ 的局部状态与已收消息可以完全相同。若此时永久排除 $q$，协议会在 $\beta$ 中误判；若必须永远等待确证，又会在 $\alpha$ 中失去进展。故障检测器理论正是研究要补充什么信息才能打破这组不可区分执行。

一条公平异步执行还可让第 $k$ 条消息延迟 $k$ 个调度阶段：延迟序列没有统一上界，但每条消息最终到达。相反，永久扣住某条发给正确进程的消息违反可靠交付条款。无上界与不交付是不同量词。

崩溃故障公理库崩溃故障Crash failure进程停止执行且此后不再采取步骤的故障。与公平性都独立于时序模型。“正确”只表示未崩溃；要保证它继续执行，还须在可容许执行公理库可容许执行Admissible execution满足给定调度、公平性和故障模型约束的执行。中加入进程公平性。异步也不消除本地顺序与消息因果，因果广播仍可保持 happens-before；缺失的是可用于截止期推理的时长界。

FLP 不可能性公理库FLP 不可能性定理FLP impossibility · Fischer–Lynch–Paterson theorem完全异步系统中即使只允许一个进程崩溃，也不存在保证所有可容许执行终止的确定性共识协议。表明：完全异步、确定性、可靠消息并允许一次 crash-stop 时，不存在覆盖所有可容许执行的共识终止保证。它没有否定正常调度下快速决定，也没有削弱协议的安全不变量。

故障检测器公理库故障检测器Failure detector按故障模式为进程提供受约束的怀疑集合、领导者等抽象输出。把关于崩溃的额外信息显式做成 oracle；最终领导者检测器 $\mathrm{\Omega }$ 只要求某个未知时刻后所有正确进程永久信任同一个正确进程。部分同步允许自适应超时最终实现这类稳定性，纯异步时间信息本身做不到。

实践系统通常借随机化或部分同步公理库部分同步模型Partial synchrony · Partially synchronous system时间界存在但其数值或开始生效时刻不为算法预先掌握的分布式系统模型。补入活性所需的信息；在最终时序稳定后，自适应超时才可能具体化 Ω 一类接口。Paxos公理库PaxosPaxos consensus通过相交 quorum、递增 ballot 与已接受值继承规则，在崩溃故障下为单个共识实例选择唯一值。 等协议由此形成“异步下保安全、时序稳定后求进展”的分工。理解协议时，应分别说明纯异步执行中保住什么，以及活性额外依赖哪个 oracle 或时间假设。