主节点没有按时回复，备节点能否立即接管？第 07 篇的主备与链式复制把这个问题留在了故障时间线上：旧主可能已经停止，也可能仍在接收写入，只是无法与备节点通信。两个节点分别开始服务，数据复制得再快，也不能补回对写入顺序缺失的共同决定。

一次共识先缩小这个问题：固定一组进程，各自提出一个值，最终决定同一个值。日志复制可以连续处理多个这样的决定，但单次共识的边界需要先明确。MIT 6.5840 的 Paxos 讲义从故障与网络延迟难以区分切入；Stanford CS244b 把 FLP 放在开篇阅读。本篇沿着这一课程顺序，讨论决定必须满足什么，以及何种环境允许决定最终发生。MIT 2026 Lecture 4、Stanford 2024课程表。

共识需要同时限制结果与等待

考虑 A、B、C 三个进程，输入分别为 0、1、1。这里采用停止故障模型：进程可以永久停止执行，存活进程遵守算法，不伪造消息。成员集合事先固定；消息不会凭空产生或被篡改。崩溃恢复、动态成员和拜占庭故障需要额外定义。

一次决定是不可撤销的输出。暂存候选值、投票、收到多数回复都不能未经论证就称为决定。采用以下四个目标时，每条执行历史都能有明确的检查对象。

性质 本篇采用的要求 违规情形
一致同意，uniform agreement 任意两个已经决定的进程决定相同值 A 决定 0，B 决定 1
有效性，validity 决定值曾被某个参与进程提出 所有输入只有 0、1，却决定 7
决定完整性，integrity 每个进程至多决定一次 A 先决定 0，随后改为 1
终止性，termination 每个正确进程最终决定 某个一直正常执行的进程一直没有决定

前三项限制可以出现的结果，属于这里的安全性要求。最后一项要求进展，属于活性。只保证不分叉很容易：所有进程永远等待即可。只要求很快有输出也容易：超时便决定自己的输入。两者都没有完成共识目标。

“正确进程”需要按整条执行定义。在停止故障模型中，它不会崩溃，并持续获得执行机会。若 A 决定 0 后崩溃，B 再决定 1，uniform agreement 仍被破坏；只限制正确进程之间的 agreement 则可能不排除这条历史。Chandra–Toueg 在 §5 使用后一种 agreement，而其 §6.2 算法证明了更强的 uniform agreement。CT96，pp.239、244–246。

共识的“一致同意”也不等于第 06 篇讨论的线性一致性。共识约束一次决定的值；线性一致性约束对象操作历史及其实时先后关系。要从日志共识得到一个线性一致的 KV 服务，还需处理日志应用、请求去重、读取路径与操作返回时机。

超时能观察到什么

在逻辑时刻 5，A 仍未收到 C 的心跳。以下两条历史在 A 处具有相同前缀。

1
2
3
历史一：C 在发送心跳前停止；A 在 tick 1..5 收不到心跳。
历史二：C 正常发送；消息延迟至 tick 7；A 在 tick 1..5 收不到心跳。
共同观察：tick 5 时仍无心跳，触发同一超时分支。

如果 A 是确定性的，而且初始状态与本地事件相同，那么截至 tick 5 的行为也相同。它可以把 C 加入怀疑集合，但不能凭这段观察断言 C 已经崩溃。延迟上界若没有写入模型，任何固定超时都可能被更长但有限的延迟超过。

对工程系统而言，怀疑仍然有用。超时可以触发重新连接、发起新一轮选举，或暂时拒绝服务。但允许新主写入，还必须确保旧主不能继续形成冲突决定。这个约束由任期、投票与提交规则等协议机制承担，超时本身没有提供证明。

FLP 排除的是哪一种保证

FLP 考察确定性协议、完全异步的消息传递，以及至多一个进程停止执行。异步意味着没有可用于算法保证的消息延迟和进程相对速度上界；可靠意味着发给正确进程的消息最终收到。某条消息可以延迟很久，但不能因此被任意永久丢弃。

结论中的量词是：满足安全性和非平凡性、并要求容忍至多一次停止故障的确定性协议，存在一个允许的执行始终不作决定。它没有说所有执行都无法完成，更没有说多数服务器正常时每次请求都会失败。FLP，§2–3，pp.376–380。

原文的非平凡性比前面的有效性弱：0 和 1 分别能在某个可达配置成为决定值。它排除“无论输入是什么都决定 0”这样的退化办法，却不完整约束输出与输入的对应关系。现代有效性加上终止要求当然也不能避开这个更弱任务的不可能性；引用定理时仍应保留定义区别。Aspnes，§1。

双价配置如何阻止最终决定

