Chandra–Toueg 1996：会犯错的怀疑预言怎样成为共识的最弱检测器

破除误解：不可靠不是作废，最弱也不是最不准#

第一层误解把「不可靠」听成「这份预言没有用，FLP 仍然挡住一切」。不可靠的精确含义是：检测器可以在有限、甚至无穷多个时刻把活人写成嫌疑人，也可以暂时漏掉已经停机的进程。论文要的不是永不犯错的完美神谕——完美检测器 \(\mathcal{P}\) 几乎把同步偷运回来，完全异步里本来就造不出。它要的是：错误被允许，但错误必须服从分级后的契约。契约的下限可以弱到「终有一个正确进程，从此不再被任何正确进程怀疑」。有了这一句，旋转的协调者终会落到一个不再被误杀的活人身上，进展可以发生。没有这一句，每一轮都可以被误杀打断，安全锁得住，活性签不了。把「允许犯错」读成「等于没有预言」，等于拒绝阅读分级。

第二层误解把故障检测器听成心跳与超时的实现手册。工程里常用超时去逼近「谁可能已经停了」，那是把抽象往一台具体机器上安装的一种尝试，不是论文的对象。本页不写间隔、阈值、重试曲线，也不比较哪种超时更灵敏。检测器是接口：每个进程有一份随时间变化的怀疑名单，完备性约束崩溃者最终是否被写进名单，准确性约束活人最终是否被冤枉。名单从哪里来，论文当作预言，不当作配方。把抽象读成集群菜谱，会把「模型里多了一类信息」误认成「你应当把哪一个计时器拧到多少」。FLP 已经说明，没有上界的等待仍是异步；本页拒绝用另一套等待数字去假装上界已经出现。

第三层误解把「最弱」听成「犯错最多、最不准的那个」。弱是归约序，不是失误计数。检测器 \(D\) 比 \(D'\) 弱，意思是：只查询 \(D'\) 的进程，能够在本地模拟一份满足 \(D\) 规格的输出。\(\Diamond W\) 对共识最弱，是说两条方向同时成立：用它（加上多数）已经够解共识；任何别的、已经能解共识的检测器，都强到可以模拟它。再弱的预言给不出「最终有一个不被误杀的正确进程」，确定性协议就回到 FLP 的对手调度。最弱不是质量最差，而是分界线上刚好够用的那一点信息。把最弱听成「越不准越好」，把序关系读成运维口号了。

第四层误解把这份抽象收进 拜占庭将军问题，或收进本-奥尔的硬币。口头拜占庭假定送达正确、缺席可察，难处是叛徒对两名听众说两套话；本页的故障是崩溃停机，不作恶、不伪造，难处仍是完全异步里慢与死没有可检验分界。检测器补的是关于停机的信念，不是关于谎言的仲裁。随机化算法 那一扇门交出全称活性、换回几乎必然；本页交出的是「进程能查询一份会犯错的名单」，换回确定性终止。三扇门互不吞并。Paxos 与部分同步是亲戚，走安全始终成立、活性另写假设的路，与硬币不是同一扇，与怀疑预言也只在「额外假设」这一层上碰面，并不互相证明。

分级与归约：完备、准确，以及多数之下的几何#

模型与 FLP 共用崩溃与消息传递：没有全局时钟，正确进程之间的信终被投递，只是没有上界。允许至多 \(t\) 个进程停机。每个进程持有一份本地输出，即它当前怀疑已经崩溃的进程集合；输出可以来回改口。完备性只谈死人：强完备要求每个已崩溃进程终将被每一个正确进程永久怀疑；弱完备只要求终将被某一个正确进程永久怀疑。准确性只谈活人：强准确禁止在崩溃之前怀疑任何人；弱准确只要求存在某个正确进程，自始至终不被怀疑；把「自始至终」改成「存在某个时刻之后」，就得到最终强准确与最终弱准确。八个组合给出 \(\mathcal{P}\)、\(\mathcal{S}\)、\(\Diamond\mathcal{P}\)、\(\Diamond\mathcal{S}\) 以及弱完备一侧的 \(W\) 与 \(\Diamond W\) 等。名字是规格，不是芯片型号。

弱完备可以升成强完备，且准确性规格保持不变。观念上的装置是流言，不是拓扑图纸：进程把自己的怀疑名单传给别人，别人并入后再传。若某个正确进程已经永久怀疑了崩溃者 \(p\)，这份指控会扩散到所有正确进程。活人若从未被冤枉，扩散也发明不出新的冤枉——准确性被保存。于是 \(W\) 能模拟 \(\mathcal{S}\)，\(\Diamond W\) 能模拟 \(\Diamond\mathcal{S}\)。讨论共识时，真正卡住分界的是准确性有多弱，不是完备性有多弱。本页把升格当作存在性证据：弱完备并不额外损失可解性。不把流言写成报文格式，也不把扩散间隔写成可执行参数。

