部分同步模型

形式陈述 ​

部分同步位于同步公理库同步系统Synchronous distributed system计算步和通信延迟有已知上界的系统模型。与异步公理库异步系统Asynchronous distributed system消息延迟和进程相对速度没有已知有限上界的系统模型。模型之间。Dwork、Lynch 与 Stockmeyer 给出两种标准形式。第一种形式假设消息延迟和正确进程相对速度存在有限上界，但算法事先不知道这些界的数值；界从执行开始便成立。第二种形式给定算法可知的界 $\mathrm{\Delta }$ 等参数，但只保证存在某个未知的全局稳定时刻（global stabilization time, GST），在 GST 之后，正确进程之间的消息与处理速度才持续满足这些界；GST 之前可有任意长但有限的延迟。

两种形式都必须和通信可靠性、公平性以及故障模型共同使用。部分同步本身只限制时序，不规定进程是崩溃停止、遗漏消息还是 Byzantine 行为，也不规定最多允许多少故障。协议的安全性与活性应分别量化：常见设计在 GST 之前也保持安全，但终止只承诺在 GST 之后经过有限时间发生。

直觉 ​

真实系统既很难提供从第一刻起始终准确的最坏延迟，也并非永远毫无时间规律。部分同步把这种处境压缩成一个可证明的承诺：系统可能经历任意长的混乱期，但最终会进入一个延迟受控且不再退出的时期；或者界一直存在，只是算法不知道它究竟多大。算法不能识别“现在就是 GST”，只能通过越来越宽松的等待策略，最终碰到一个足以覆盖真实界限的阶段。

这解释了安全与活性的分工。超时过短时，协议可能反复怀疑正确领导者、切换轮次，却不应据此提交互相冲突的值；一旦时序稳定且某轮使用了足够长的超时，消息能按证明所需顺序抵达，活性才恢复。部分同步没有推翻纯异步模型中的不可能性，而是明确加入了那个模型不提供的最终时间信息。

例子与边界 ​

考虑带轮次和领导者的共识协议。每轮等待领导者提案，超时后进入下一轮，并把超时长度逐轮增大。GST 前，调度器可以让每轮关键消息都晚于当轮超时到达，系统因此不断换领导者；只要锁定、证书或法定人数规则设计正确，已获得的安全证据不会被较慢网络破坏。GST 后真实消息界固定，超时最终超过该界；当一个正确领导者恰好主持这样的轮次时，提案与投票能及时完成，协议终止。

“网络大多数时候很快”不是同一个形式假设：它允许偶发慢消息在任意晚的时刻再次出现，未必存在永久稳定的 GST。GST 也不是系统广播的事件，进程没有一个可读取的 is_stable 标志；若算法依赖准确检测它，就已经假设了更强的预言信息。固定超时在实践中偶尔有效，也不代表证明处于部分同步模型，除非给出界最终成立或未知界一直存在的明确承诺。

此外，部分同步不等于只允许崩溃故障。采用 Byzantine 故障时仍可使用部分同步，但法定人数大小、签名条件与可容忍故障数必须按 Byzantine 模型另行推导。

推论与应用 ​

部分同步为许多共识协议提供活性条件。Paxos公理库PaxosPaxos consensus通过相交 quorum、递增 ballot 与已接受值继承规则，在崩溃故障下为单个共识实例选择唯一值。、PBFT公理库实用拜占庭容错Practical Byzantine Fault Tolerance · PBFT在部分同步网络与至多 f 个拜占庭副本下使用 3f+1 副本实现状态机复制的协议。 一类协议可在异步时序下维持安全，再借助最终稳定的领导者和超时获得终止。故障检测器公理库故障检测器Failure detector按故障模式为进程提供受约束的怀疑集合、领导者等抽象输出。从另一角度抽象最终可用的时序信息；最终强等检测性质与部分同步中的可解性有紧密联系。

FLP 不可能性公理库FLP 不可能性定理FLP impossibility · Fischer–Lynch–Paterson theorem完全异步系统中即使只允许一个进程崩溃，也不存在保证所有可容许执行终止的确定性共识协议。覆盖允许一个崩溃的纯异步确定性模型。部分同步协议能够终止，是因为可容许执行集合已被缩小：无限期推迟关键消息的执行不再被允许，而不是因为协议在 FLP 的原假设内绕过了结论。评估实现时，应分别查明 GST 前安全性、GST 后活性、超时增长方式与故障上限，不能用“最终网络会好起来”替代这些条件。

参考资料

• Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer, “Consensus in the Presence of Partial Synchrony,” Journal of the ACM 35(2), 1988, pp. 288–323。
• Hagit Attiya and Jennifer Welch, Distributed Computing: Fundamentals, Simulations, and Advanced Topics, 2nd ed., Wiley, 2004，Chs. 5–6，timing assumptions and consensus。