最终领导者故障检测器 Ω

形式陈述 ​

固定进程集合 $\mathrm{\Pi }$、崩溃故障模式 $F$ 与时间域。最终领导者故障检测器 $\mathrm{\Omega }$ 在每个进程 $i$ 处持续输出一个标识

$${\mathrm{leader}}_i(t)\in \mathrm{\Pi }.$$

它唯一的稳定性要求是存在某个正确进程 $\ell$ 和有限时刻 $T$，使

$$\mathrm{\exists }\ell \in \mathrm{correct}(F),\mathrm{\exists }T,\mathrm{\forall }i\in \mathrm{correct}(F),\mathrm{\forall }t\ge T,{\mathrm{leader}}_i(t)=\ell .$$

量词中的“同一个、正确、永久”缺一不可。$T$ 之前，各正确进程可以输出不同标识，输出可以频繁改变，也可以指向已经或将要崩溃的进程。检测器不通知任何进程稳定时刻已经到来；即使当前所有输出恰好相同，参与者也不能仅凭这一观察断定以后不会再变化。

$\mathrm{\Omega }$ 不输出怀疑集合，因此不以 completeness/accuracy 分类。它只提供最终共同协调焦点，不告诉调用者哪些其他进程故障，也不保证当前 leader 响应迅速。故障检测器公理库故障检测器Failure detector按故障模式为进程提供受约束的怀疑集合、领导者等抽象输出。总览描述抽象输出历史；本页刻画的是其中一种特定输出类型，不能把它改写成 perfect failure detector 的简化版。

“$\mathrm{\Omega }$ 是解决共识的最弱故障检测器”是一条带模型的可约化结论。经典结果考虑可靠异步消息传递、崩溃停止故障和相应正确进程环境：$\mathrm{\Omega }$ 在标准多数正确等条件下足以恢复确定性共识的终止；反过来，任何能在该环境中解决共识的故障检测器，都可被算法转换为实现 $\mathrm{\Omega }$ 的输出历史。这里的“最弱”指故障检测器之间的可实现归约，不是输出字段更少、误报率最低或任意故障比例下都能工作。

直觉 ​

纯异步系统公理库异步系统Asynchronous distributed system消息延迟和进程相对速度没有已知有限上界的系统模型。里，进程永远无法凭有限等待区分“对方崩溃”和“消息很慢”。$\mathrm{\Omega }$ 不试图给出完整故障真相，只承诺混乱最终会收敛到一个共同且仍存活的协调者。共识协议可以在稳定前不断换轮次而保持安全，一旦这个共同焦点形成，新的提议便有机会持续获得进展。

它像一枚最终停止摆动的指南针，却没有“已锁定”指示灯。算法必须容忍指南针在任意长的有限前缀中指向错误方向；如果临时 leader 能产生不可撤销外部副作用，还需任期、quorum 或 fencing token 约束旧 leader，而不能把 $\mathrm{\Omega }$ 的未来保证当作当前独占权。

例子与边界 ​

在部分同步网络中，各进程可用心跳与自适应超时维护当前信任对象。稳定界出现前，网络抖动让 A 信任 B、C 信任 D，随后又交换判断；这仍符合 $\mathrm{\Omega }$。当消息延迟和正确进程速度最终受界，超时逐步放宽后，所有正确进程可以永久选择同一个持续响应的正确进程 $\ell$。实现依赖新增的最终时序条件，不代表纯异步模型仅靠本地时钟就能构造 $\mathrm{\Omega }$。

即使所有进程当前输出 $\ell$，$\ell$ 下一刻仍可能崩溃，检测器随后再次变化；只有定理中存在的未知 $T$ 之后，选中的 $\ell$ 才保证正确且不再替换。应用若需要租约期内唯一写权限，必须另外证明时钟界与 fencing；$\mathrm{\Omega }$ 本身没有租约期限，也不阻止旧 leader 继续向外部服务发送消息。

$\mathrm{\Omega }$ 与选主问题公理库选主问题Leader election使所有正确进程最终一致输出同一唯一进程为领导者的分布式任务。也不是同一对象。选主是算法需完成的任务，常要求进程最终宣布唯一合法领导者；$\mathrm{\Omega }$ 是可被协议反复查询的 oracle，稳定前允许多个不同输出。它可以帮助实现最终选主和共识，却不自动提供日志新旧、成员合法性或提交安全。

推论与应用 ​

最终领导者把共识的活性依赖压缩成一个精确接口：安全性可在所有异步执行中由轮次和相交证据维持，终止性则在 $\mathrm{\Omega }$ 稳定后推进。Paxos 类协议中的稳定 proposer 与 Raft 类协议中的长期 leader 都体现相似工程结构，但具体协议还需要选票、日志与成员规则，不能把它们简化成一次 $\mathrm{\Omega }$ 调用。

评估一个超时选主实现时，应分别检查它在何种网络与故障假设下最终稳定、稳定对象是否正确，以及调用协议是否能容忍稳定前的任意错误输出。只演示正常网络下选出一个 leader，没有建立 $\mathrm{\Omega }$ 对所有允许前缀和所有正确进程的量词。

参考资料

• Tushar D. Chandra, Vassos Hadzilacos, and Sam Toueg, “The Weakest Failure Detector for Solving Consensus,” Journal of the ACM 43(4), 1996, pp. 685–722。
• Tushar D. Chandra and Sam Toueg, “Unreliable Failure Detectors for Reliable Distributed Systems,” Journal of the ACM 43(2), 1996, pp. 225–267。
• Marcos K. Aguilera, Carole Delporte-Gallet, Hugues Fauconnier, and Sam Toueg, “On Implementing Omega in Systems with Weak Reliability and Synchrony Assumptions,” PODC 2003, pp. 306–314。