\(\mathcal{S}\) 的弱准确更强：存在某个正确进程，从来不被怀疑。这个人可以充当永不被误杀的协调者，共识甚至不需要正确进程占多数——多数是下一档的事。\(\Diamond\mathcal{S}\) 与 \(\Diamond W\) 只承诺这件事最终发生，未知时刻之前，每一轮的协调者都可能被误杀。安全必须在这段混乱前缀上独自成立，因此需要 \(n \ge 2t+1\)：正确进程始终占多数，两批 \(n-t\) 的集合必然相交。几何很短。进程带着估计进入编号轮，轮次把协调者轮流指向每一个标识。一轮里，活着的人把估计交给本轮协调者，再等待协调者的提议，或者等待自己的检测器把他写成嫌疑人。若提议被一个多数采纳，值被锁住：以后任何多数都会与这个多数相交，后继轮次不能改口。若协调者被怀疑，本轮作废，指针前移。安全从不询问检测器此刻是否说对了；检测器只被允许打断一轮，不许改写已经上锁的值。

活性问的是：作废会不会没完没了。最终弱准确给出那个未知时刻之后的稳定点：存在某个正确进程 \(c\)，从此不再被任何正确进程怀疑。旋转指针无限次经过每一个标识，终会落到 \(c\)。这一轮里，正确进程不会靠怀疑来抛弃他；在公平投递下，他的提议会被一个多数看见，锁与决定相继发生。这不是「每一条调度在第几步必须结束」的步数上界，而是：只要预言遵守 \(\Diamond W\)，公平执行里终止会发生。多数在混乱前缀上保护安全，稳定之后的那个不被误杀的活人保护活性。把这两句话写成带超时的重试循环，就离开证明，走进本页拒绝的配方。

最弱是同一条几何的对偶。若某检测器已经让你解共识，你就拥有一种能力：让全体正确进程对「哪一个标识值得信任」达成不可撤回的一致。反复使用这种能力，可以把「谁还被当成活人」收敛成一份名单——终有一个正确进程从此不再出现在任何人的嫌疑人里。那份名单正是 \(\Diamond W\) 的输出规格。反过来，若预言连这一句都给不出，旋转协调者就没有稳定点，FLP 的对手可以让每一轮在即将上锁时被误杀打断。四月这篇论文写出分级、完备性升格，以及 \(\Diamond\mathcal{S}\) 加多数足以解共识；把「凡能解共识者皆可实现 \(\Diamond W\)」写成严格抽取的，是同年 7 月钱德拉、瓦索斯·哈季拉科斯（Vassos Hadzilacos）与图埃格的姊妹篇。两篇共用抽象，本页把最弱当作这条纲领的结论，不把抽取步骤抄成伪代码。论文还证明，在同一模型里原子广播与共识可以互相归约：能决定一个值，就能决定一条序列。那是同一抽象的推论，不是另一套集群日志教程。

它证明了什么，也就划出了它没有证明什么。它证明：崩溃异步里，确定性共识所缺的那一点信息，可以写成一份允许无穷次犯错的怀疑预言；在多数正确时，\(\Diamond W\) 是分界。它没有证明完全异步里如何实现 \(\Diamond W\)——若纯异步就能实现它，就可以解共识，与 FLP 冲突。检测器是假设，正如部分同步是假设。它没有证明拜占庭口头模型里的人数下界，没有给出任何计时器该拧到哪里，也没有把领导者选举的后来记号 \(\Omega\) 当作本页的对象。\(\Omega\) 与 \(\Diamond W\) 等价是后话，本页停在 1996 年那份名单接口。交换是显式的：你交出「进程对停机一无所知」，换回确定性终止。硬币那一扇门交出的是全称活性；时间那一扇门交出的是「延迟可以永远任意长」。三份合同不要抄在同一张操作单上。

跨域连接#

