时序和故障模型

时序和故障模型规定了分布式算法可以对消息延迟和处理器速度做出何种假设，以及组件允许以何种方式发生故障。

Definition

时序模型确定了关于消息传递时间和相对进程速度上限的假设，而故障模型则确定了进程和通道可能偏离其指定行为的方式集合。

Scope

本主题涵盖了同步、异步和部分同步的时序模型；从崩溃（故障停止）到遗漏和时序，再到任意（拜占庭）故障的故障分类；以及连接异步系统和基于超时的推理的故障检测器抽象。这些模型是推导可能性和不可能性结果的公理。

Core questions

• 算法可以假设哪些延迟和速度限制，以及超时如何依赖于它们？
• 协议必须掩盖哪些故障类别——崩溃、遗漏、时序、拜占庭？
• 如何通过增加故障检测器来增强异步系统，以规避不可能性结果？

Key theories

部分同步

实际系统既不是完全同步也不是完全异步的；部分同步模型假设延迟和速度的限制最终成立或未知，这足以解决共识问题，同时保持现实性。

故障模型层次结构

故障范围从良性的故障停止崩溃，到发送/接收遗漏和时序违规，再到任意的拜占庭行为；协议必须容忍的故障严重程度决定了所需的复制因子和消息复杂度。

不可靠故障检测器

抽象故障检测器提供关于哪些进程已崩溃的可能不正确的提示；表征足以解决共识问题的最弱检测器，将异步的严谨性与实际的基于超时的实现相结合。

Clinical relevance

生产系统在设置超时、选择复制因子或决定是否防御恶意参与者时，都会隐式地选择一个时序和故障模型；错误地理解这些假设是导致脑裂和数据丢失事件的常见根本原因。

History

在异步模型被证明对于容错共识过于薄弱之后，Dwork、Lynch和Stockmeyer于1988年引入了部分同步，Chandra和Toueg于1996年形式化了不可靠故障检测器，共同提供了使实际容错一致性成为可能的建模工具。

Debates

超时是时序假设还是故障检测器？

一种观点认为超时编码了（最终的）同步边界；另一种观点认为它们是抽象故障检测器的一种实现。这两种框架在很大程度上是等效的，但强调了网络模型和算法之间不同的设计边界。

Key figures

• Cynthia Dwork
• Nancy Lynch
• Larry Stockmeyer
• Tushar Chandra
• Sam Toueg

Seminal works

• dwork1988
• chandra1996
• lynch1996

Frequently asked questions

为什么在纯异步系统中无法实现可靠的故障检测？

在没有消息延迟限制的情况下，一个任意慢但活跃的进程与一个崩溃的进程无法区分，因此任何检测器有时都必须是错误的。这就是为什么异步系统需要通过时序假设或不可靠检测器来增强。