一个配置包含所有进程的本地状态以及尚未收到的消息。若从某配置出发，存在决定 0 的延伸，也存在决定 1 的延伸，称它为双价配置；若可能的决定值只剩一个，就成为单价配置。双价描述后续调度留下的可能性，不表示已经有进程决定了两个值。

证明首先建立双价初态的存在。以较强的输入有效性理解这一步：全 0 输入必须最终决定 0，全 1 输入必须最终决定 1。把输入一个进程一个进程地改变，假如每个初态都单价，就会出现仅一个进程 p 的输入不同、决定值却不同的相邻初态。让 p 不执行，其他进程无法区分两种初态；容忍一次停止故障又要求它们最终决定，于是得到矛盾。原文用其较弱非平凡性也建立了对应结论。

初态双价还不够。普通算法可能收到下一条消息就安全决定。FLP 的关键引理说明：从双价配置出发，对选定的待处理事件，可以先安排有限的其他事件，再处理它，使结果仍双价。证明利用了不同进程事件的可交换性，以及对某个进程停止执行的容忍要求；如果所有这类延伸都强制变成单价，就能构造彼此无法区分却被要求作不同决定的执行。这是证明直觉，完整分类见原文 §3 的引理 3。

最后需要处理公平性：不能总把同一条消息延后。原文按进程轮转，并优先选择相应进程的较早消息；每次用引理补上一段有限调度，既处理选定事件又保持双价。无限连接后，每个进程都走无限步，每条消息最终交付，却始终没有决定。FLP，§3，特别是 p.380。

因此，这条坏执行甚至可以没有实际崩溃。证明中“可能有一个进程停止”迫使协议不能无限依赖某个特定进程；最终构造再利用这些约束安排持续不决定的执行。“至多一个故障”不能被改写为“必须恰好一个故障”。

部分同步给终止增加条件

Dwork、Lynch、Stockmeyer 给出两种典型的部分同步描述。第一种存在固定通信与进程速度界，但协议事先不知道界有多大。第二种界已知，却只在未知的全局稳定时刻 GST 之后成立。两者都比已知界从一开始成立的同步模型弱，又比完全异步提供更多进展条件。DLS88，摘要与 §1.2，pp.288–290。

在未知界的模型里，可以逐渐延长等待时间；在 GST 模型里，前期的轮次可能因过慢消息而失败。算法必须另外证明：环境满足所需条件后，某个轮次有足够时间完成。仅仅增长超时，并没有自动证明领导者最终稳定或消息处理不会饥饿。

安全性仍须覆盖不稳定阶段。若 GST 前已经出现两个决定，稳定后再多交换消息也无法恢复不可撤销的同意。DLS 将安全性与终止分别处理：协议的同意与有效性不能因迟迟未稳定而失效，终止则依赖相应最终时序条件。

“多数能通信足够久”可以概括一些算法的进展环境，不能替代完整模型。多数是固定配置中的多数，还要说明进程调度、通信方向、故障上限及协调者行为。对一组条件证明可终止，不表示真实部署中的某个超时配置已经满足那些条件。

故障检测器约束的是怀疑历史

故障检测器可以被抽象为每个进程随时间输出的怀疑集合。完整性描述故障者最终是否被发现，准确性限制对健康者的错误怀疑。两类性质不能相互替代：永远怀疑所有进程容易发现故障，但无法提供有用的准确性。

性质 要求
强完整性 最终，每个崩溃进程都被每个正确进程永久怀疑
强准确性 任何进程在崩溃之前不被怀疑
最终强准确性 从某个时刻起，正确进程不再被怀疑
最终弱准确性 从某个时刻起，存在一个正确进程不再被任何正确进程怀疑

强准确性包含“后来会崩溃的进程在崩溃前”的保护，不能只解释为正确进程不被怀疑。最终弱准确性也没有要求所有正确进程最终都被识别准确：除了受保护的那个进程，其他正确进程仍可能反复被误判。CT96，§2.3，pp.232–233。

强完整性与强准确性组成完美检测器 P；将准确性换成最终强准确性得到 ◇P，换成最终弱准确性得到 ◇S。符号 ◇ 表示最终性质。CT 的相关共识算法在多数进程正确时使用 ◇S：早期怀疑可以出错，协议仍需保护已经形成的决定约束，最终性质则帮助证明进展。

这是一组关于全部输出历史的假设。一次心跳实验没有误判，不能证明实现了 P；连续一小时没有误判，也不能证明此后永远满足 ◇P。需要把网络、调度与超时增长的条件写进实现论证。最弱故障检测器的定理属于另一篇 Chandra–Hadzilacos–Toueg 论文，不与 CT96 的检测器分类混用。作者文献目录。