• 认识论：异步里的沉默不是关于「对面已死」的现成知识。延迟与崩溃产生形状相同的观察，正确进程没有上帝视角把两者分开。FLP 说的是：仅凭自己收到的邮件，确定性主体无法既保证一致又保证必然终止。钱德拉与图埃格改的不是观察本身，而是主体被允许查询的东西：一份可以改口的怀疑名单。名单不是已经核验的死亡证明，而是允许犯错的信念输出。完备性约束真的死亡终将被信念捉住，准确性约束活人终将从冤枉里脱身。工程事故常发生在把本地等待当成已经共享的公共知识——那是把「我等够了」误认成「我们都知道他死了」。本页的预言把这句误认拆开：你可以怀疑，你必须承认怀疑可能错，你不得把错的怀疑写成第二个值。
• 时间哲学：完全异步仍然拒绝一个全局共享的「此刻」。\(\Diamond\) 读作「存在某个未知时刻之后」，不是墙上时钟的某一秒。最终弱准确并不指出稳定点在哪一毫秒，只断言稳定点存在。缺席因此仍不是可观察的现在，而是可能仍在未来才到达的延迟；检测器没有把「该到而未到」写成已经发生的事件，它只是终将停止冤枉某一个活人。把 \(\Diamond\) 理解成「再等一会儿就知道谁死了」，会把最终性还原成超时，模型退回没有上界的等待，定理退回 FLP。部分同步给的是延迟终将被未知上界管住；本页给的是信念终将稳定。两句都在谈「最终」，谈的不是同一种时间。
• 知识：单价配置是系统已经把答案写成公共事实的状态；二值待定是两种知识状态仍都可及。决定是一次不可撤回的承诺。检测器不直接写出共识的值，它写出的是关于「谁还配被等待」的临时信念。信念可以改口，决定不能。多数上锁把「这个值已经被一群人采纳」提升为公共事实；最终不被误杀的那个活人，把「我们可以结束等待」提升为终将到来的公共事实。学习者尚未得到稳定点时，正确动作是不宣称已知谁已死亡，而不是猜一个死者名单去强行提交。把「集群里有人已经提交」与「我已经知道有人提交」混成同一个时刻，会把活性失败误诊成分叉。活性失败是知识迟迟不能闭合；分叉才是安全被打破。
• 模态逻辑：论文把四个准确性规格写成带或不带 \(\Diamond\) 的句子，不是为了摆符号，而是为了标明量词落在哪一层。强准确是关于整条执行的全称句：任何时刻、任何活人，都不得被怀疑。最终弱准确把必然性从整条执行上拿掉，只留下存在量词：存在一个时刻、存在一个活人，使得此后怀疑不再落到他身上。模态里 \(\Diamond\) 本义是「在某个可达世界上为真」；这里的可达世界是执行的未来后缀。FLP 禁止的是没有这层 \(\Diamond\) 时的确定性全称终止；本页允许的是把 \(\Diamond\) 写进预言规格，而不是写进进程自己的局部推理。把菱形误读成「可能已经死了」，会把可能算子当成停机诊断，规格塌回一句无法核验的日常怀疑。
• 集合论：一轮的安全靠集合相交，不靠机柜拓扑。大于 \(n/2\) 的子集不能有两个值相异的副本同时存在，所以一旦某个值被一个多数采纳，后继多数必须与它相交，改口不可能。\(n-t\) 与 \(t+1\) 的算术保证：崩溃占掉 \(t\) 个座位之后，活着的人交出的两批回信仍然叠在一起。检测器的输出也是集合——嫌疑人集合——但它不参加相交论证；相交在估计与提议的值集合上进行。把怀疑名单画成可用区或机架图，会把外延对象误认成布线图。拓扑可以改变哪些消息暂时到得了；到得了与否改变经验频率，不改变「多数相交锁安全、最终不被误杀的活人锁活性」这两句外延陈述。

参考文献#

• Tushar Deepak Chandra & Sam Toueg, "Unreliable Failure Detectors for Reliable Distributed Systems", Journal of the ACM 43(2), 1996, pp. 225–267. DOI: 10.1145/226643.226647. —— 本文对象：不可靠故障检测器的分级，以及多数之下 \(\Diamond S\) / \(\Diamond W\) 足以解共识。
• Tushar Deepak Chandra, Vassos Hadzilacos & Sam Toueg, "The Weakest Failure Detector for Solving Consensus", Journal of the ACM 43(4), 1996, pp. 685–722. DOI: 10.1145/234533.234549. —— 姊妹篇：凡能解共识的检测器皆可实现 \(\Diamond W\)。
• Michael J. Fischer, Nancy A. Lynch & Michael S. Paterson, "Impossibility of Distributed Consensus with One Faulty Process", Journal of the ACM 32(2), 1985, pp. 374–382. DOI: 10.1145/3149.214121. —— 用以标明本页给的是额外预言，不是在原模型里反驳定理。
• Michael Ben-Or, "Another Advantage of Free Choice: Completely Asynchronous Agreement Protocols", Proceedings of the 2nd Annual ACM Symposium on Principles of Distributed Computing (PODC), 1983, pp. 27–30. DOI: 10.1145/800221.806707. —— 用以对照第二扇门：给硬币，而不是给怀疑名单。
• Cynthia Dwork, Nancy A. Lynch & Larry Stockmeyer, "Consensus in the Presence of Partial Synchrony", Journal of the ACM 35(2), 1988, pp. 288–323. DOI: 10.1145/42282.42283. —— 部分同步下共识可终止，用以对照「给时间」与「给信念」是两扇不同的门。对象见 Dwork–Lynch–Stockmeyer 1988。