随机化改变终止要求的量词

随机算法需要规定硬币操作的分布，以及调度者能够观察什么。给定允许的调度者后，常见目标是对随机结果以概率 1 终止；概率为零的不终止执行仍可能存在。它与确定性协议对全部允许执行都终止的要求不同。

调度者能否读取过去的随机结果、是否能预知未来结果，会影响协议证明。实际选举中加入随机等待，有助于减少重复碰撞，但仅凭这一机制不能宣布解决了完全异步环境中的容错共识。随机化协议必须独立证明同意、有效性与概率终止。Aspnes，§2、§4。

三个可以运行的有限调度

代码位于仓库 examples/distributed-systems/consensus08/main.go。它使用 Go 标准库、逻辑 tick 和有限消息队列，无网络端口、子进程或真实计时。它没有实现可容错共识算法，三个场景分别检查观察前缀、安全性反例与有限延迟后的恢复。

1
2
3
cd examples/distributed-systems
GOCACHE=/private/tmp/ds-go-cache go run -race ./consensus08 -check
GOCACHE=/private/tmp/ds-go-cache go vet ./consensus08

调度器每步将时钟增加 1，然后按入队顺序交付当步到期的全部消息。默认观察窗口为 5；-window 25 可以改变窗口，内置检查还覆盖 1、2、5、25。tick 仅表示模型步，不对应毫秒。

第一个场景比较 C 已停止和 C 心跳延迟两个世界。A 在窗口内记录完全相同的本地历史，包括触发怀疑；延迟世界的心跳随后到达。C 的真实状态由场景控制器知道，但没有泄露给 A 的决定逻辑。

第二个场景刻意采用错误规则：窗口结束时决定自己的输入。三节点之间的六条提案消息都晚一个 tick 交付。A、B、C 先决定 [0 1 1]，随后消息全部送达，输出仍不改变。一个有限前缀已经足以证明这个规则违反同意要求。

第三个场景保留相同输入与消息延迟，但等待收到全部三份输入后才决定最小值。窗口内三个进程都未决定；消息交付后全部得到 0。这个规则在无故障且可靠交付的场景中可以结束，却不能容忍某个成员在发送输入前崩溃。

本地实际执行输出为：

1
2
3
4
timeout: window=5 equal-prefix=true suspect-both=true delayed-heartbeat-at=7 delivered=1 pending=0
unsafe: window=5 before=[0 1 1] after=[0 1 1] agreement-violation=true delivered=6 pending=0
wait-all: window=5 before=[-1 -1 -1] after=[0 0 0] delivered=6 pending=0
checks: windows=[1 2 5 25] passed; finite-model observations only, no FLP proof

-1 是未决定的内部标记。检查同时断言生成与交付消息数相等、队列为空，避免把“延迟后恢复”偷换成永久消息丢失。坏规则在消息送达前后保持同一组决定，也让消息交付后的结果有明确比较。

这些结果属于已运行的本地模型观察。有限窗口未决定不能证明永远不决定；等待全部输入的简单规则失败，也不能证明所有协议都失败。FLP 的普遍结论来自双价性与无限公平执行的证明，不来自把窗口调得很大。

两道推导练习

题一： 三个进程都一直运行，调度器永久保留一条发给 A 的消息，其余消息正常交付。A 一直未决定。这是否给出 FLP 所需的允许执行？若仅保留一百万步再交付呢？

解答： 第一种违反发给正确进程的消息最终交付要求，不是该模型的 admissible 执行。第二种没有仅因延迟长而违规，但一百万步的有限前缀仍不能证明无限不终止。需要继续构造满足交付和进程执行条件的无限历史，同时保持不决定；FLP 的调度引理承担这一工作。

题二： C 已崩溃并最终被所有正确进程永久怀疑。A、B 正确，某时刻以后 A 从不被怀疑，B 仍无限次被误判。这样的检测器是否可以属于 ◇S？能否据此让 B 超时便单独决定？

解答： 这条完整历史满足强完整性和最终弱准确性的相应要求，因而与 ◇S 相容。完整实现是否属于 ◇S 还须检查所有允许历史。最终弱准确性只需一个正确进程获得持续准确性，不保护全部正确进程。它也没有授权 B 单独决定；安全决定仍需协议规则，否则 B 的输出可能与 A 冲突。

下一篇 Paxos 将具体处理这个缺口：后续轮次如何保留已经形成的决定约束，以及协调者竞争何时停止影响进展。

参考资料

论断证据表记录资料版本、页节与核验边界；本地验证记录保留模型执行命令、输出及未覆盖事项。