Lecture 15: Consensus and the FLP Impossibility — 共识问题与 FLP 不可能性
Lecture 15: Consensus and the FLP Impossibility — 共识问题与 FLP 不可能性
讲义对应：CS 425 FA2026 Lecture 17「Consensus（FLP 不可能性）」（原始讲义
L15.A.FA25.pdf《Impossibility of Consensus》，41 页）。本章在本笔记中编号为 Lecture 15，位于”经典分布式算法”部分。相关素材另参考L15.B.FA25.pdf（Paxos 对 FLP 的讨论）、L13.FA25.pdf（安全性与活性的定义、割与因果性）、L6.FA25.pdf（Chandra–Toueg 关于故障检测器与共识的关系）。 教材对应：Coulouris 5th Ed. Ch. 15 Coordination and Agreement（§15.5 共识与相关问题，其中 §15.5.2 即 FLP 结果）、§14.5（全局状态、安全性与活性）；补充：§15.1（故障检测器）、Ch. 18（复制）。 阅读材料：必读（全体学生，不可选）：Fischer, Lynch & Paterson, Impossibility of Distributed Consensus with One Faulty Process, JACM 1985，Sections 1–3。补充：Lamport, Shostak & Pease, The Byzantine Generals Problem, ACM TOPLAS 1982；Chandra & Toueg, Unreliable Failure Detectors for Reliable Distributed Systems, JACM 1996；Castro & Liskov, Practical Byzantine Fault Tolerance, OSDI 1999。
15.1 概述
本章回答分布式系统理论中最深刻的一个问题：$N$ 个进程各自提出一个值，只通过消息通信，能否保证最终所有正确的进程都对同一个值达成一致？ 这里的”能否”不是工程意义上的”能不能写出来”，而是在给定的系统模型下是否存在任何算法。答案令人震惊：在同步系统中，共识可以简单地用 $f+1$ 轮全体广播解决；而在异步系统中，即使只允许一个进程崩溃、即使算法是确定性的并且拥有无限的计算时间，也不存在保证终止的共识算法——这就是 FLP 不可能性（FLP Impossibility），由 Fischer、Lynch 与 Paterson 于 1985 年在 JACM 上证明，被公认为分布式系统领域最根本的结果之一。
本讲在整门课中处于理论枢纽的位置：向前，它把课程 Lecture 13（Snapshots）建立的安全性（Safety）与活性（Liveness）框架、”割与因果性”，以及课程 Lecture 5/6 的故障检测器（Failure Detector）三者汇合成一个精确的不可能性陈述；向后，它是理解 Paxos/Raft（课程 Lecture 19）、领导者选举（课程 Lecture 18）、复制状态机与两阶段提交（课程 Lecture 19、21/22） 为什么长成现在这个样子的唯一途径——这些系统全部都在”绕开 FLP”。本章的黄金法则是：
FLP 不是告诉我们”共识不可能”，而是告诉我们”共识的代价是什么”：你必须在异步性、确定性、总终止性三者中至少放弃一个。真实系统选择放弃”总是终止”，因为安全性被违反会损坏数据（不可恢复），而暂时不终止只是暂时不可用（可恢复）。
15.2 核心概念与分布式机制图解
15.2.1 共识问题（Consensus Problem）的严格定义
定义与目的：系统中有 $N$ 个进程 $p_1,\dots,p_N$。每个进程 $p_i$ 有一个输入变量（input variable） $x_i$（讲义取二值：$x_i \in \{0,1\}$，称为 binary consensus；一般情形 $x_i$ 可取任意值），以及一个输出变量（output variable） $y_i$，初值为 $\bot$（undecided，未决定），并且一旦写定就不可更改。进程之间只能通过消息通信，通信图是完全图（任何两个进程都能直接通信）。共识要求设计一个协议，使得最终所有正确的（correct，即未发生故障的）进程都写出同一个值。讲义的表述是：结束时要么所有进程把输出置为 0（all-0’s），要么全部置为 1（all-1’s）。
三个必须同时满足的性质（本章的基础，请务必背下来）：
性质 形式化陈述 通俗含义 违反它的后果 终止性 / 活性（Termination） 每个正确进程最终都执行”决定（decide）”动作：$\forall i \in \text{correct}:\ \Diamond(y_i \neq \bot)$ 每个活着的人最后都投了票 系统”卡死”：永远没有结果 一致性 / 安全性（Agreement） 不存在两个正确进程决定不同的值：$\forall i,j \in \text{correct}:\ y_i \neq \bot \wedge y_j \neq \bot \Rightarrow y_i = y_j$ 大家投的票必须一样 系统”分裂”：不同副本产生不同历史，数据损坏 合法性（Validity / Integrity） 决定的值必须是某个进程提议过的值：$\exists j:\ y_i = x_j$ 票不能凭空产生 系统”撒谎”：决定了一个谁都没提过的值 注意三个细节，它们正是初学者最常搞错的地方：
- 终止性要求的不是”最终达成一致”，而是”每个正确进程都做出决定“。这两者的差别恰恰是 FLP 中被违反的那一条：在 FLP 构造的执行里，大家从来没有”不一致”，而是永远没人决定。所以 FLP 的结论是”终止性无法保证”，不是”一致性无法保证”。
- 终止性只约束正确进程。崩溃的进程不需要决定，这正是容错的定义：故障进程可以什么都不做，协议只对幸存者负责。
- 合法性有强弱之分。讲义给出的两个版本是：Validity（若所有进程提议同一个值 $v$，则被决定的就是 $v$）与 Integrity（决定的值必须被某个进程提议过）；另外还有 Non-triviality（非平凡性）：存在至少一个初始状态最终导致 all-0’s，也存在至少一个初始状态最终导致 all-1’s。非平凡性不是”锦上添花”，而是 FLP 证明的必要前提——否则”所有人都决定 0”这个平凡协议就能满足一致性与终止性（它只违反合法性）。
直觉解释（”它是什么？”）：把共识想成一群人开会表决，但会议室的规则极其苛刻：没有主持人、没有时钟、没有”投票截止时间”，任何人可能中途离场（崩溃），而每个还在场的人都必须在没有任何人告诉他”投票结束了”的情况下，自己判断出一个最终结论，并且必须与所有其他人判断出的结论完全一致。这就是为什么它比”投票”难得多——投票有主持人宣布开始与结束，而共识没有。
共识 $\neq$ 多数表决（Majority Voting）：讲义明确把这一点列为思考题。多数表决解决的是”我这一票该投给谁”，它假设了投票的时机与集合是已知的；共识解决的是”在没有全局时钟、部分参与者可能消失的情况下，如何让所有人对同一个值做出不可撤销的决定”。多数表决实现的是单次收集，共识需要的是在故障与延迟下仍然收敛的过程。此外，多数表决本身并不保证活性（少数派可能永远等不到多数派），也完全无法对付”有人撒谎”（那需要拜占庭容错，见 15.2.12）。
共识的平凡解与它的非法之处：讲义思考题”什么是共识的平凡解（trivial solution）”的答案是：“所有人无条件决定 0”。它满足终止性（每个人都决定了）与一致性（大家决定的值相同），却违反合法性（如果没人提议过 0，决定 0 就是凭空产生）以及非平凡性（永远不可能出现 all-1’s）。这个平凡解提醒我们：不可能性定理必须把合法性写进前提，否则结论没有价值。
关键假设与系统模型：本章默认 crash-stop（失败即停止） 故障模型——进程要么正确运行，要么永久停止（不发送任何消息），不会发出错误的内容；通道是可靠（reliable）的，即不会丢失、不会篡改、不会凭空产生消息（这一假设在异步模型里只要求”最终送达”，不要求任何时间上界），并且是有向点对点的。当讨论拜占庭（Byzantine）故障时（15.2.12 起），故障进程可以任意行为，包括撒谎、合谋、对不同的接收者说不同的话。
15.2.2 为什么共识如此重要：它是最”小”的同步原语
定义与目的：共识不是一个孤立的学术问题，而是分布式系统的核心原语（core primitive）。讲义用一页幻灯片列出了四个看似无关的任务：让所有服务器”以相同顺序收到相同的更新”、维护彼此的成员列表并在有人离开或故障时同步更新、选出一个领导者并让所有人知道、保证对某个临界资源（例如文件）的互斥访问。它们的共同点是：一群进程要对某个东西的”值”达成一致——消息的顺序、某个进程的 up/down 状态、谁是领导者、谁拥有临界资源的访问权。
用途全景（每一条都能在本课程后面找到对应章节）：
问题 需要”达成一致的到底是什么值” 对应课程内容 全序多播 / 原子广播（Total-Order / Atomic Multicast） 每条消息在所有接收者处的相对顺序 课程 Lecture 15（Multicast） 领导者选举（Leader Election） “谁是领导者” 课程 Lecture 18；把选出的进程编号的最后一比特当作共识决定值即可 分布式互斥 / 锁服务（Mutual Exclusion / Lock Service） “谁持有临界资源”，即进入临界区的次序 课程 Lecture 16；Chubby、ZooKeeper 的锁就是共识的应用 复制状态机（Replicated State Machine） 每个副本执行的操作序列（只要顺序一致，状态就一致） 课程 Lecture 19/22；Paxos、Raft、Zab、Viewstamped Replication 的骨架 成员管理（Membership） “当前成员集合是什么” 课程 Lecture 5/6 原子提交（Atomic Commit，2PC/3PC） “全体提交还是全体回滚” 课程 Lecture 21/22 跨分片事务（Distributed Transactions） 多个分片的提交顺序与事务时间戳 Spanner（TrueTime + Paxos）、CockroachDB、TiDB 理论洞见：共识是”最小”的同步原语。讲义给出的方向是“许多分布式问题等价于共识，或者比共识更难”：完美故障检测器（Perfect Failure Detection）等价于共识；领导者选举等价于共识（选出一个进程后，用它的编号的最后一比特作为共识的决定值即可）；而一致性（Agreement，即所有进程对某个值达成一致但不要求合法性）比共识更难。之所以说”等价”，是因为两个方向都能互相归约：有了共识就能实现全序多播（把每条消息当作一个提议，用共识决定序号）、实现领导者选举（对”我推荐谁”达成共识）、实现复制状态机（对操作日志的每个槽位做共识）；反过来，任何一个能实现上述功能的系统，只要把它跑起来再看结果，就已经解决了一次共识。“归约”是分布式系统理论的核心工具：不可能性会沿着归约链向上传染。
直觉解释（”它是什么？”）：共识像一根钢梁。它本身没什么用，但一旦有了它，桥、楼、吊车（全序多播、选举、复制、锁服务）全都能搭起来；而如果这根钢梁在某个模型下造不出来，那么所有需要它的建筑在那个模型下都造不出来。这就是 FLP 让当年一大批”我们是 100% 可靠”的宣传一夜之间消失的原因：它们的可靠性宣称暗含了”我们能解共识”，而 FLP 说那不可能。
关键假设与系统模型：上面所有”等价”都必须在同一个系统模型下成立。异步模型下不可能实现的东西，在同步模型下可能有简单解；反之，同步模型下的算法搬到异步模型下可能丧失活性。讨论分布式算法时，第一句话永远是”系统模型是什么”——这也是讲义在给出”同步可解、异步不可解”之前，先花两页讲清楚两种模型的原因。
15.2.3 两种系统模型：同步与异步
定义与目的：同步系统模型（Synchronous System Model）对时间做出三条强假设：(1) 每条消息都在已知上界内送达；(2) 每个进程本地时钟的漂移率有已知上界；(3) 每个进程的每一步执行时间落在一个已知区间 $[lb, ub]$ 内（讲义原文：$\text{lb} < \text{time} < \text{ub}$）。异步系统模型（Asynchronous System Model）则完全不做这些假设：进程执行没有时间上界、时钟漂移率任意、消息传输延迟没有上界。
直观解释（”它是什么？”）：同步系统像一条装配线：每个工位有节拍，传送带的速度有保证，所以”这个零件 3 秒后一定到下一站”。典型的例子是讲义给出的多处理器 / 共享总线的超级计算机（例如 Cray）——所有处理器共享一个公共时钟与一条总线，时序是可控的。异步系统像寄平信：信一定会到（可靠），但可能明天到，也可能三个月后到，而且你无法从”信还没到”推出”这封信丢了”。讲义给出的例子是 Internet、ad-hoc 网络、传感器网络。
机制图解（两个模型的关键差别）：
同步模型: 每一步、每条消息都在已知上界内完成 ——「慢」是有限的
┌────┐ ≤ d_max ┌────┐ ≤ d_max ┌────┐
│ p1 │ ────────▶ │ p2 │ ────────▶ │ p3 │ 超时 => 一定故障(可判定)
└────┘ └────┘ └────┘
轮次(r)概念成立: 一轮的长度 >> d_max => 一轮之内的消息"必然全部送达"
异步模型: 没有任何上界 ——「慢」与「死」不可区分
┌────┐ ? ┌────┐ ? ┌────┐
│ p1 │ ────────▶ │ p2 │ ────────▶ │ p3 │ 等待 => 永远不知道还要不要等
└────┘ └────┘ └────┘
没有可用的轮次概念: "等多久"无法用任何有限常数界定
- 模型之间的包含关系（讲义特别强调的一点）：异步模型比同步模型更一般、也更难。因此
- 为异步系统设计的协议，自动适用于同步系统（异步协议不依赖任何时间假设，同步系统额外提供的时间保证它用不上）；
- 反之不成立：依赖超时的同步协议在异步系统中可能永远不终止（这正是 Paxos/Raft 的活性只在”部分同步”时得到保证的根源）；
- 不可能性结果沿反方向传染：既然异步模型是最一般的模型，那么”异步下不可能”意味着”任何比它更弱的假设下也不可能”；而”同步下可能”只是一个更强假设下的特例。
- 关键假设与系统模型：本讲最重要的方法论是讲义的“证明不可能性时可以同时收紧模型并放松问题”（Proof Setup）：为了证明异步系统中共识不可能，我们可以 (1) 采用更受限的系统模型（例如假设消息缓冲区是”全局的”、进程一步事件是原子的、通道不重复不丢失），(2) 考虑更容易的问题（例如只要求”某个进程最终写下输出”，而不是所有进程都决定；并且只允许一个进程崩溃，而且崩溃的是哪一个由我们选择，即对手可以挑选最有利于它的崩溃者）。为什么这样做是合法的？ 因为如果连”更容易的问题 + 更受限的模型”都不可能，那么”更难的问题 + 更一般的模型”当然也不可能。这个”削弱问题”的技巧贯穿整个 FLP 证明：FLP 允许对手挑一个进程让它崩溃，而正是这”一个”崩溃造成了不可能性。
15.2.4 同步系统中的共识：作为对照
定义与目的：在同步系统模型下，共识可解，而且解法出奇地简单——全体广播 + 集合取并 + 用确定的规则挑一个值。讲义给出的算法在 $f+1$ 轮内完成（$f$ 为最多可能崩溃的进程数），每轮每人把”自己上一轮新知道的值”多播给所有人，最后按”编号最小的提议者”（consistent minimum based on id，而不是最小数值）取值。完整伪代码、正确性论证与复杂度见 15.3.1。
直观解释（”它是什么？”）：像会议室里传纸条：每个人都把自己知道的所有提议写在一张新纸条上发给所有人。第 1 轮结束时，所有人都知道了所有人的提议（只要没人出事）。若有人出事——例如某人刚把纸条发给你就晕倒了，没能发给别人——那就需要再传一轮：你手里”多出来的那条信息”会在下一轮被转发给其他人。关键洞察是：每多一个可能出事的人，就需要多一轮来”把消息补上”，因为一轮最多能”吸收”一次崩溃造成的缺口。
机制图解（$f+1$ 轮的直观必要性）：
第1轮: 每人广播自己的初始值
第2轮: 每人广播"上一轮新学到的值"
...
第 f+1 轮: 仍在广播
为什么必须 f+1 轮? 想象一条"信息链条":
r=1: p_k 把值 v 只发给了 p_i (然后崩溃) ← 第 1 个崩溃
r=2: p_i 把 v 只发给了 p_j (然后崩溃) ← 第 2 个崩溃
... ← ...
r=f+1: 每多走一轮, 就多需要一次"崩溃"来阻断传播
需要 f+1 次崩溃才能让 v 在 f+1 轮后仍未被所有人知道
=> 但崩溃总数 <= f, 所以 f+1 轮之后不可能还有"未传播到的值"
- 能容忍多少故障：在 crash-stop（fail-stop） 模型下，只要 $f < N$（即至少有一个进程永远正确）共识就可解；$f = N$ 时系统里没有”正确进程”，共识命题退化（没有进程需要决定），因此没有讨论价值。讲义的归纳证明用到的恰好是”$f+1$ 轮内不可能发生 $f+1$ 次崩溃”。故障模型的差别很重要：
- fail-stop / crash-stop：进程停止后永远不再出现，其他进程看到它”静默”；
- crash-recovery：进程崩溃后可能重启并恢复（恢复后是继续参与还是需要重新同步状态，取决于协议），此时”崩溃次数”与”故障进程数”分离，成员管理（课程 Lecture 5/6）要处理”它回来了但我以为它死了”；
- omission（遗漏）故障：进程还在运行但可能丢消息，比 crash-stop 弱一些但更难推理；
- Byzantine（拜占庭）故障：进程任意行为（撒谎、对不同的接收者说不同的话、合谋），见 15.2.12——这时需要的冗余从 $f+1$ 变成 $3f+1$。
- 同步模型假设有多强？ 讲义明确点出：同步系统的典型例子是共享总线/公共时钟的多处理器（如 Cray、多核机器）。而互联网、云、跨数据中心的网络都不满足这些假设：消息延迟没有上界（拥塞、路由抖动、GC 停顿、虚拟机迁移、时钟漂移都能让延迟任意变大）。因此”同步模型下的共识算法”在实践中不能直接使用——它需要你相信一个你不该相信的假设。这正是我们必须认真研究异步模型的原因：在互联网上，唯一的”最坏情况”假设就是异步，而在异步下，共识不可能。
15.2.5 FLP 不可能性：定理陈述与精确含义
定理陈述（FLP Impossibility，Fischer–Lynch–Paterson, JACM 1985）：
在一个异步系统中，即使只允许一个进程发生崩溃故障（crash failure），也不存在任何确定性（deterministic）算法能够在有限时间内解决共识问题。 更精确地说：对任何满足一致性（Agreement）与合法性（Validity）的确定性协议，都存在一个执行（execution），使得其中所有进程永远不做出决定。
讲义的口径是：“无论你提出什么协议/算法，总存在一个最坏情况的执行（包含故障与消息延迟），使得系统无法达成共识”，并强调“这对任何算法都成立”。1983 年结果首次发表（PODC），1985 年发表于 JACM。
这个定理到底说了什么？六条必须逐一澄清的含义：
- 它说的是”不可能同时保证一致与总终止”，而不是”共识不可能实现”。FLP 构造的执行里，各进程从未决定不同的值——被破坏的是终止性。因此你永远可以说：”我的协议是安全的（永远不会出现两个不同的决定），只是不保证一定给出结果。”
- 它只针对确定性算法。随机化算法（每个进程用随机数打破对称性）可以绕过它：终止性变成”以概率 1 终止”，期望有限时间——详见 15.3.2 的 Ben-Or 算法。
- 它只针对异步系统。同步模型下共识可解（15.2.4）；部分同步（partially synchronous）模型下也可解——这是 Paxos/Raft/Zab 的基础。
- “一个”故障就够了，这是最惊人的地方。不是”故障太多导致不可解”，而是”只要允许 $f=1$ 且崩溃者由对手挑选，就足以不可解”。因此”加大冗余”（用 5 个副本而不是 3 个、用 100 个副本）完全不能解决异步下的 FLP 问题。
- 它假设没有（完美的）故障检测器。若系统提供完美故障检测器 P（强完备 + 强准确），异步模型就等价于同步模型，共识立刻可解。Lecture 5/6 的结论与此严丝合缝：在丢包网络中无法同时保证故障检测器的完整性与准确性，否则就能解共识。
- 最重要的实践含义：FLP 不是悲观的终结论，而是一张精确的”代价清单”。真实共识系统（Paxos、Raft）明确地放弃”总是终止”：它们保证安全性（Safety）永远不被违反，只在”网络条件足够好”时保证活性（Liveness）（Paxos 讲义原话：safety and eventual liveness；FLP result still applies: Paxos is not guaranteed to reach Consensus, ever, or within any bounded time）。它们换来的东西是：这些协议可以在真实互联网上运行，而”总是终止的异步共识”只存在于论文里。
现实类比（以及这个类比的边界）：把共识想成三个朋友约饭，其中一个可能手机没电。
朋友 A: "咱们吃火锅吧?" 处理: 等 B、C 回复
朋友 B: "行, 火锅" 处理: 等 A、C 回复
朋友 C: (手机没电 / 只是在地铁里)
─────────────────────────────────────────────────────────────
A 和 B 永远无法区分这两种情况:
(1) C 的手机真的没电了 => 应该"不等了, 我们自己定"
(2) C 只是暂时收不到消息 => 应该"再等等, 不然定的不是大家的意思"
而"再等等"与"不等了"这两个决定, 正是终止性与一致性之间的取舍。
类比的边界（必须点明）：(1) 约饭里 A、B 通常有”三点前必须定”这种外部时钟——一旦有了它，你就偷偷假设了部分同步，FLP 的前提消失了；(2) 约饭里偶尔”没达成一致”只是不方便，而分布式系统里”两个副本决定不同的值”是数据损坏；(3) 类比里只有 3 个人，但 FLP 的结论与人数无关——一万个副本也一样，因为问题出在”无法区分慢与死”这一认识论困境上，而不是”人不够多”。这个”无法区分（indistinguishability）”正是 FLP 证明的技术核心，我们马上会在引理 2 中看到它的第一次出场。
- 关键假设与系统模型（精确版）：
- 异步消息传递：消息延迟任意大但有限（可靠通道：不丢、不重复、不篡改）；进程执行速度任意（但每一步有限）；
- 确定性（deterministic）：进程的下一步动作完全由当前状态与收到的消息决定，不含随机选择，也不读取真实时间；
- 故障模型：至多一个进程崩溃（且对手可以选择崩溃哪一个）；崩溃 = 从此不再执行任何事件；
- 网络模型（讲义的做法）：把整个网络看成一个全局消息缓冲区（Global Message Buffer）——
send(p', m)把消息放进缓冲区，receive(p')从缓冲区中取出并投递一条消息，可能返回 null（即没有任何消息可投递）。投递哪条消息、什么时候投递、是否投递，全部由对手/调度器决定。这一点至关重要：它把”消息的任意延迟”变成了”在配置树中任选一条分支”。 - 问题被削弱：只要求”某个进程最终写下输出”（而不是所有正确进程都决定），崩溃数 $f=1$，且崩溃者由对手挑选。
FLP 的网络模型: 网络 = 一个巨大的缓冲区, 投递时机由对手决定
┌───────┐ send(p', m) ┌──────────────────────────────┐
│ p │ ───────────────▶ │ 全局消息缓冲区 (multiset) │
└───────┘ │ 消息可被任意延迟、任意排序 │
┌───────┐ receive(p') │ receive 可能返回 null │
│ p' │ ◀─────────────── │ (没有消息可投递 = 消息"还没到")│
└───────┘ (可能 null) └──────────────────────────────┘
★关键: "消息还在缓冲区里"与"消息永远不会被投递"对进程完全不可区分
15.2.6 FLP 证明的词汇表：配置、事件、执行、价
定义与目的：FLP 的证明是一段漂亮的组合论证。为了读懂它，首先需要四个精确定义（讲义用两页幻灯片给出，注意这里的”事件（Event）”不是 Lamport 事件）：
- 进程状态（Process State）：程序计数器、寄存器、栈、局部变量，加上输入寄存器 $x_p$（初值 0 或 1）与输出寄存器 $y_p$（初值 $\bot$）。
- 配置（Configuration）：全局状态 $C$ = 每个进程的局部状态 $\times$ 全局消息缓冲区的内容。一个配置就是”世界的一张完整快照”（对应 Lecture 13 的全局状态概念）。
- 事件（Event）：一个事件是原子的，由三步组成：(a) 某个进程 $p$ 收到一条消息（记 $e=(p,m)$，$m$ 是消息，可能是 null）；(b) 处理这条消息（可能改变 $p$ 的状态，也可能写定 $y_p$）；(c) 发送该事件产生的所有消息（放进缓冲区）。事件 $e$ 作用于配置 $C$ 得到新配置 $C^{\prime}$，记作 $C^{\prime} = C + e$。
- 调度 / 执行（Schedule / Execution / Run）：一个事件序列。若 $C_0$ 是初始配置，$s = (e_1, e_2, \dots)$ 是事件序列，则 $C_0 + s$ 表示依次应用这些事件得到的配置。注意：执行是有限还是无限由对手决定——这正是”终止性”要对付的东西。
“决定”与”已决定配置”：若某进程的输出寄存器被写定为 0 或 1，我们就说它决定了；决定一旦做出不可撤销（输出寄存器只能被写一次）。这个”不可撤销”是 FLP 证明反复使用的性质：一旦某个进程决定了 $v$，此后无论发生什么事件，这个进程的决定值都是 $v$，因此该配置之后的所有可达配置的决定值集合中都包含 $v$。
- 配置的价（Valence）：设从配置 $C$ 出发所有可能执行（在允许的故障范围内）所能决定的值构成集合 $V(C)$：
- 若 $\vert V(C)\vert = 2$（既能走到决定 0，也能走到决定 1），称 $C$ 是双价的（bivalent）——讲义原话：”bivalent means outcome is unpredictable（结果是不可预测的）”；
- 若 $\vert V(C)\vert = 1$，称 $C$ 是单价的（univalent）；进一步，若 $V(C)=\{0\}$ 称 0-价（0-valent），若 $V(C)=\{1\}$ 称 1-价（1-valent）；
- 若 $\vert V(C)\vert = 0$（从 $C$ 出发永远不会决定任何值——例如所有进程都崩溃了），这种配置按讲义的口径不属于两类之一；在 FLP 的证明中我们只关心”还会决定某个值”的配置。
为什么”价”这个概念是证明的枢纽：终止性要求”总有一条路径走到决定”。如果存在一条无限执行，路径上每个配置都是双价的，那么这条路径上的任何配置都不可能已经决定了值（因为一个已经决定了 0 的配置不能再走到决定 1，就不再是双价了）。于是”无限双价路径”$\Leftrightarrow$”一个永远不决定的执行”$\Leftrightarrow$”终止性被违反”。整个 FLP 证明就是证明这条无限路径存在，而它分两步走：引理 2（起点：存在双价的初始配置） + 引理 3（引擎：从任何双价配置都能走到另一个双价配置）。再加上一个”交通规则”引理 1（不相交调度可交换）。讲义把这三点列成”我们要证明的东西”清单：
- There exists an initial configuration that is bivalent.
- Starting from a bivalent config., there is always another bivalent config. that is reachable.
15.2.7 引理 1：不相交调度可交换（Commutativity）
定义与目的（引理 1）：设 $\sigma_1$、$\sigma_2$ 是两个调度（事件序列），它们作用于不相交的接收进程集合（即 $\sigma_1$ 里的每个事件的接收进程都不出现在 $\sigma_2$ 里，反之亦然），并且都能在配置 $C$ 上应用。那么 \(C + \sigma_1 + \sigma_2 \;=\; C + \sigma_2 + \sigma_1\) 也就是说，两个不冲突的调度可以交换顺序，结果完全相同。
直观解释（”它是什么？”）：像两个人各自写自己的日记：A 在自己的本子上写东西，B 在另一个本子上写东西，两人互不干涉。那么”A 写完 B 再写”和”B 写完 A 再写”，最后两个本子上的内容一模一样。注意这里的”互不干涉”是按接收进程划分的：一个事件只改变”收到消息的那个进程”的状态，并把新消息放进缓冲区；若两个事件作用在不同进程上，第一个事件不可能改变第二个事件的”触发条件”（消息 $m$ 在缓冲区内，可能被任意延迟），因此我们可以自由交换它们的顺序。
机制图解：
C 应用顺序 σ1, σ2 或 σ2, σ1, 结果相同
/ \ ┌──────────────┐
σ1 / \ σ2 │ 配置 C │
/ \ └──────┬───────┘
C1 C2 σ1 ┌───────────┴───────────┐ σ2
\ / ▼ ▼
σ2 \ / σ1 C1 C2
\ / │ σ2 │ σ1
▼ ▼ ▼
C'' (同一个配置) └──────▶ C'' ◀────────┘
条件: σ1 与 σ2 的接收进程集合不相交, 且二者都能在 C 上应用
为什么这个”交通规则”是必需的：FLP 要构造的是一条无限执行，而为了在双价配置之间”无限地走下去”，必须能够自由地延迟某个事件（把事件 $e$ 推迟到后面执行）。交换性告诉我们：”推迟一个事件”不会破坏执行的可应用性，也不会改变最终结果——只要这个事件与其他事件作用于不同进程。异步性的本质就体现在这里：消息可以被任意延迟而不被任何进程察觉，因此对手总能选择”先做别的事”。
关键假设与系统模型：交换性依赖于“事件是局部的”——一个事件的接收者只有一个进程。若事件是”全局的”（例如一次广播的原子提交），交换性就不成立。它也依赖于缓冲区的多重集语义：消息在缓冲区中的顺序不重要，重要的是被哪个进程、以什么顺序取出。
15.2.8 引理 2：存在双价的初始配置（以及”一个故障就够”的根源）
定义与目的（引理 2）：存在一个初始配置，从它出发既能决定 0、也能决定 1（即它是双价的）。
- 证明（严格遵守讲义的论证结构）：
- 反设：所有初始配置都是单价的（要么 0-价，要么 1-价），没有双价初始配置。
- 构造格（lattice）：$N$ 个进程的初始配置共有 $2^N$ 个（每个 $x_p \in \{0,1\}$）。把它们排成一个格：相邻的两个配置恰好只在一个进程的输入值上不同。
- 找跳变点：全 0 配置（所有进程提议 0）必然是 0-价的（合法性/非平凡性：大家都提议 0，怎么可能决定 1）；全 1 配置必然是 1-价的。于是沿着格中的任意一条”从全 0 到全 1”的路径（例如每次只把一个进程的输入从 0 翻成 1），数值必然发生跳变，因此存在一对相邻配置 $C_0, C_1$，其中 $C_0$ 是 0-价、$C_1$ 是 1-价。设二者唯一不同的是进程 $p$ 的输入值。
- 让 $p$ 崩溃（关键一步）：考虑这样一个执行——$p$ 从一开始就崩溃，一步都不走（事件序列中不包含任何以 $p$ 为接收者的事件）。那么从 $C_0$ 出发和从 $C_1$ 出发的执行，对其余所有进程完全不可区分：唯一的差别是 $p$ 的输入寄存器是 0 还是 1，而 $p$ 从不发送任何消息，这个差别永远不会被任何其他进程观察到。
- 矛盾：不可区分意味着，其余进程在两条执行中收到相同的消息、做相同的状态转换、最终决定同一个值 $v$。可是 $C_0$ 是 0-价（所有执行都决定 0），$C_1$ 是 1-价（所有执行都决定 1）——特别地，”$p$ 崩溃”这一条执行也必须决定 0 与 1 两者之一，矛盾。
- 机制图解（引理 2 的两张图）：
图 A: 初始配置的格与「价」的跳变
────────────────────────────────────────────────────────────────
沿"每次只翻一个进程的输入"的路径, 从全 0 走到全 1:
(0,0,0) ──▶ (1,0,0) ──▶ (1,1,0) ──▶ (1,1,1)
0-价 0-价 ↑ ? ? 1-价
└── 必然存在一对相邻配置 (C0, C1)
一个 0-价、一个 1-价, 且只差一个进程 p 的输入
────────────────────────────────────────────────────────────────
图 B: 为什么这一对不可能是「一 0-价、一 1-价」
────────────────────────────────────────────────────────────────
C0: p 输入 = 0 C1: p 输入 = 1
│ │
│ 令 p 一开始就崩溃, 一步不走 │
▼ ▼
其余进程看到的: 其余进程看到的:
· 完全相同的消息序列 · 完全相同的消息序列
· 完全不知道 p 的输入是 0 还是 1 · 完全不知道
│ │
▼ ▼
必须决定同一个值 v 必须决定同一个值 v
────────────────────────────────────────────
=> C0 与 C1 同价, 与「一个是 0-价、一个是 1-价」矛盾
=> 反设不成立: 某个初始配置必为双价 ★
这一引理为什么是”1 个故障就够了”的根源：证明里只用到一个进程的崩溃（那个输入值被翻转的 $p$），而且这个崩溃是我们（对手）主动选择的。所以 FLP 的不可解性与”能容忍几个故障”无关——一个就够了。请把这句话记牢：不是”故障太多”，而是”慢与死不可区分”。只要允许对手挑选一个进程让它沉默，它就能在”恰好让价格发生跳变的那个初始配置”上制造不可判定性。
为什么必须把 $p$ 的输入而不是别的什么东西翻转？ 因为在初始配置里，唯一的信息就是各进程的输入。价格（谁能被决定）作为初始配置的函数，必须从”全 0 侧的值 0”过渡到”全 1 侧的值 1”；而”过渡”只能发生在某条相邻边上——“翻转一个进程的输入”这件事的可观测后果，恰恰可以被”该进程崩溃”抹掉，因为崩溃的进程不发言，其输入对别人不可见。这就是引理 2 的全部魔法。
关键假设与系统模型：引理 2 只需要 (1) 存在至少两个可能的决定值（非平凡性，保证全 0 配置是 0-价、全 1 配置是 1-价）；(2) 至多一个进程崩溃就已经足够，而且崩溃者可选；(3) 进程不能读取真实时间或随机数（确定性），也不能通过”试探性地联系 $p$”来区分——异步模型中这种试探永远不会返回一个”确定没人在”的答案。
15.2.9 引理 3：从双价配置总能走到另一个双价配置
定义与目的（引理 3）：从一个双价配置出发，总存在一个事件序列，使得到达的配置仍然是双价的。（讲义原话：Starting from a bivalent config., there is always another bivalent config. that is reachable.）这个引理是”无限路径”的引擎：它保证我们不会被”卡”在某个双价配置上无路可走。
证明的骨架（讲义的三步走）：设 $C$ 是一个双价配置，$e=(p,m)$ 是任意一个可以在 $C$ 上应用的事件（例如”把缓冲区里的一条消息投递给 $p$”）。定义两个集合：
- $\mathcal{C}$：不执行 $e$ 就能从 $C$ 到达的所有配置的集合（即”先把 $e$ 压在缓冲区里，先干别的”能走到的所有局面）；
- $\mathcal{D} = e(\mathcal{C}) = \{\,c + e \;:\; c \in \mathcal{C}\,\}$：把 $e$ 应用到 $\mathcal{C}$ 中每个配置后得到的配置集合。
断言：$\mathcal{D}$ 中必有一个双价配置。 一旦这个断言成立，引理 3 就得证了——因为 $\mathcal{D}$ 里的配置当然是从 $C$ 可达的。
- 反证与两种情形（这是整个 FLP 证明最精细的地方）：反设 $\mathcal{D}$ 中全是单价配置。
- 因为 $C$ 是双价的，从 $C$ 出发既能到达 0 也能到达 1，于是可以找到 $\mathcal{D}$ 中的 $d_0$（0-价）、$d_1$（1-价）；
- 设 $d_0 = c_0 + e$、$d_1 = c_1 + e$，其中 $c_0, c_1 \in \mathcal{C}$；
- 关键的结构性事实：在 $\mathcal{C}$ 中取一条”从一个’$+e$ 之后呈 0-价’的配置 $c^0$ 出发、走到一个’$+e$ 之后呈 1-价’的配置 $c^1$”的路径（每一步只施加一个事件）。沿着这条路径，”$+e$ 之后的价”必然在某一处从 0 跳到 1；取跳变处的相邻两个配置作为 $c_0, c_1$，于是它们之差恰好是一个事件：$c_1 = c_0 + e^{\prime}$，其中 $e^{\prime} = (p^{\prime}, m^{\prime})$；同时 $d_0 = c_0 + e$ 是 0-价、$d_1 = c_1 + e$ 是 1-价。
然后按 $e^{\prime}$ 的接收进程 $p^{\prime}$ 与 $e$ 的接收进程 $p$ 是否相同，分成两种情形：
情形 I：$p^{\prime} \neq p$（两个事件作用在不同进程上）。由引理 1，$e$ 与 $e^{\prime}$ 可交换，于是 \(d_0 + e^{\prime} \;=\; (c_0+e)+e^{\prime} \;=\; (c_0+e^{\prime})+e \;=\; c_1 + e \;=\; d_1\) 也就是说：从 0-价的 $d_0$ 出发，施加一个事件 $e^{\prime}$ 就到达了 1-价的 $d_1$。于是 $d_0$ 同时具备两种能力：作为 0-价配置，从它出发的执行都决定 0；而沿着 $e^{\prime}$ 走一步到 $d_1$ 之后，从 $d_1$ 出发的执行都决定 1——按定义 $d_0$ 就是双价的。这与”$\mathcal{D}$ 中全是单价配置”的假设矛盾。$\blacksquare$
情形 I (p' ≠ p): 由图中的两条路径到达同一个配置 c0 ──e──▶ d0 (0-价) │ │ e' │ │ e' 这两个 e' 是同一个事件, ▼ ▼ 因为 e 与 e' 可交换(引理 1) c1 ──e──▶ d1 (1-价) => d0 + e' = d1 于是 d0 既能决定 0(自己是 0-价), 又能走到 d1 去决定 1 => d0 双价 => 矛盾!情形 II：$p^{\prime} = p$（两个事件的接收者是同一个进程）。此时 $e$ 与 $e^{\prime}$ 都作用于 $p$，二者的顺序不能随便交换，引理 1 直接用不上。讲义的做法是引入一条“$p$ 一步都不走”的有限、已决定的执行 $s$：
- $s$ 为什么存在：因为”最多一个进程崩溃”中的那个崩溃者由我们自由选择，就取 $p$ 为崩溃者。于是其余 $N-1$ 个进程都是正确的，它们必须在有限时间内做出决定（这就是 FLP 把问题削弱成”某个进程最终写下输出”的用处）。
- 设 $A = c_0 + s$，则 $A$ 是一个已决定的配置，记它的决定值为 $v$。由于 $p$ 在 $s$ 中一步未走，$s$ 与任何”只作用于 $p$ 的事件”都作用于不相交的进程集合，由引理 1 可以交换顺序。于是我们得到两条都能到达 $A$ 的后续的路径： \(A + e \;=\; (c_0+s)+e \;=\; (c_0+e)+s \;=\; d_0 + s\) \(A + (e^{\prime},e) \;=\; (c_0+s)+(e^{\prime},e) \;=\; (c_0+(e^{\prime},e))+s \;=\; d_1 + s\)
- 两次利用价：$A + e = d_0 + s$ 说明”从 0-价的 $d_0$ 出发，沿着 $s$ 可以走到一个’已经有人决定 $v$’的配置”，而 $A$ 中那个进程的决定不可撤销，所以 $v$ 是 $d_0$ 可达的决定值 ⇒ $v = 0$。同理 $A+(e^{\prime},e) = d_1 + s$ 说明 $v$ 也是 $d_1$ 可达的决定值 ⇒ $v = 1$。
- $v$ 同时等于 0 和 1 ⇒ 矛盾。
情形 II (p' = p): 故意让 p 全程沉默, 让其余进程必须自己决定 c0 ──s──▶ A (s 有限, 结束时已有进程决定 v; s 中 p 一步不走) │ │ e │ │ e ← e 只作用于 p, s 不含 p => 可交换(引理 1) ▼ ▼ d0 ──s──▶ A + e d0 是 0-价 => d0 能决定的只能是 0 => v = 0 c1 ──e──▶ d1 ──s──▶ A + (e', e) (同理 e' 也与 s 可交换) d1 是 1-价 => d1 能决定的只能是 1 => v = 1 => v 同时是 0 和 1 => 矛盾 => 反设"D 中全是单价配置"不成立 ∎
为什么这个证明如此依赖异步性：情形 I 用到了”事件可交换（消息可被任意延迟而不被察觉）”；情形 II 用到了”$p$ 可以一步都不走”——在异步系统里，”$p$ 的消息还没到”与”$p$ 已经死了”是同一件事，因此对手可以无限期地不给 $p$ 投递消息，同时让其他进程继续跑。如果系统是同步的，对手就不能这么做：超时之后”$p$ 死了”成为公共知识，其他进程可以把它排除掉、按剩下的集合做决定——这就是同步模型下 $f+1$ 轮算法能够成功的原因，也是”绕过 FLP”的第一条路径（部分同步）的起点。
- 关键假设与系统模型：引理 3 依赖 (1) 事件局部性（引理 1）；(2) 共 1 个故障、故障者可选（情形 II 里我们选择让 $p$ 沉默）；(3) 决定不可撤销；(4) 缓冲区语义（消息可以被任意延迟）。
15.2.10 定理：把引理 2 与引理 3 串起来（配置树与无限双价路径）
定理（FLP 不可能性，讲义 Putting it all Together）：
引理 2：存在双价的初始配置。 引理 3：从任何双价配置出发，总能到达另一个双价配置。 定理：因此在异步分布式系统中，总存在一条事件序列（一个执行），使得这组进程永远停留在双价、永远不达成共识。
证明：取引理 2 给出的双价初始配置 $C_0$。反复应用引理 3：得到双价配置序列 $C_0, C_1, C_2, \dots$，其中每个 $C_{k+1}$ 都是从 $C_k$ 出发施加某个有限事件序列后到达的双价配置。把所有这些事件首尾相接，就得到一条无限执行。在这条执行上，每个配置都是双价的，而”双价”意味着”还能走到决定 0、也能走到决定 1”，特别地，这条路径上没有任何进程已经决定（一旦有进程决定 $v$，该配置就只能走到决定 $v$，就不再是双价）。于是这条无限执行上没有任何进程做出决定——终止性被违反。因此不存在同时保证一致性、合法性与终止性的确定性异步共识协议。$\blacksquare$
机制图解（本章最重要的一张图：配置树与无限双价路径）：
配置树 (configuration tree)
根 = 某个初始配置 每个节点 = 一个配置
边 = 一个事件 (e=(p,m)) 每条从根向下的路径 = 一个执行
┌──────────┐
│ 初始配置 │
└────┬─────┘
┌────────────────────┼────────────────────┐
│ │ │
┌───▼───┐ ┌───▼───┐ ┌───▼───┐
│ 0-价 │ │ 双价★ │ │ 1-价 │ ← 引理 2:
└───────┘ └───┬───┘ └───────┘ 必有双价节点
┌─────────────┼─────────────┐
│ │ │
┌───▼───┐ ┌───▼───┐ ┌───▼───┐
│ 0-价 │ │ 双价★ │ │ 1-价 │ ← 引理 3:
└───────┘ └───┬───┘ └───────┘ 双价节点下面
┌─────────────┼─────────────┐ 永远还能找到
│ │ │ 双价子节点
┌───▼───┐ ┌───▼───┐ ┌───▼───┐
│ 1-价 │ │ 双价★ │ │ 0-价 │
└───────┘ └───┬───┘ └───────┘
│
⋮ ← 无限延伸: 对手永远可以选"双价"这一支
│
┌────▼────┐
│ 双价★ │
│ ⋮ │
└─────────┘
★ 存在一条无限长的执行, 途中所有配置都是双价
=> 这条路径上没有任何进程决定过任何值
=> 违反 Termination => 不存在这样的确定性算法 ∎
- 这张图怎么读（三个要点）：
- 树的形状由对手决定：在异步模型里，每个配置的下一个事件（投递哪条消息、给谁）是不确定的，因此一个配置有许多子节点；”执行”就是从根出发的一条路径。
- 单价节点是”死胡同”：到了 0-价节点，不管怎么走都只会决定 0；决定一旦发生，价值就固定。所以”永不决定”的执行必须全程避开单价节点。
- 引理 2 给出起点、引理 3 给出”不断链”的保证，两者合起来就是”存在一条无限的双价路径”。注意这条路径是存在的（existence），不是”所有执行都不终止”——FLP 说的是”总有那么一个最坏的执行”，这也解释了为什么实际系统大部分时候跑得很好：最坏执行需要对手精确配合（恰好延迟正确的那些消息），而真实的网络故障往往是随机的、不一致的。
15.2.11 绕过 FLP：必须放弃某一样东西
定义与目的：FLP 的前提是三条假设的合取：异步 + 确定性 + 允许一个崩溃（且无故障检测器）。因此要”绕过”它，就必须至少放松其中之一。这不是权宜之计，而是逻辑上的必然：所有可用的共识算法都可以被精确地归类为”放松了哪一条”。下表是本讲最重要的一张总结表：
放松/改变的假设 新的系统模型 代表算法/系统 付出的代价 放松”异步” 部分同步（Partially Synchronous）：消息延迟与时钟漂移最终有界，但不知道界何时开始成立 Paxos、Raft、Zab、Viewstamped Replication 在延迟真的无界时算法可能不终止（不保证活性）；但安全性永远成立 放松”确定性” 随机化（每个进程可以抛硬币） Ben-Or（1983）、Rabin 的随机化共识、PBFT 的随机化视图变更 只能保证以概率 1 终止：存在概率为 0 的不终止执行；期望轮数有限（共享硬币 $O(1)$，私有硬币 $O(2^{n-f})$） 放松”无故障检测器” 引入（最终型）故障检测器：$\Diamond P$、$\Diamond S$、$\Diamond W$ Chandra–Toueg 共识（1996） 检测器本身无法在异步丢包网络里被完美实现（Lecture 5/6）：完整性与准确性不能同时保证，因此”最终准确”只能靠超时近似 （补充）改变故障类型 拜占庭故障 + 部分同步 OM(m)、PBFT、Tendermint、HotStuff 副本数从 $f+1$ 升到 $3f+1$，消息复杂度从 $O(N)$ 升到 $O(N^2)$，并需要签名/MAC （对照）不做任何放松 纯异步 + 确定性 + 1 个崩溃 不存在 —— 这就是 FLP - 路径一：放松异步 $\Rightarrow$ 部分同步与”安全性优先”的工程妥协。部分同步模型假设：消息延迟与时钟速率最终会落在某个（未知的）界内，系统可以”好一阵子、坏一阵子”。这正是 Paxos/Raft/Zab 的行为方式：它们用超时来推进（选主、重试），而在超时之前它们什么都不做——宁可等待也不冒险。
- 代价的精确表述：如果网络永远不进入同步期（或者总在最坏的时刻抖动），这些协议可能永远选不出领导者、永远无法提交新的请求——也就是活性（liveness）没有保证。讲义对 Paxos 的原话是：Paxos provides safety and eventual liveness … FLP result still applies: Paxos is not guaranteed to reach Consensus (ever, or within any bounded time)。
- 必须点明的关键权衡：实际共识算法用”安全性永远保证 + 活性尽力而为”换取可行性。这个不对称不是偷懒，而是 15.2.17 要讲的工程哲学。
路径二：放松确定性 $\Rightarrow$ 随机化算法。用随机数打破对称性：如果所有进程都”随机地”选一个新值，那么总有可能（概率大于 0、且独立于历史）在某一步上大家一起选中同一个值，从而跳出 FLP 的无限双价路径。代价是终止性从”必然”降级为”以概率 1”：任何有限轮的失败概率都严格大于 0，但 $\Pr[\text{永不终止}] = 0$，且期望轮数有限。详见 15.3.2 的 Ben-Or。
- 路径三：引入故障检测器。如果系统能提供完美故障检测器 P（强完备：每个崩溃最终被所有正确进程怀疑；强准确：被怀疑的进程确实崩溃了），那么”$p$ 是否已经死了”成为一个可判定的问题，异步模型就等价于同步模型，共识立刻可解。但 Lecture 5/6 已经证明：在丢包网络中不可能同时保证完整性与准确性，否则就能解共识——这本身就是 FLP 的一个推论（若存在完美检测器，用它来”屏蔽”崩溃进程后剩下的系统是同步的）。于是只能退而求其次：
- $\Diamond P$（最终完美）：最终强完备 + 最终强准确；
- $\Diamond S$（最终强）：强完备 + 最终弱准确（最终会有一个正确的进程不被无端怀疑）；
- $\Diamond W$：更弱，用于”多数进程可能故障”的情形。 Chandra–Toueg 定理：$\Diamond S$ 足以解决共识（在多数进程正确的假设下），并且 $\Diamond S$ 是最弱的能解决共识的故障检测器。这就是 15.3.6 的算法基础。Paxos/Raft 实际上内建了 $\Diamond S$ 型的检测器：它们的超时机制就是”最终强烈的怀疑”——超时太短会误判（准确性问题），太长会导致活性差（检测速度问题），工程上必须在两者之间做取舍。
- （补充）路径四：改变故障类型并不”绕过”FLP。一个常见的误解是”拜占庭容错更强，所以更难”，但要注意方向：拜占庭故障是更强的故障假设，它并不让 FLP 消失。在异步系统中，确定性拜占庭共识同样不可能；PBFT/Tendermint/HotStuff 之所以能工作，是因为它们同时采用了部分同步（PBFT 的安全性不依赖同步，活性依赖同步窗口）或随机化视图变更。“更强的容错”与”绕过 FLP”是两件正交的事。
15.2.12 拜占庭故障与拜占庭将军问题
- 定义与目的：拜占庭故障（Byzantine Failure）指故障进程可以任意行为：发送错误的值、对不同接收者发送互相矛盾的消息、伪造/重放消息、伪装成别人、与其他故障进程合谋、干脆不发消息。它得名于 Lamport、Shostak 与 Pease 1982 年的论文 The Byzantine Generals Problem（ACM TOPLAS）：一群拜占庭将军包围了一座城市，必须决定”进攻”还是”撤退”；将军之间只能靠信使通信；其中有些将军是叛徒，会想尽办法让忠诚的将军无法达成一致。
- 为什么这个模型是现实需求：crash-stop 假设”出错的机器只是停下来”，但现实中的出错方式要坏得多——软件 bug 会让副本计算出不同的结果（非确定性、越界、空指针）、磁盘静默损坏（silent data corruption）会让副本读到不同的数据、被入侵的节点会主动作恶、配置错误会让一个节点用旧版本代码运行。这些都不是”停机”，而是”胡说八道”。
- 问题的形式化（两个条件）：
- IC1：所有忠诚的将军决定相同的行动计划（Agreement）；
- IC2：若指挥官是忠诚的，则所有忠诚的将军服从它的命令（Validity/正确性）。
- 消息模型：口头消息（Oral Messages）——消息内容可能被篡改，叛徒可以转述任何它想说的东西（但不能伪造一个忠诚者未曾说过的话，也就是”没有签名”）；书面/签名消息（Signed Messages）——消息带不可伪造的签名，叛徒无法伪造别人的签名，忠诚者可以把”有签名的证据”转发给别人。
- 机制图解（口头消息模型下的两种”耳语”能力）：
口头消息: 叛徒可以 (a) 对不同人说不同的话 (b) 转述时撒谎
┌───────────────────────────────────────────────────────────┐
│ 指挥官 C (叛徒) │
│ ├── 对 p1 说 "进攻" │
│ └── 对 p2 说 "撤退" │
└───────────────────────────────────────────────────────────┘
★ p1、p2 互相转发自己收到的命令后, 各自看到 "一个进攻、一个撤退",
他们无法判断: 是 C 在撒谎? 还是对方在撒谎? ——「不可区分性」再次出现
- 关键假设与系统模型：故障数上界为 $f$；通信图是完全图（每个将军能直接联系每个将军）——这一点很重要，否则连消息传递本身都成问题；同步与异步的差别在拜占庭模型下同样致命：口头消息算法 OM(m) 的正确性依赖同步（每轮消息在有限时间内送达），异步下它无法工作（FLP 的拜占庭版本同样成立）。
15.2.13 核心定理：口头消息下需要 $N \ge 3f+1$
- 定理（Lamport–Shostak–Pease, 1982）：
在口头消息模型下，$N$ 个将军中若有 $f$ 个叛徒，则当且仅当 $N \ge 3f+1$ 时存在同时满足 IC1 与 IC2 的算法。相应地，算法 $OM(m)$ 在 $N > 3m$ 时正确。
- $f=1, N=3$ 为什么不够：三种场景的不可区分性（必考内容）。设指挥官下令值 $\in \{1=\text{进攻}, 0=\text{撤退}\}$，考虑三个”对某个忠诚中尉来说难以区分”的场景：
场景 1: 指挥官忠诚(下令 1); 中尉 p2 是叛徒(对 p1 谎报 0)
┌───────────────┐
│ C 忠诚: 下令 1 │
└───┬───────┬───┘
1 │ │ 1
▼ ▼
┌────────┐ ┌──────────┐
│ p1 忠诚 │ │ p2 叛徒 │
└────────┘ └────┬─────┘
▲ │ 谎报 0
└───────────┘
p1 的视角 = (指挥官说 1, 同伴 p2 说 0)
IC2 要求: p1 必须决定 1 (因为指挥官是忠诚的)
场景 2: 指挥官是叛徒(对 p1 说 1、对 p2 说 0); p1、p2 都忠诚
┌───────────────┐
│ C 叛徒 │
└───┬───────┬───┘
1 │ │ 0 ← 对两个人说不同的话(自相矛盾)
▼ ▼
┌────────┐ ┌────────┐
│ p1 忠诚 │ │ p2 忠诚 │
└───┬────┘ └───┬────┘
│ 1 │ 0 ← 各自如实转述"自己听到的那个值"
└────┬─────┘
▼
p1 的视角 = (指挥官说 1, 同伴 p2 转述 0) = (1, 0) ← 与场景 1 中 p1 的视角【完全相同】
p2 的视角 = (指挥官说 0, 同伴 p1 转述 1) = (0, 1)
IC1 要求: p1 与 p2 必须决定同一个值
场景 3: 指挥官忠诚(下令 0); 中尉 p2 是叛徒(对 p1 谎报 1)
p1 的视角 = (指挥官说 0, 同伴 p2 谎报 1) = (0, 1) ← 与场景 2 中 p2 的视角【完全相同】
IC2 要求: p1 必须决定 0
不可能性的完整推理（三步，务必掌握）：
- 由场景 1 的 IC2：任何算法在视角 $(1,0)$ 上必须输出 1（否则那个忠诚中尉就违背了忠诚指挥官的命令）；
- 由场景 3 的 IC2：任何算法在视角 $(0,1)$ 上必须输出 0；
- 于是在场景 2 中，p1 的视角是 $(1,0)$、p2 的视角是 $(0,1)$，二人必然输出 1 与 0 两个不同的值，违反 IC1。 结论：$N=3, f=1$ 时不存在任何同时满足 IC1 与 IC2 的算法——不是因为算法不够聪明，而是因为三种场景对当事人而言无法区分。这与 FLP 的”引理 2”用的是同一种武器：不可区分性（indistinguishability）。
- $N = 4, f = 1$ 为什么就行：多一个忠诚的将军，就多了一票”真话”，使多数表决能够压过叛徒的谎话。
N=4, f=1: 指挥官忠诚(下令 1); 中尉 p3 是叛徒(对 p1、p2 谎报 0)
┌───────────────┐
│ C 忠诚: 下令 1 │
└──┬────┬────┬──┘
1 │ 1 │ 1 │
▼ ▼ ▼
┌────┐┌────┐┌─────────┐
│ p1 ││ p2 ││ p3 叛徒 │
└─┬──┘└─┬──┘└────┬────┘
│1 │1 │0 0 ← 撒谎
▼ ▼ ▼ ▼
p1 收到的值 = [1 (来自 C), 1 (p2 转述), 0 (p3 撒谎)] => 多数 1 ✔
p2 收到的值 = [1 (来自 C), 1 (p1 转述), 0 (p3 撒谎)] => 多数 1 ✔
=> 3 个忠诚者中只要有 2 个说真话, 就能压过 1 个叛徒 => IC1 & IC2 成立
对比 N=3, f=1 (场景 1):
p1 收到的值 = [1 (来自 C), 0 (p2 撒谎)] => 1:1 平局 => 无法判断 => 失败
- 为什么是 $3f+1$：两层直觉：
- 投票算术（第一层）：多数表决要能过滤谎话，必须让真话严格多于假话，即忠诚者 $N-f$ 要大于叛徒 $f$，给出 $N > 2f$。这解释了下界至少是 $2f+1$。
- 转述链的”影子”（第二层，这才是 $3f$ 的来源）：$OM(m)$ 的递归让每个中尉转述自己听到的值，于是叛徒在每一层都能撒谎。最坏情况下，一个叛徒可以让一组忠诚者相信”指挥官说的是 0”，同时让另一组相信”指挥官说的是 1”——两组人各自看到的世界都自洽，只是相差”一个叛徒的影子”。要防住它，忠诚者必须有能力在两种可能的世界里都占多数：$N-f$ 个忠诚者要同时压过”$f$ 个真叛徒”和”$f$ 个被污染的转述”，即 $N-f > 2f$，也就是 \(\boxed{\,N \ge 3f+1\,}\)
- 必要性：$N \le 3f$ 时，可以把将军们划分成三组（每组不超过 $f$ 个），并构造两个对所有忠诚者”看起来一样”的场景：一个场景里”指挥官忠诚、某一组是叛徒”，另一个场景里”指挥官是叛徒、另一组是叛徒”。两组忠诚者被要求做出不同决定，而他们看到的消息完全相同 ⇒ 矛盾。因此 $N \ge 3f+1$ 既是充分条件也是必要条件。
- 关键假设与系统模型：$OM(m)$ 要求同步（每轮在有限时间内完成）与完全图（任意两人可直接通信）。它同时满足 IC1 与 IC2，消息复杂度却是 $O(N^{f+1})$ 级别（见 15.3.4）——叛徒越多，要交换的”证据”就呈指数爆炸，这正是 PBFT 用三个阶段把复杂度压回 $O(N^2)$ 的动机。
15.2.14 签名消息：用密码学把成本从三倍降到加一
定义与目的：如果消息带不可伪造的签名（unforgeable signature），叛徒就无法伪造别人说过的话，也无法篡改别人发过的内容。于是忠诚的将军可以把”指挥官亲笔签名的命令“当作证据转发给其他将军：一个自相矛盾的指挥官会被当场识破。讲义与论文的结论是：签名消息下 $N \ge f+2$ 即可（即只需要”忠诚者能互相核对证据”，而不是”忠诚者是叛徒的三倍”）。更强的形式化定理甚至允许叛徒数量任意多，只要忠诚将军之间能够通信并验证签名。直观类比：口头消息像”传话游戏”，签名消息像”书面合同”——传话会被歪曲，合同不能。
机制图解（签名如何识破一个自相矛盾的指挥官）：
没有签名(N=3,f=1): 有签名(N=3,f=1):
C 对 p1 说 1, 对 p2 说 0 C 对 p1 签"1"、对 p2 签"0"
│ │
p1 转述"1"给 p2, p2 转述"0"给 p1 p1 把 (1, 签名C) 转发给 p2
│ p2 把 (0, 签名C) 转发给 p1
▼ ▼
p1 看到 [1, 0] 平局 => 无从判断 p1 看到 C 签名的 1 和 0 两份命令
p2 看到 [0, 1] 平局 => 无从判断 => 直接判定「C 是叛徒」=> 回退默认值
(每个将军都可能是叛徒) p2 同理 => 两人一致 ✔
- 重要的范围界定（很多教材讲错的地方）：
- $N \ge f+2$ 是”拜占庭将军问题（同步、口头/书面消息）”这一形式化下的结论；
- 在异步/部分同步的 BFT 共识里，签名并不能把副本数降到 $f+2$：$N \ge 3f+1$ 依然是必需的下界（PBFT、Tendermint、HotStuff 都用 $3f+1$）。原因是异步下还需要quorum 交集来保证安全性（15.2.15），签名只能防伪造，不能提供”何时可以安全推进”的信息。
- 签名的代价是密钥基础设施（PKI）+ 计算开销：签名/验签通常比 MAC 慢几个数量级。因此 PBFT 在副本之间用 MAC（消息认证码）、只在客户端回复等场合用签名，而现代 BFT（HotStuff）则通过门限签名（threshold signature）把 $O(N^2)$ 的消息压缩成 $O(N)$ 的证书。
15.2.15 PBFT：把拜占庭容错做成”可用”的三阶段协议
定义与目的：$OM(m)$ 的指数复杂度使它无法实用。Castro 与 Liskov 在 OSDI 1999 提出的 PBFT（Practical Byzantine Fault Tolerance） 用三阶段（pre-prepare → prepare → commit）+ quorum 证书 + 视图变更把消息复杂度压到 $O(N^2)$，并能在部分同步网络（Internet）上运行。它是第一个”实用”的 BFT 协议，也是所有现代 BFT（Tendermint、HotStuff、Casper、Byzantine Paxos）的共同祖先。
系统模型：$N = 3f+1$ 个副本（replica），最多 $f$ 个拜占庭故障；部分同步（安全性不需要同步假设，活性在同步窗口内保证）；消息可能被篡改但不能伪造签名/MAC；副本通过 view（视图） 编号，每个视图有一个 primary（主副本），其余为 backup。客户端等待 $f+1$ 个不同副本的相同回复才认为请求完成（因为 $f$ 个副本可能撒谎，$f+1$ 个中至少有一个是诚实的）。
机制图解（正常路径的三阶段）：
Client ── request(o, t, c) ──▶ Primary R0
│
┌────────────────────────────────┴─────────────────────────────────┐
│ ① PRE-PREPARE(v, n, D(m)): Primary 广播给所有 backup │
│ (v = 视图号, n = 序号, D(m) = 请求摘要) │
└────────────────────────────────┬─────────────────────────────────┘
┌──────────┬────────────────┼────────────────┬──────────┐
▼ ▼ ▼ ▼ ▼
┌────┐ ┌────┐ ┌────┐ ┌────┐ ┌────┐
│ R1 │ │ R2 │ ... │ Rf │ ... │R3f │ │ R0 │
└─┬──┘ └─┬──┘ └─┬──┘ └─┬──┘ └─┬──┘
│ ② PREPARE(v, n, D(m), i): 每个副本广播给其他所有副本
└─────────┴────────────────┴────────────────┴──────────┘
▼
当副本 i 拥有: 1 条匹配的 PRE-PREPARE + 2f 条匹配的 PREPARE(来自不同 backup, 含自己)
=> 进入 prepared 状态 (这份 2f+1 个副本的"prepared 证书"是安全性的核心)
│
│ ③ COMMIT(v, n, i): 每个副本广播给其他所有副本
▼
当副本 i 收到 2f+1 条匹配的 COMMIT(含自己) => committed-local
=> 执行请求, 把结果直接回复给 Client
│
▼
Client: 收到 f+1 个不同副本的相同回复 => 请求完成 ✔
★ 任意两个 2f+1 的 quorum 至少相交 f+1 个副本, 其中至少 1 个是诚实的
=> 两个冲突的请求不可能都拿到 prepared 证书 => 安全性
视图变更（View Change）：如果 primary 是拜占庭的（例如它故意不给某个请求分配序号、或对不同副本发不同的 pre-prepare），backup 会通过超时发起视图变更：每个副本广播
VIEW-CHANGE(v+1, 最近稳定检查点, 自己持有的 prepared 证书集合)；新 primary 收集 $2f+1$ 条视图变更消息（构成 new-view 证书）后广播NEW-VIEW，其中包含它必须重新提议的请求集合与对应的 PRE-PREPARE。副本验证后进入新视图。这一步就是 PBFT 里”活性被同步假设兜底”的地方：只有超时最终能生效（网络进入同步期）时，视图变更才会成功。关键假设与系统模型与对比：
Paxos / Raft（崩溃容错） PBFT（拜占庭容错） 副本数 $N \ge 2f+1$（多数即可） $N \ge 3f+1$ 故障模型 crash-stop / crash-recovery 任意行为（含撒谎、合谋） 每请求消息数 $O(N)$（Leader 广播 + 多数 ack） $O(N^2)$（每个副本广播给所有副本） quorum $\ge \lfloor N/2\rfloor+1$ $\ge 2f+1$ 客户端确认 1 个回复（Leader 的回复） $f+1$ 个不同副本的相同回复 密码学 通常不需要（可用 MAC/签名） 需要（MAC / 签名 / 门限签名） 同步假设 部分同步（活性） 部分同步（活性） 一句话总结这个对比：容忍更坏的故障，就要付出更多的副本与更多的消息——故障越”坏”（从沉默到撒谎），算法需要的”证据”就越多，因为你不能再相信任何单一消息，只能相信”足够多的独立证人”。
15.2.16 现代 BFT 与区块链：共识的复兴
- 定义与目的：PBFT 之后的二十年里，BFT 协议沿着两条路线演进：降低复杂度与改变”信任来源”。
- Tendermint（2014–2018，Cosmos）：PBFT 的简化变体，用 propose → prevote → precommit 三轮投票 + 锁定（locking） 规则，把”视图变更”融进正常路径；$N=3f+1$，消息 $O(N^2)$。
- HotStuff（2019，Diem/Libra）：用门限签名把 quorum 证书压缩成 $O(1)$ 大小、把通信从”全互连”变成”星型（Leader 收集）”⇒ $O(N)$ 消息复杂度（每次视图），并把视图变更做成”流水线（pipelining）”，成为现代 BFT 的主流骨架（DiemBFT、Aptos、Sui 等）。
- Casper FFG / Ethereum：把 BFT 的”最终性（finality）”机制叠加在 PoS 之上。
- Byzantine Paxos（Lamport, 2011）：把 Paxos 的 acceptor 换成 $3f+1$ 个副本，展示”经典共识 + 拜占庭”的组合。
- 区块链的共识（PoW / PoS）：这是另一条路——不追求”用 quorum 精确地用多数压过少数”，而是用资源（算力）或权益（stake）加上概率安全性来达成一致：PoW 中”最长链”只有在攻击者掌握多数算力时才可能被改写，因此安全性是概率性的（需要等待若干个区块确认）。用经济激励（诚实比作恶更赚钱）+ 概率最终性，替代了 BFT 的”确定性最终性”——代价是吞吐低、延迟高（PoW 的能耗与确认时间），好处是开放网络（无需许可）下的成员管理问题被消解。
- 机制图解（”确定性最终性” vs “概率最终性”）：
BFT 类 (PBFT/Tendermint/HotStuff): 确定性最终性
quorum 证书一旦形成 => 该值【永远】不会被推翻 (安全性是逻辑必然)
代价: 需要固定的成员集合(N=3f+1)、O(N^2) 或 O(N) 消息、对网络同步有依赖
PoW / PoS (Nakamoto 共识): 概率最终性
区块被"确认"k 次 => 被推翻的概率随 k 指数下降 (例如 2^-(k))
代价: 吞吐低、延迟高、能耗/资本门槛; 好处: 开放成员、无需许可
15.2.17 安全性与活性的不对称：分布式系统设计的核心哲学
- 定义与目的：Lecture 13 给出了两条”正确性”的定义：安全性（Safety）= “坏事永远不会发生”（例如：不会有两个进程决定不同的值）；活性（Liveness）= “好事最终会发生”（例如：所有进程最终会决定）。FLP 告诉我们：在异步系统里这两者不可兼得（讲义原话：Consensus: Decisions (Liveness) and correct decisions (Safety) cannot both be guaranteed by any consensus protocol in an asynchronous distributed system）。
工程上如何取舍（本讲最重要的实践结论）：几乎所有真实系统都选择”安全性绝对保证 + 活性尽力而为”。原因是两条性质的失败后果不对称：
违反安全性 违反活性 后果 两个副本决定不同的值 ⇒ 数据损坏、状态分叉、已确认的写入消失 系统暂时无法写入/无法选主 ⇒ 暂时不可用 可恢复性 不可恢复（需要人工介入、可能永久损失数据） 可恢复（网络恢复后自动继续） 用户感知 静默错误，最危险 超时/报错，用户会重试 因此工程上的选择 绝不妥协：宁可不返回，也不返回错误结果 尽力而为：用超时、重试、退避来最大化”最终能推进”的概率 - 这正是 FLP 的”建设性”解读：FLP 不是一句”做不到”的判决，而是一张精确的代价清单： \(\text{异步} \wedge \text{确定性} \wedge \text{总终止} \;\Longrightarrow\; \text{一致性不可保证}\) 因此你要明确地放弃一样东西。Paxos/Raft 放弃的是”总终止”（在极端情况下无限等待 leader）；Ben-Or 放弃的是”确定性与有界时间”（改成概率 1 终止）；ZooKeeper/etcd 的运维手册放弃的是”少数派可用性”（分区时少数派不可写）。没有免费的午餐，但你可以选择买哪一份。
15.3 算法伪代码与正确性分析
本节给出六份算法：同步 Flooding 共识（讲义的同步解法）、Ben-Or 随机化共识（绕过 FLP 的随机化路径）、FLP 双价执行构造（把 15.2 的证明写成可执行的构造性伪代码）、拜占庭口头消息 OM(m)、PBFT 三阶段协议、以及 Chandra–Toueg 的 $\Diamond S$ 故障检测器共识。每份都按”假设与系统模型 → 伪代码 → 逻辑解说 → 正确性论证（安全性/活性/合法性）→ 复杂度”五段展开。
算法 15.3.1：同步系统下的 Flooding 共识
假设与系统模型
- 同步系统：所有进程按 round（轮次）推进，一轮的长度 » 最大消息传输延迟，因此”一轮之内的消息必然全部送达”；有超时机制，能判定”某个进程本轮没发消息”。
- 故障模型：crash-stop，至多 $f$ 个进程崩溃（崩溃后不再发送任何消息）；崩溃发生在轮次边界（最坏情形可建模为”崩溃那一轮只发给部分人”）。
- 通道：可靠、有向、完全图（每个进程能直接发给每个进程）。
- 规模：$N$ 个进程，$f < N$；协议需要知道 $f$（否则不知道该跑几轮）。
- 目标：$f+1$ 轮后，所有正确进程决定同一个值。
伪代码
# 进程 pi 的局部状态
# Values_i : { 提议者 id -> 值 }, 自己目前知道的所有提议 (讲义: Values^r_i)
# prev_i : 上一轮开始时的 Values_i (讲义: Values^{r-1}_i)
初始化:
Values_i <- { (i, v_i) } # 讲义: Values^0_i = {} ; Values^1_i = { v_i }
prev_i <- {}
for r = 1 to f+1 do # 同步轮次; 轮长 >> 最大传输延迟
# ---------- 步骤 1: 多播"上一轮新知道的值" ----------
delta <- { (p,v) in Values_i : p not in prev_i }
for each j != i do
send (VALUES, r, delta) to pj # 讲义: multicast(Values^r_i - Values^{r-1}_i)
# ---------- 步骤 2: 取回本轮消息并合并 ----------
prev_i <- Values_i # Values^r_i 成为下一轮的 Values^{r-1}
for each (VALUES, r, V_j) received from pj do # 同步保证: 本轮的存活者全部到达
for each (p,v) in V_j do
Values_i[p] <- v # 讲义: Values^{r+1}_i = Values^r_i U V_j
# ---------- 步骤 3: 超时/崩溃处理 ----------
if 本轮没有收到 pj 的任何消息 then
mark pj as crashed; continue # 同步模型下"没收到"是可判定的, 直接忽略
end for
# ---------- 决定 ----------
d_i <- v, where (p, v) in Values_i with the smallest proposer id p
decide(d_i)
算法逻辑解说（数值走一遍） 取 $N=3, f=1$，提议值 $p_0=1,\ p_1=0,\ p_2=0$；$p_0$ 在第 1 轮崩溃，且它只把消息发给了 $p_1$（最坏的定向丢失）：
- 第 1 轮：$p_0$ 把 $\{p_0{:}1\}$ 发给 $p_1$（没发给 $p_2$）；$p_1$、$p_2$ 各自把值发给所有人。轮末：$Values_1=\{p_0{:}1,p_1{:}0,p_2{:}0\}$，$Values_2=\{p_1{:}0,p_2{:}0\}$——两人掌握的信息不同。
- 第 2 轮（= $f+1$）：$p_1$ 多播自己的新值 $\{p_0{:}1\}$（这正是”上一步新知道的值”），$p_2$ 多播 $\{p_1{:}0\}$。轮末：两人都变成 $\{p_0{:}1,p_1{:}0,p_2{:}0\}$。
- 决定：两人都取”编号最小的提议者 $p_0$”的值 ⇒ 都决定 1 ✔。
- 如果只跑 $f=1$ 轮：$p_1$ 决定 1、$p_2$ 决定 0 ⇒ 一致性被违反。这就是”少一轮”的代价，也是 15.4.1 代码里实验 2a/2b 的对照。
正确性论证
- Agreement（所有正确进程决定相同的值）——讲义给出的反证法，逐步展开：
- 反设两个正确进程 $p_i$、$p_j$ 在第 $f+1$ 轮结束时的值集合不同，取 $v \in Values_i \setminus Values_j$；
- $p_i$ 必然是在最后一轮（第 $f+1$ 轮）才收到 $v$ 的。否则（若它更早就知道 $v$），根据步骤 1 的规则，它会在它知道 $v$ 之后的第一轮把 $v$ 作为新值多播给所有人，$p_j$ 就会在那一轮收到 $v$；
- 既然 $v$ 是在最后一轮到达 $p_i$ 的，那么在最后一轮里，必定存在第三个进程 $p_k$ 把 $v$ 发给了 $p_i$，却没有发给 $p_j$——即 $p_k$ 在发完 $p_i$ 之后、发给 $p_j$ 之前崩溃了（这是唯一能让两个正确进程在同一轮收到不同消息的原因）；
- 同理，$p_k$ 又必然是在倒数第二轮才从某个进程 $p_{k^{\prime}}$ 那里学到 $v$ 的，而 $p_{k^{\prime}}$ 也在那一轮崩溃了（否则 $p_k$ 与 $p_j$ 都会收到 $v$）；
- 如此上推一轮一轮地推，每一轮都必须有一个不同的进程崩溃（已经崩溃的进程不可能在更早的轮次里发送消息，所以这些崩溃者互不相同），总共需要 $f+1$ 次崩溃；
- 但前提是至多 $f$ 个进程崩溃 ⇒ 矛盾。$\blacksquare$
- Agreement 的推论：既然所有正确进程的最终值集合完全相同，而决定规则（”编号最小的提议者”）是该集合的确定性函数，所有正确进程必然得到同一个决定值 ✔。
- Validity / Integrity（决定值是某个进程提议过的值）：决定值来自 $Values_i$ 中的某个二元组 $(p,v)$，而 $(p,v)$ 一定源于 $p$ 自己的提议或在消息中传播而来的提议，因此必然是某个进程的提议值，不会凭空产生 ✔。另外，若所有进程都提议同一个值 $v$，则所有值集合都只含 $\{v\}$，直接决定 $v$ ✔（讲义口径的 Validity）。
- Termination（每个正确进程最终决定）：同步模型下每轮有固定的时间上界（轮长 > 最大延迟），因此每个正确进程必然完成 $f+1$ 轮并执行 decide；崩溃的进程不需要决定 ✔。注意这条论证依赖于同步假设与”$f$ 已知”——异步模型下”这一轮结束了”无法判定，这正是整个算法失效的地方。
- 前提被破坏时会怎样（重要）：如果实际崩溃数超过 $f$，$f+1$ 轮的归纳链条就不够长，可能出现两个正确进程最后掌握的值集合不同 ⇒ Agreement 失效。15.4.1 的实验 3 给出了 $f_{\text{假设}}=1$ 但实际崩溃 2 个进程时一致性被破坏的完整执行（$p_1$ 决定 1，$p_2$ 决定 0）。
复杂度
- 轮数（时间）：$f+1$ 轮；每轮耗时 $O(\max\text{delay})$ ⇒ 总时间 $O(f \cdot d_{\max})$。
- 消息数：每轮每进程向 $N-1$ 个进程各发 1 条 ⇒ 每轮 $O(N^2)$ 条，总共 $O(N^2 f)$ 条。
- 每条消息的载荷：$\delta$ 最多含 $N$ 个提议值 ⇒ 每轮传输 $O(N^3)$ 个值，总共 $O(N^3 f)$ 个值；若改为直接发全量集合，量级不变。
- 空间：每进程 $O(N)$（保存自己的值集合）+ 每轮 $O(N)$ 的收发缓冲。
- 改进空间：若只需容忍 $f$ 个崩溃且不要求”知道所有值”，可以把”集合”换成”当前最小值 + 计数”，把载荷降到 $O(1)$；但在最坏情况下仍需 $O(N^2 f)$ 条消息。
算法 15.3.2：Ben-Or 随机化共识（绕过 FLP 的路径之二）
假设与系统模型
- 异步消息传递：没有时钟、没有超时；唯一的等待条件是”收到 $n-f$ 条消息”。由于没有时间概念，“消息还没到”与”消息永远不会到”不可区分——这正是 FLP 的温床。
- 故障模型：crash-stop，至多 $f$ 个进程崩溃，且要求 $n \ge 2f+1$（即正确进程严格占多数；拜占庭版本的阈值见本节末）。
- 随机性：每个进程可以使用硬币。两种模型：
- 私有硬币（private coin）：每个进程自己抛，互不相关；
- 共享硬币 / 公共硬币（shared / common coin）：第 $r$ 轮所有进程拿到同一个随机位（可用门限签名或可验证秘密分享 VSS 实现——这本身是一个小型的同步原语，见 15.7 的陷阱说明）。
- 目标：以概率 1 终止的共识（而不是必然终止）——这是 FLP 允许的唯一”出逃口”。
伪代码
# 每个进程 pi 维护: est_i (当前的提议估计, 初值 = 自己的提议值 xi), decided_i (是否已决定)
# 阈值 (见下方推导): D = f+1 (决定阈值) A = 1 (采纳阈值)
for r = 1, 2, 3, ... do # 轮号是局部的, 没有全局轮次概念
# ============ 阶段 1: 提议 (propose) ============
for each j != i do send (EST, r, est_i) to pj
wait until 收到 n-f 条 (EST, r, *) 消息 # 崩溃进程不发消息; 其余"慢消息"被无限延迟
if 收到的 n-f 条 estimate 全部等于同一个值 v then
pref_i <- v # 「一致」才表态
else pref_i <- ⊥ # 不敢表态
# ============ 阶段 2: 投票 + 决定 (vote / decide) ============
for each j != i do send (PREF, r, pref_i) to pj
wait until 收到 n-f 条 (PREF, r, *) 消息
cnt(v) <- |{ 收到的 pref == v }| # 忽略 ⊥
v* <- argmax_v cnt(v) # 得票最多的值
if cnt(v*) >= D then # 门槛 1: 决定
decided_i <- v* ; est_i <- v* ; decide(v*)
else if cnt(v*) >= A then # 门槛 2: 采纳, 固定为下一轮提议
est_i <- v*
else # 门槛 3: 没有任何支持
# ============ 阶段 3: 抛硬币 (coin) ============
if 使用共享硬币 then est_i <- COMMON_COIN(r)
else est_i <- 自己抛一枚硬币
# 这一轮的"先例"就此作废, 用随机性打破对称性
if decided_i then 停止参与 (或只转发自己的决定)
end for
一轮的结构（ASCII 图）
┌───────────────────────────────────────────────────┐
│ 第 r 轮 (每个进程自己数轮号, 没有全局时钟) │
└───────────────────────────────────────────────────┘
┌──────────────────────────────────────────────────────────────────────────┐
│ ① 提议 PROPOSE: 广播 est_i ──▶ 等待收齐 n-f 条 │
│ 收到的 n-f 条全都 = v ? ──是──▶ pref_i = v │
│ └─否──▶ pref_i = ⊥ (不敢表态) │
├──────────────────────────────────────────────────────────────────────────┤
│ ② 投票 VOTE: 广播 pref_i ──▶ 等待收齐 n-f 条 │
│ cnt(v) = 收到的 v 票数 (⊥ 不计) │
│ cnt(v) >= D = f+1 ──是──▶ ★ 决定 v (并 est_i := v) │
│ cnt(v) >= A = 1 ──是──▶ est_i := v (锁定, 下一轮继续提议 v) │
├──────────────────────────────────────────────────────────────────────────┤
│ ③ 抛硬币 COIN: 没有任何值得到支持 ──▶ est_i := 硬币(0/1) │
│ (私有: 各人自己抛 / 共享: 全轮同一个随机位) │
└──────────────────────────────────────────────────────────────────────────┘
│
▼ 进入第 r+1 轮
★ 只要出现"所有正确进程的 est 相同"的局面, 下一轮必然全体决定
概率性终止: 每轮 >= 2^-(n-f) 的概率进入该局面 => 轮数服从(重尾)几何分布
阈值是怎么来的（必须理解，否则只是背参数）：设决定阈值为 $D$、采纳阈值为 $A$，它们要同时满足三条约束：
\[\underbrace{D-f \;\ge\; A}_{\text{传播性：决定必须能被别人看到}}\qquad \underbrace{D \;\le\; n-f}_{\text{可行性：阶段 1 一致时能看到 } n-f \text{ 张票}}\qquad \underbrace{D \ge 1,\ A \ge 1}_{\text{非平凡}}\]- 传播性为什么是 $D-f \ge A$：设正确进程 $p$ 决定 $v$，它在阶段 2 收到 $\ge D$ 张 $v$ 票。任何其他正确进程 $q$ 只收 $n-f$ 条消息，最多漏看 $f$ 条（把最慢的 $f$ 个发送者当成崩溃），因此 $q$ 至少看到 $D-f$ 张 $v$ 票。要让 $q$ 也把 $v$ 固定下来（否则两人的估计会分叉，未来可能决定出不同的值），就必须有 $A \le D-f$。
- 在 $n \ge 2f+1$ 下的最小选择：取 $\boxed{D = f+1,\ A = 1}$。此时 $D = f+1 \le n-f \iff n \ge 2f+1$ ✔，且 $D - f = 1 = A$ ✔。
- 为什么阶段 1 用”一致（unanimity）”而不是”多数（majority）”：这是本算法最容易被忽视的一处设计。若阶段 1 用”严格多数”，那么在实际崩溃数 $c < f$ 时（存活进程多于 $n-f$，各进程看到的子集不同），两个不同的值可能同时各获多数，于是阶段 2 里一个进程会同时看到两个值的票，”该采纳哪一个”变得含糊，传播性论证随之失效；补救办法是把 $A$ 提高到 $A \ge n-D$，而这会要求 $2D \ge n+f$，把可容忍的 $f$ 压到 $f \le 2$（$n$ 为偶数时）。改用”一致”可以严格证明至多一个值能在同一轮获得选票（见下面的不变式 I），从而让 $A=1$ 站得住。这是一个”阈值必须互相匹配”的典型例子：正确性不是来自某个孤立的参数，而是来自一组不等式的联合成立。
算法逻辑解说
- 三个阶段的分工：阶段 1 试探”大家是否已经一致”；阶段 2 把试探结果变成票，票足够多就锁定并决定；阶段 3 只在”什么支持都没有”时启用，用随机性把所有人从”谁都不服谁”的僵局里拉出来。
- 关键点是
⊥的含义：它表示”我这轮不敢表态”，而不是”我反对”。这样设计的好处是：撒谎/模糊不会污染真正一致的候选值，一个值要么被大家共同确认（阶段 1 一致），要么就得不到任何票。 - 执行示例（15.4.2 代码的真实输出，$N=3, f=1$，提议 $[1,0,0]$，$p_1$ 崩溃）：
第1轮: 估计=['0', 'X', '1'] pref=['.', 'X', '.'] 硬币=各自翻转
第2轮: 估计=['0', 'X', '0'] pref=['.', 'X', '.'] 硬币=各自翻转
第3轮: 估计=['0', 'X', '0'] pref=['0', 'X', '0'] 硬币=各自翻转 => 全部决定 0
第 1 轮：$p_0$ 与 $p_2$ 的估计不同 ⇒ 双方都没有”一致”（pref = ⊥）⇒ 没有票 ⇒ 两人各自抛硬币，正好都抛到 0，于是第 2 轮两人估计相同 ⇒ 第 2 轮阶段 1 达成一致 ⇒ 第 3 轮阶段 2 双方都看到 $n-f=2 \ge D=2$ 张 0 票 ⇒ 一并决定 0。这里的决定值 0 来自硬币，但它在二值共识下并不违反合法性：只要硬币真的被用到，就说明两个值都曾被提议过（见下面的合法性论证）。
正确性论证（安全性：与随机性无关，绝对成立）
不变式 I（同一轮至多一个值获得选票）：设 $Z_v$ 为本轮中”在阶段 1 为 $v$ 达成一致”的进程集合。若 $v \ne w$ 都有非空 $Z_v, Z_w$，则 $Z_v \cap Z_w = \emptyset$（一个进程的视角只能一致于一个值）。任一 $z \in Z_v$ 在阶段 1 收到的 $n-f$ 条 estimate 全为 $v$，故发送者中至少有 $n-f$ 个进程的估计是 $v$；同理至少有 $n-f$ 个进程的估计是 $w$。于是发送者总数 $\ge 2(n-f) \ge n+1 > n$，与实际发送者数 $\le n$ 矛盾。因此每轮至多一个值能拿到任何票。$\blacksquare$
Agreement（$y_i = y_j$ 对所有正确进程成立）：
- 由不变式 I，一轮中最多只有一个候选值 $v$ 能获得票。
- （传播） 若正确进程 $p$ 决定 $v$（看到 $\ge D = f+1$ 张 $v$ 票），则任何其他正确进程 $q$ 至多漏看 $f$ 个发送者，故至少看到 $1$ 张 $v$ 票；由 $A = 1$，$q$ 必定把 $est_q$ 固定为 $v$。因此”一个人决定”这个事实会在一轮之内强制传播给所有正确进程。
- （锁定） 若所有正确进程的估计都等于 $v$，则在下一轮阶段 1 中，每个正确进程收到的 $n-f$ 条 estimate 全为 $v$（崩溃进程不发消息）⇒ 全体达成一致 ⇒ 全体 $\text{pref}=v$ ⇒ 阶段 2 每人看到 $n-f \ge f+1 = D$ 张 $v$ 票 ⇒ 全体决定 $v$。
- （不可逆） 一旦所有正确进程的估计被锁在 $v$，任何其他值 $w$ 都不可能再在阶段 1 达成一致（所有人的估计都是 $v$，只有崩溃进程”可能”持有 $w$，而它们不发消息），因此不可能有 $w$ 的票、也就不可能有人决定 $w$。
- 由 1–4：任意两个正确的决定都必然都是 $v$。$\blacksquare$（注意：这条证明没有用到任何概率论，因此 Agreement 是”绝对”成立的——随机化只影响终止性。）
Validity / Integrity：
- 若所有进程提议同一个值 $v$，则第 1 轮阶段 1 全体一致 ⇒ 全体 $\text{pref}=v$ ⇒ 每个进程看到 $n-f \ge f+1$ 张 $v$ 票 ⇒ 第 1 轮就决定 $v$ ✔。
- Integrity（决定值是某个进程提议过的值）：在二值共识下自动成立，理由分两步：
- 硬币只有在”提议出现了分歧”时才可能被用到。若所有正确进程都提议同一个值 $v$（崩溃进程的提议不影响它们是否发言），那么第 1 轮阶段 1 中每个正确进程收到的 $n-f$ 条估计全是 $v$（崩溃者不发消息），全体一致 ⇒ 全体 $\text{pref}=v$ ⇒ 每人看到 $n-f \ge f+1 = D$ 张 $v$ 票 ⇒ 第 1 轮就决定 $v$，根本轮不到硬币。
- 既然如此，只要某轮真的抛了硬币，就说明两个值都曾（由正确的进程）被提议过，硬币无论取 0 还是 1 都落在”被提议过的值”里 ⇒ 决定值必然合法 ✔。 （注意：这条便利只属于二值共识。多值共识下硬币可能给出一个没人提议过的值，必须把硬币的取值范围限制在”已被提议的值集合”内——这是随机化共识实现中一个真实的 bug 来源。）
Termination 以概率 1 成立（活性分析）：
- 定义”收敛事件“：某一轮结束时，所有正确进程的估计相同。
- 情形 (a)：本轮没有任何进程在阶段 1 达成一致 ⇒ 所有正确进程都 $\text{pref}=\bot$ ⇒ 全部走硬币分支。若所有硬币取值相同（概率 $2 \cdot 2^{-(n-f)} = 2^{-(n-f)+1}$，私有硬币）则收敛；若使用共享硬币，则这一情形必然收敛。
- 情形 (b)：某些进程为 $v$ 达成一致、其余为 $\bot$ ⇒ 前者估计为 $v$，后者取硬币。若所有硬币取值都等于 $v$（概率 $2^{-(n-f)}$）则收敛；若不然，下一轮估计是”$v$ 与 $\lnot v$ 的混合”，于是没有任何子集能达成一致 ⇒ 退化成情形 (a)，再一轮即可用共享硬币收敛。
- 因此每一轮至少以 $p = 2^{-(n-f)}$ 的概率进入”全体估计相同”的状态，而一旦进入该状态，下一轮必定全体决定（见 Agreement 第 3 条）。由于各轮硬币独立，决定所需轮数被参数为 $p$ 的几何分布随机占优： \(\mathbb{E}[\text{轮数}] \;\le\; \frac{1}{p} \;=\; 2^{\,n-f},\qquad \Pr[\text{永不终止}] \;=\; \lim_{k \to \infty}(1-p)^k \;=\; 0\) ⇒ 以概率 1 终止，且并非”某一轮之后必然终止”——任何有限轮之后都还残留 $(1-p)^k > 0$ 的不终止概率。这正是 FLP 的”最坏执行”在随机化算法里的化身。$\blacksquare$
- 共享硬币的威力（实验结论）：若每轮所有进程拿到同一个随机位，(a) 情形必然收敛、(b) 情形只需最多两轮 ⇒ 期望 $O(1)$ 轮。所以”私有硬币 vs 共享硬币”的差别不是常数因子，而是 $2^{\Theta(n)}$ 与 $O(1)$ 的差别：15.4.2 的实验里 $N=7, f=2$ 时私有硬币平均 14.77 轮、最长 79 轮（重尾），共享硬币平均 1.93 轮、最长 2 轮。
复杂度
- 消息：每轮 2 个阶段 × $n$ 个进程各广播 $n-1$ 条 ⇒ $O(n^2)$ 条/轮（可用”只发给 $n-f$ 个进程再加转发”优化到 $O(n \cdot f)$，但复杂度量级仍是二次）。
- 轮数：私有硬币期望 $O(2^{n-f})$、最坏无界；共享硬币期望 $O(1)$、最坏无界（这正是 FLP 的印记）。
- 空间：每进程 $O(n)$（保存本轮收到的估计/票）。
- 通信量随规模：$O(n^2)$ 每轮 × 期望轮数 —— 私有硬币下随规模指数爆炸，因此只在 $n$ 很小时实用；共享硬币则给出实用的 $O(n^2)$。
- 拜占庭版本：把阈值换成 $A = f+1$、$D = 2f+1$，并要求 $n \ge 3f+1$（此时 $D \le n-f$ ✔，传播性 $D - f = f+1 = A$ ✔）。
算法 15.3.3：FLP 双价执行构造（把证明写成可执行的构造）
假设与系统模型
- 异步消息传递；确定性协议 $P$（可把它看成一个纯函数：配置 × 事件 → 配置）；故障模型为”至多一个进程崩溃，且崩溃者由构造者选择“；网络 = 全局消息缓冲区，投递时机由构造者控制。
- 这不是一个”运行在真实系统上的协议”，而是一段分析性伪代码（analytical pseudocode）：它是 FLP 定理的构造性证明，同时也是”对手如何逼出一个不终止执行”的算法说明。
伪代码
构造 (对手视角): 输入 = 确定性共识协议 P, 进程数 N, f = 1
输出: 一条无限执行, 使所有进程永不决定
# ---- 准备: 由引理 2 得到一个双价的初始配置 ----
C <- 由引理 2 的存在性论证给出的双价初始配置
choose p_faulty <- "输入翻转导致跳变的那一个进程" # 破产的候选: 引理 2 中的 p
mark p_faulty as crashed # p_faulty 从此不再执行任何事件
# ---- 主循环: 每一步都保持在"双价"上 ----
loop forever:
E <- { 所有当前可应用于 C 的事件 } # 缓冲区里所有消息的投递 (以及 null 事件)
found <- false
for each e in E do # 尝试每一个事件, 找一个"保持双价"的
if 从 (C + e) 出发仍可到达"决定 0"的执行
and 从 (C + e) 出发仍可到达"决定 1"的执行 then
C <- C + e # 引理 3 保证这样的 e 一定存在
deliver(e) # 真的把这条消息投递给它的接收者
found <- true
break
if not found then
# 引理 3 断言这永远不会发生: D = e(C) 中必有双价配置
abort "与引理 3 矛盾"
# ---- 结果 ----
# 循环永不退出; 途中每个配置 C 都是双价
# => 这条执行上没有任何进程决定过任何值
# => 违反 Termination
# => 不存在同时满足 Agreement + Validity + Termination 的确定性异步协议 ∎
算法逻辑解说
- 伪代码里的关键是那个 for 循环：它枚举”当前缓冲区里可投递的消息”，并故意挑选那些’投递之后仍然双价’的消息。这对应 FLP 引理 3 中”总存在一个事件 $e$ 使得 $D=e(\mathcal{C})$ 里还有双价配置”的断言。
deliver(e)就是真实的”把消息投递出去”：构造出的执行是合法的——它遵守异步模型（消息可以任意延迟，因此”投递哪条、什么时候投递”完全合法），且只有一个进程崩溃。- 注意
found永远不会是 false：这正是引理 3 的内容；换言之，”永远留在双价分支上”是结构性的，不是运气。
正确性论证（构造的正确性 = FLP 定理的证明）
- 引理 2（起点存在）：见 15.2.8。给出双价初始配置 $C_0$，并确认”翻转输入的那一个进程”可以作为那个唯一的崩溃者。
- 引理 3（可无限延伸）：见 15.2.9。它保证每轮迭代都能找到保持双价的事件 $e$，分”$p^{\prime} \ne p$（用引理 1 交换性）”与”$p^{\prime} = p$（用’$p$ 全程沉默的有限已决定执行’）”两种情形证明。
- 不变式：主循环的每一步之后，$C$ 都是双价配置。
- 结论：由不变式，$C$ 是双价的含义是”从 $C$ 出发还能走到决定 0、也能走到决定 1”，特别地，这条执行上没有任何进程已经决定过任何值（一旦有人决定 $v$，该配置就只能走到 $v$，与双价矛盾）。于是这条无限执行永远不决定——终止性被违反，定理得证。$\blacksquare$
复杂度：不存在（这是一个不终止的构造）；有意义的是它的信息论含义：对手只需控制”消息投递顺序”这一件事，就能让任意确定性协议失效——不需要伪造消息、不需要超过一个故障。
算法 15.3.4：拜占庭口头消息算法 OM(m)
假设与系统模型
- 同步系统（每一轮的递归调用都在有限时间内完成，收不到即视为默认值）。
- 拜占庭故障：至多 $m$ 个叛徒；口头消息（叛徒可以撒谎与矛盾，但不能伪造忠诚者说过的话）；完全图。
- 值域 $\{1=\text{ATTACK}, 0=\text{RETREAT}\}$，默认值为 RETREAT（Lamport 等的约定：拿不定主意就撤退）。
- 目标：IC1（所有忠诚将军决定相同的值）与 IC2（指挥官忠诚时，忠诚将军服从它）。
伪代码
majority(v1, ..., v_{n-1}) : # 多数函数, 平局取默认值
if 存在值 v 出现次数 > (n-1)/2 then return v
else return DEFAULT (RETREAT)
OM(0) —— 指挥官 c 直接把值发给每个中尉:
c 把值 v 发给每个中尉
每个中尉 i: v_i <- 收到的值 (若 c 叛变, v_i 可能是任意值; 收不到则 DEFAULT)
return (v_i 为中尉 i 的决定)
OM(m) —— m > 0, 指挥官 c, 中尉集合 L = { l_1, ..., l_{n-1} }:
步骤 1: c 把值 v 发给每个 l in L # c 是叛徒时, 可以对不同人发不同的值
步骤 2: for each l in L:
v_l <- 步骤 1 中 l 收到的值 (收不到 => DEFAULT)
l 作为指挥官, 对 L \ {l} 中的每个 l' 执行 OM(m-1), 发送值 v_l
# 即: l' 会从"l 主持的 OM(m-1)"中拿到一个值 (记作 从 l' 视角看到的 v_l)
步骤 3: for each l in L:
values_l <- { v_l } U { 步骤 2 中 l 从其他中尉 l' 那里得到的值 }
decide_l <- majority(values_l) # 注意 values_l 有 n-1 项
return (decide_l 为中尉 l 的决定)
算法逻辑解说（$N=4, f=1$ 走一遍）
- 指挥官 $C$ 忠诚，下令 ATTACK（1）；中尉 $p_3$ 是叛徒。
- 步骤 1：$C$ 对三个中尉都说 1 ⇒ $v_{p_1}=v_{p_2}=v_{p_3}=1$。
- 步骤 2：每个中尉作为指挥官执行 $OM(0)$：$p_1$ 对 $p_2,p_3$ 说 1；$p_2$ 对 $p_1,p_3$ 说 1；$p_3$（叛徒）对 $p_1,p_2$ 说 0。
- 步骤 3：$p_1$ 的 $values=[1(\text{来自 }C), 1(p_2), 0(p_3)]$ ⇒ 多数 1 ⇒ 决定 ATTACK ✔；$p_2$ 同理决定 ATTACK ✔。IC1、IC2 同时成立。
- 对照 $N=3, f=1$（同样的场景）：$p_1$ 的 $values=[1(\text{来自 }C), 0(p_2)]$ ⇒ 1:1 平局 ⇒ 默认 RETREAT ⇒ 违反 IC2。多出来的那一个忠诚中尉就是”打破平局”的那一票。
正确性论证
- 归纳的骨架（先记住这条统一的计数引理）：$OM(m)$ 的证明对 $m$ 归纳（基础 $m=0$：不存在叛徒，故指挥官必然是忠诚的，$OM(0)$ 显然满足 IC1/IC2）。归纳步中，每个忠诚中尉的决定都是一次对 $n-1$ 个值的多数表决，而这 $n-1$ 个值可分成两部分：
- 共同部分：来自忠诚中尉主持的子协议（以及自己从忠诚指挥官那里收到的值）。由归纳假设（$OM(m-1)$ 满足 IC1/IC2），对所有忠诚中尉来说这一部分完全相同，其大小 $\ge n-1-m$；
- 可变部分：来自至多 $m$ 个”可能撒谎”的条目（$\le m-1$ 个叛徒中尉转述的值 + 自己从叛徒指挥官那里听来的值），其大小 $\le m$。 由于 $n > 3m \Rightarrow n > 2m+1 \Rightarrow n-1-m > m$，共同部分本身就构成严格多数，多数表决的结果只由共同部分决定 ⇒ 所有忠诚中尉得到同一个多数值（任何”杂音票”都不足 $(n-1)/2$ 张，改变不了结论）。下面两种情形只是这条引理的两个应用：
- IC2（指挥官忠诚）：忠诚的指挥官把 $v$ 发给所有中尉，每个忠诚中尉的 $v_l = v$。在步骤 2 中，每个忠诚中尉 $l$ 用它拿到的正确值 $v$ 主持 $OM(m-1)$；由归纳假设（$l$ 是该子协议的忠诚指挥官，适用 IC2），每个忠诚中尉 $l^{\prime}$ 从 $l$ 的子协议里得到的值都是 $v$ ⇒ 共同部分全部是 $v$，且大小 $\ge n-1-m > m \ge$ 可变部分 ⇒ $majority$ 返回 $v$ ⇒ 所有忠诚中尉决定 $v$ ✔。
- IC1（所有忠诚者一致）：若指挥官忠诚，直接由 IC2 得一致 ✔。若指挥官是叛徒，则叛徒中尉至多 $m-1$ 个：对每个忠诚中尉 $j$（在它自己主持的 $OM(m-1)$ 里它是忠诚指挥官），由归纳假设的 IC2 可知，任何忠诚中尉 $i$ 从 $j$ 那里得到的值都恰好是 $v_j$——对所有忠诚的 $i$ 而言都是同一个 $v_j$，这正构成上面的”共同部分”；因此所有忠诚中尉的多数表决都由共同部分决定 ⇒ 他们得到相同的决定值 ✔。$\blacksquare$
- IC2 的必要性（$N \le 3f$ 时的失败）：见 15.2.13 的三种场景——场景 1 与场景 3 迫使算法在视角 $(1,0)$、$(0,1)$ 上分别输出 1 和 0；于是在场景 2（指挥官叛徒、两名中尉忠实）中两个人必然输出不同的值，违反 IC1。因此 $N \ge 3f+1$ 既是充分也是必要条件。$\blacksquare$
复杂度
- 消息数：$T(0) = n-1$，$T(m) = (n-1) + (n-1)\cdot T(m-1)$ ⇒ \(T(m) \;=\; \sum_{k=1}^{m+1}\frac{(n-1)!}{(n-k-1)!} \;=\; O\!\left(n^{\,m+1}\right)\) 即对叛徒数 $m$ 呈指数级（$m=f$ 时约 $O(n^{f+1})$）。这就是 $OM(m)$ 不能实用的原因，也是 PBFT 用三阶段 quorum 把复杂度压回 $O(n^2)$ 的动机。
- 轮数（时间）：$m+1$ 轮消息往返（递归深度 $m+1$）。
- 空间：每个将军保存 $O(n^m)$ 级别的”转述历史”（因为要记住谁转述了什么）。
算法 15.3.5：PBFT 的三阶段协议与视图变更
假设与系统模型
- $N = 3f+1$ 个副本，至多 $f$ 个拜占庭故障；部分同步（安全性不依赖同步，活性依赖最终同步）；
- 消息通道可靠（可能延迟、重排，但不会丢失/篡改）；副本之间的消息用 MAC（共享密钥）或签名保护；
- 副本按 view（视图） 编号 $v$，主副本 $\text{primary} = v \bmod N$；序号 $n$ 唯一标识每个请求的提交位置；$D(m)$ 是请求 $m$ 的摘要（digest）；
- 客户端：发送请求后等待 $f+1$ 个不同副本的相同回复才算完成。
伪代码
# 副本 i 的局部状态: v(视图号), n(序号), log, prepared 证书集合, committed 集合
# 常量: f = (N-1)/3 ; QUORUM = 2f+1
---------------- 正常路径 (primary = p) ----------------
upon 收到 client 的 request m at primary p:
分配序号 n (单调递增), 广播 PRE-PREPARE(v, n, D(m)) 给所有副本
# 注: PBFT 要求"同一 (v,n) 上只接受一个摘要", 否则视为主副本作恶
upon 副本 i 收到 PRE-PREPARE(v, n, d) from primary:
if 摘要校验通过 and 未在 (v,n) 上接受过别的摘要 then
记录该 pre-prepare; 广播 PREPARE(v, n, d, i) 给所有副本
upon 副本 i 收到 PREPARE(v, n, d, j) from 副本 j:
记录; if 已收集到 { PRE-PREPARE(v,n,d) } U { 2f 条来自不同副本的 PREPARE(v,n,d,*) }
then 进入 prepared(v, n, d) 状态; 广播 COMMIT(v, n, i) 给所有副本
# 「prepared 证书」= 1 条 pre-prepare + 2f 条 prepare = 2f+1 个副本的共同确认
upon 副本 i 收到 COMMIT(v, n, j) from 副本 j:
记录; if 收到 2f+1 条来自不同副本的 COMMIT(v, n, *) (含自己)
then 进入 committed-local(v, n) 状态
等待所有 n' < n 的请求都已执行 (保序) 后执行 m
把结果 reply 直接发给 client
upon client 收到 f+1 个不同副本对同一 (n, 结果) 的相同 reply:
请求完成 ✔ # f 个副本可能撒谎, 因此需要 f+1 个一致回复(其中至少 1 个诚实)
---------------- 视图变更 (primary 疑似故障) ----------------
upon 副本 i 超时 (primary 在同步窗口内没有推进):
广播 VIEW-CHANGE(v+1, 最近稳定检查点, 自己持有的所有 prepared 证书)
upon 新 primary p' = (v+1) mod N 收到 2f+1 条 VIEW-CHANGE:
构造 NEW-VIEW(v+1, V, O):
V = 这 2f+1 条视图变更消息 (作为"新视图证书")
O = 需要重新提议的请求集合 (由 V 中最新/最高的检查点与 prepared 证书决定)
广播 NEW-VIEW(v+1, V, O); 对 O 中每个请求重新广播 PRE-PREPARE
upon 副本 i 收到合法的 NEW-VIEW(v+1, V, O):
验证 V 的签名/摘要一致, 按 O 重新执行 prepare/commit 流程; 进入视图 v+1
把已 prepared 但未 committed 的请求继续走完 => 活性恢复
算法逻辑解说
- 三阶段各解决一个问题：PRE-PREPARE 定序（把请求绑定到唯一的 $(v,n)$）、PREPARE 确认”整个集群都看到了同样的定序”（防止主副本对不同副本说不同的话）、COMMIT 确认”足够多的副本已经准备好执行它”（防止视图切换时的”旧请求丢失/重复执行”）。
- 为什么是 $2f+1$：任何两个 $2f+1$ 的 quorum 至少相交 $(2f+1)+(2f+1)-(3f+1) = f+1$ 个副本，其中至少有一个是忠诚的，于是”同一序号上出现过两个不同摘要”这件事会被这个忠诚副本发现并拒绝 ⇒ 安全性。
- 为什么客户端要等 $f+1$ 个回复：$f$ 个副本可能是叛徒并合谋返回错误结果，$f+1$ 个一致回复里至少有一个来自忠诚副本，而忠诚副本只会返回它真正执行过的结果 ⇒ 客户端不会被骗。
- 执行顺序：PBFT 是复制状态机（课程 Lecture 19/22），因此必须”按序号顺序执行”，这要求低序号请求的缺失会阻塞高序号请求（可用 checkpoint + 状态转移补齐）。
正确性论证
- 安全性（Agreement，不依赖同步假设）：
- 同一 $(v,n)$ 上不可能有两个不同的请求都进入 prepared 状态：进入 prepared 需要 $2f+1$ 个副本的 PREPARE（或 pre-prepare + 2f 个 PREPARE），两个不同的摘要各需要一个 $2f+1$ 的 quorum，二者相交 $f+1$ 个副本、其中至少一个忠诚，而忠诚副本在同一 $(v,n)$ 上只会接受一个摘要 ⇒ 矛盾。（主副本作恶试图”双重分配”会被 quorum 交集挡住。）
- 跨视图不冲突：视图变更时，新主副本必须提交 $2f+1$ 条视图变更消息（同样是一个 quorum），因此至少有一个忠诚副本的 prepared 证书被包含进来，任何”已经 prepared 的请求”都会被重新提议，不会被丢弃、也不会被替换成别的请求 ⇒ 已经 committed 的请求在所有副本上的执行结果不变。
- 客户端不会看到两个冲突的结果：它要求 $f+1$ 个一致的回复，而其中至少一个是忠诚副本的真实执行结果 ⇒ 两个不同的结果不可能都拿到 $f+1$ 个一致回复。
- 活性（Liveness）：在最终同步的窗口内，超时能够正确触发视图变更；由于 $N = 3f+1$ 且主副本轮转，最终会出现一个忠诚的主副本，它诚实定序、能收集到 quorum ⇒ 请求最终被提交并执行。注意：如果网络永远不进入同步期，PBFT 也可能永远卡在”不断视图变更”里——这正是 FLP 允许的那种”不终止”，而安全性始终未破。
- Validity / 正确性：副本只执行客户端真正提交的请求；摘要校验使得被篡改的请求无法进入 prepared 状态；执行结果由副本真实的状态机计算得出 ⇒ 结果来源于真实请求 ✔。
复杂度
- 消息复杂度：正常路径每请求 $O(N^2)$ 条消息（pre-prepare 广播 1 轮、prepare 与 commit 各 $N$ 个副本广播给 $N-1$ 个副本），视图变更为 $O(N^2)$（每副本广播一次视图变更 + 新主广播 NEW-VIEW）。
- 时间：正常路径 3 个阶段 ≈ 3 个 RTT（再加客户端确认）；视图变更额外 2 个 RTT 量级。
- 密码学开销：$O(N^2)$ 次 MAC 校验（或签名校验）；用门限签名可以把证书压缩到 $O(1)$，使 HotStuff 一类协议达到 $O(N)$ 消息/视图。
- 规模瓶颈：$N = 3f+1$ 意味着每容忍 1 个拜占庭节点就要 3 个副本；$O(N^2)$ 使 PBFT 在 $N$ 超过几十时就不实用（这也是区块链采用”委员会抽样”来缩小 $N$ 的原因）。
算法 15.3.6：Chandra–Toueg 的 $\Diamond S$ 故障检测器共识（绕过 FLP 的路径之三）
假设与系统模型
- 异步消息传递，但系统提供故障检测器 $\Diamond S$：强完备性（每个崩溃的进程最终被所有正确进程怀疑）+ 最终弱准确性（存在某个正确进程，最终不再被任何正确进程怀疑）。
- 故障模型：crash-stop，多数进程正确（$n \ge 2f+1$）。
- 算法结构：轮转协调者（rotating coordinator） + 两轮消息。
伪代码
# 每个进程 pi: est_i (估计值), r (当前轮号, 从 1 开始), decided
# 常量: n, f, QUORUM = n - f
for r = 1, 2, 3, ...:
c <- ((r - 1) mod n) + 1 # 第 r 轮的协调者 (轮流当值)
# ---------- 阶段 1: 所有人把估计报给协调者 ----------
for each j != i do send (EST, r, est_i) to pj
if i == c then
wait until 收到 n-f 条 (EST, r, *) 消息 # 用 ◇S 判断谁已经崩溃, 不再等它
v <- 收到的消息中"最新"的那个值 # 选择规则可任意(如按到达顺序取最后一条)
for each j != c do send (COORD, r, v) to pj # 协调者广播自己选定的值
# ---------- 阶段 2: 采纳协调者的值并回执 ----------
wait until 收到 (COORD, r, v) from pc, 或 ◇S 判定 pc 已崩溃
if 收到 (COORD, r, v) then
est_i <- v ; send (ACK, r, i) to pc
else
est_i <- ⊥ # 协调者不可用, 本轮作废
# ---------- 阶段 3: 协调者宣布决定 ----------
if i == c then
wait until 收到 n-f 条 (ACK, r, *) 消息
decide(v) ; for each j do send (DECIDE, r, v) to pj
upon 收到 (DECIDE, r, v) from pc:
est_i <- v ; decide(v)
# 某个进程在本轮决定后, 广播 (DECIDE) 让所有人一起决定(可靠广播)
算法逻辑解说
- “轮转协调者”是活性的关键：即使当前协调者崩溃或不可用，下一轮换一个人来当，$\Diamond S$ 最终会停止怀疑某个正确的进程 $c^$；当轮次轮到 $c^$ 且它收集到 $n-f$ 个 ACK 时，决定就发生了。
- “$n-f$ 个”而不是”$n$ 个”：这正是”不等待已崩溃进程”的体现——异步系统里我们分不清”慢”与”死”，但 $\Diamond S$ 的最终弱准确性保证了最终有一个正确的进程不会被无端怀疑，于是所有正确进程都能凑齐 $n-f$ 条、不会永远阻塞。
- 一个具体节奏：$n=3, f=1$，若第 1 轮协调者 $p_1$ 崩溃，则第 1 轮无果（所有正确进程 $\text{est}=\bot$）；第 2 轮协调者 $p_2$ 正常，收集到 2 个 EST（含 $p_3$），广播值，收到 2 个 ACK ⇒ 决定 ✔。
正确性论证
- Agreement：设 $p_i$ 在第 $r$ 轮决定 $v$、$p_j$ 在第 $r^{\prime} \ge r$ 轮决定 $w$。
- 若 $r^{\prime} = r$：两者看到的是同一轮协调者广播的同一个 $v$，且都要求 $n-f$ 个 ACK/EST；同一轮只有一个协调者、只广播一个值 ⇒ $v = w$ ✔。
- 若 $r^{\prime} > r$：关键引理是”如果某个正确进程在第 $r$ 轮决定 $v$，那么到了第 $r+1$ 轮，所有正确进程的估计都已经是 $v$（或者它们的估计不足以选出别的值）“。理由：$p_i$ 决定 $v$ 说明至少 $n-2f \ge 1$ 个正确进程收到了 $v$ 并把它当作自己的估计（$n-f$ 个 ACK 中至多 $f$ 个来自崩溃/故障者），而这些正确进程在后续各轮向协调者报告的估计都是 $v$；任何后续协调者收集 $n-f$ 个 EST 时，其中至少 $n-2f$ 个来自正确进程……严格论证需要对”协调者选择最新值”的规则做归纳（Chandra–Toueg 原文用”$v$ 会一直存活到被决定”的不变式），这里给出结论：由于固定的 $n-f$ 与 $f$ 的算术关系（$n \ge 2f+1$），一个已经由某个正确进程决定的 $v$ 无法被后续协调者”洗掉” ⇒ $w = v$ ✔。
- Validity：决定值一定来自某轮的 EST 消息，即某个进程的估计；而估计的初值是提议值，之后只会被”采纳某个已由协调者广播的值”覆盖——归纳可知决定值必然是某个进程提议过的值 ✔。
- Termination（在 $\Diamond S$ 的最终保证下）：设 $t$ 时刻之后 $\Diamond S$ 满足弱准确性，且存在正确进程 $c^$ 不再被怀疑；因为协调者轮转，$c^$ 最终会成为协调者；届时它收齐 $n-f$ 个 EST（坏消息被 $\Diamond S$ 排除/超时不再等待）、广播值、收齐 $n-f$ 个 ACK ⇒ 决定，并通过可靠广播让所有正确进程一起决定 ✔。注意这个”最终”是 $\Diamond S$ 提供的额外假设——正是它替换掉了 FLP 中被禁止的那个假设（”能区分慢与死”）。
- 与 FLP 的关系（必须点明）：FLP 说”没有故障检测器时不可能”。$\Diamond S$ 是一个比完美检测器弱、但比”什么都没有”强的额外假设。Lecture 5/6 已经告诉我们：在丢包网络里不可能同时保证完整性与准确性——所以 $\Diamond S$ 在真实系统中只能用”最终超时”近似实现，而超时的选取又回到”活性 vs 准确性”的取舍上。共识不可能被”免费”解决，只能被”收费”解决：费用就是你愿意相信的额外假设。
- Chandra–Toueg 定理：$\Diamond S$ 是最弱的、在多数进程正确时足以解决共识的故障检测器；若允许多数进程故障，则需要 $\Diamond W$。Paxos/Raft 里的超时机制本质上就是 $\Diamond S$ 的一个工程实现：领导者等待多数派响应，超时就”怀疑”并重新选举。
15.4 代码示例与分布式实现
本节给出三个只用 Python 标准库、固定随机种子、可直接 python3 运行的模拟器，分别验证本章三种核心机制：同步模型下的 $f+1$ 轮 Flooding 共识、异步随机化的 Ben-Or 共识、以及拜占庭将军的口头消息与签名消息算法。
仿真约定（三个程序通用）：
- 用”轮次制 + 显式消息投递控制“来模拟分布式环境：每个进程维护自己的局部状态，消息通过一个”投递函数”送达（可以指定”某人崩溃后不再发送”或”某一轮只发给部分人”），没有任何共享内存；
- 崩溃模型是”故障即静默”：崩溃进程不再发送任何消息，这与真实 crash-stop 行为一致（对手可以让它”恰好在对某个人撒谎/漏发之后就死”）；
- 随机性一律用
random.Random(seed)固定，输出可复现； - 每个程序都自带断言式校验（Agreement / Validity / IC1 / IC2），把”理论判决”变成”可见的通过/失败”。
15.4.1 同步 Flooding 共识模拟器
#!/usr/bin/env python3
"""
同步系统下的 Flooding 共识模拟器 (CS 425 Lecture 15 = 课程 Lecture 17)
系统模型
* 同步系统: 所有进程按 round 同步推进, 一轮内消息必然送达 (round 长度 >> 最大传输延迟)
* 故障模型: fail-stop (crash-stop); 崩溃进程从此不再发送
* 通道可靠; 额外支持 "崩溃那一轮只把消息发给了部分人" 的定向丢失(用来演示假设被突破)
算法 (讲义 Consensus in Synchronous System)
Values^0_i = {}; Values^1_i = {v_i}
for round = 1 .. f+1:
multicast(Values^round_i - Values^{round-1}_i) # 只发"上一轮新知道"的值
Values^{round+1}_i = Values^round_i
for each Vj received: Values^{round+1}_i |= Vj
decide = 取"编号最小的提议者"的值 (consistent minimum based on id, 而非最小数值)
"""
import random
def simulate(N, proposals, alive_until, partial_drop, rounds, verbose=True):
"""
N : 进程数
proposals[i] : 进程 i 的初始提议值 (0/1)
alive_until[i] : 进程 i 参与发送的最后一轮; None = 全程存活
partial_drop : {(i, r): {接收者}} 进程 i 在它崩溃的那一轮 r 只发给这些接收者
rounds : 实际执行轮数
返回 (decisions, known) ; decisions[i] in {0,1,"CRASHED"}
"""
known = [dict() for _ in range(N)] # Values^r_i : {提议者 -> 值}
prev = [dict() for _ in range(N)] # Values^{r-1}_i
for i in range(N):
known[i][i] = proposals[i]
def crashed(i, r): # 第 r 轮是否已经不再发送
return alive_until[i] is not None and r > alive_until[i]
for r in range(1, rounds + 1):
# ---- 步骤 1: 每个存活进程多播"上一轮新知道的值" ----
inbox = [[] for _ in range(N)]
for i in range(N):
if crashed(i, r):
continue
delta = {p: v for p, v in known[i].items() if p not in prev[i]}
targets = list(range(N))
if alive_until[i] == r and (i, r) in partial_drop:
targets = sorted(partial_drop[(i, r)]) # 崩溃前只发给了这几个人
for j in targets:
if j != i:
inbox[j].append((i, delta))
# ---- 步骤 2: 每个进程把收到的集合并入自己的 Values ----
for j in range(N):
if crashed(j, r):
continue
prev[j] = dict(known[j])
for (_sender, delta) in inbox[j]:
for p, v in delta.items():
known[j].setdefault(p, v)
if verbose:
cells = []
for i in range(N):
if crashed(i, r):
cells.append(f"p{i}=崩溃 ")
else:
ids = "".join(str(p) for p in sorted(known[i]))
cells.append(f"p{i}:{{{ids}}}")
print(f" 第 {r} 轮末 值集合(按提议者 id) " + " ".join(cells))
# ---- 步骤 3: 决定: 取自己知道的、编号最小的提议者的值 ----
decisions = []
for i in range(N):
if alive_until[i] is not None: # 中途崩溃过 => 故障进程, 不要求它决定
decisions.append("CRASHED")
else:
decisions.append(known[i][min(known[i].keys())])
return decisions, known
def run_case(title, N, proposals, alive_until, partial_drop, rounds):
print("-" * 76)
print(title)
print(f" N={N} 提议={proposals} 执行轮数={rounds}")
print(" 崩溃: " + (", ".join(
f"p{i} 在第 {alive_until[i]} 轮崩溃"
+ (f"(只发给 {sorted(partial_drop[(i, alive_until[i])])})"
if (i, alive_until[i]) in partial_drop else "")
for i in range(N) if alive_until[i] is not None) or "无"))
decisions, known = simulate(N, proposals, alive_until, partial_drop, rounds)
correct = [d for d in decisions if d != "CRASHED"]
agree = len(set(correct)) == 1
print(f" 正确进程最终决定值 = {decisions} => "
f"{'Agreement 成立 ✔' if agree else 'Agreement 被违反 ✘'}")
print()
return agree
if __name__ == "__main__":
random.seed(425)
print("############ 实验 1: 崩溃数 <= f, 执行 f+1 轮 => 所有正确进程一致 ############\n")
N, f = 6, 2
proposals = [random.randint(0, 1) for _ in range(N)]
alive = [None] * N
alive[0] = 1 # p0 第 1 轮崩溃
alive[2] = 2 # p2 第 2 轮崩溃
partial = {(0, 1): {1}, (2, 2): {3}}
run_case(f"实验 1: N={N}, f={f}, 执行 f+1={f+1} 轮", N, proposals, alive, partial, f + 1)
print("############ 实验 2: 崩溃数仍 <= f, 但只执行 f 轮 => 失败 ############\n")
N2, f2 = 3, 1
run_case(f"实验 2a: N={N2}, f={f2}, 只执行 f={f2} 轮 (少跑一轮)",
N2, [1, 0, 0], [1, None, None], {(0, 1): {1}}, f2)
run_case(f"实验 2b: 同样的崩溃, 执行 f+1={f2 + 1} 轮 => 一致",
N2, [1, 0, 0], [1, None, None], {(0, 1): {1}}, f2 + 1)
print("############ 实验 3: 实际崩溃数 = f+1 > f => f+1 轮也不够 ############\n")
run_case("实验 3: N=4, 假设 f=1, 执行 2 轮, 但实际崩溃 2 个进程",
4, [1, 0, 0, 0], [1, None, None, 2], {(0, 1): {3}, (3, 2): {1}}, 2)
print(" 说明: p0 的值只传给了 p3(第 1 轮崩溃), p3 又只把该值传给了 p1(第 2 轮崩溃),")
print(" 于是 p1 知道 1、p2 只能按它知道的最小编号提议者决定 0 —— 不一致。")
print(" 这正是讲义归纳证明中'每一轮各需要一个崩溃'的链条: f+1 轮只能容忍 f 个崩溃。\n")
print("############ 实验 4: 随机批量试验 (f <= N-1, 执行 f+1 轮) ############\n")
total, ok_cnt = 0, 0
for trial in range(300):
random.seed(1000 + trial)
N4 = random.choice([3, 5, 7, 9])
f4 = random.randint(0, N4 - 1)
prop = [random.randint(0, 1) for _ in range(N4)]
al = [None] * N4
for i in random.sample(range(N4), f4): # 崩溃进程及其崩溃轮次
al[i] = random.randint(1, f4 + 1)
part = {}
for i in range(N4):
if al[i] is not None: # 崩溃那一轮只发给一个随机子集
part[(i, al[i])] = set(random.sample(
[j for j in range(N4) if j != i],
random.randint(0, N4 - 2)))
dec, _ = simulate(N4, prop, al, part, f4 + 1, verbose=False)
correct = [d for d in dec if d != "CRASHED"]
total += 1
ok_cnt += (len(set(correct)) == 1)
print(f" 随机 {total} 次 (N in {{3,5,7,9}}, 0 <= f <= N-1, 崩溃那一轮随机丢消息, 执行 f+1 轮):")
print(f" Agreement 成立 {ok_cnt}/{total} 次 => "
f"{'全部成功 ✔ (与定理一致)' if ok_cnt == total else '存在失败 ✘'}")
print()
运行输出（真实运行结果）
############ 实验 1: 崩溃数 <= f, 执行 f+1 轮 => 所有正确进程一致 ############
----------------------------------------------------------------------------
实验 1: N=6, f=2, 执行 f+1=3 轮
N=6 提议=[1, 0, 0, 1, 0, 0] 执行轮数=3
崩溃: p0 在第 1 轮崩溃(只发给 [1]), p2 在第 2 轮崩溃(只发给 [3])
第 1 轮末 值集合(按提议者 id) p0:{012345} p1:{012345} p2:{12345} p3:{12345} p4:{12345} p5:{12345}
第 2 轮末 值集合(按提议者 id) p0=崩溃 p1:{012345} p2:{012345} p3:{012345} p4:{012345} p5:{012345}
第 3 轮末 值集合(按提议者 id) p0=崩溃 p1:{012345} p2=崩溃 p3:{012345} p4:{012345} p5:{012345}
正确进程最终决定值 = ['CRASHED', 1, 'CRASHED', 1, 1, 1] => Agreement 成立 ✔
############ 实验 2: 崩溃数仍 <= f, 但只执行 f 轮 => 失败 ############
----------------------------------------------------------------------------
实验 2a: N=3, f=1, 只执行 f=1 轮 (少跑一轮)
N=3 提议=[1, 0, 0] 执行轮数=1
崩溃: p0 在第 1 轮崩溃(只发给 [1])
第 1 轮末 值集合(按提议者 id) p0:{012} p1:{012} p2:{12}
正确进程最终决定值 = ['CRASHED', 1, 0] => Agreement 被违反 ✘
----------------------------------------------------------------------------
实验 2b: 同样的崩溃, 执行 f+1=2 轮 => 一致
N=3 提议=[1, 0, 0] 执行轮数=2
崩溃: p0 在第 1 轮崩溃(只发给 [1])
第 1 轮末 值集合(按提议者 id) p0:{012} p1:{012} p2:{12}
第 2 轮末 值集合(按提议者 id) p0=崩溃 p1:{012} p2:{012}
正确进程最终决定值 = ['CRASHED', 1, 1] => Agreement 成立 ✔
############ 实验 3: 实际崩溃数 = f+1 > f => f+1 轮也不够 ############
----------------------------------------------------------------------------
实验 3: N=4, 假设 f=1, 执行 2 轮, 但实际崩溃 2 个进程
N=4 提议=[1, 0, 0, 0] 执行轮数=2
崩溃: p0 在第 1 轮崩溃(只发给 [3]), p3 在第 2 轮崩溃(只发给 [1])
第 1 轮末 值集合(按提议者 id) p0:{0123} p1:{123} p2:{123} p3:{0123}
第 2 轮末 值集合(按提议者 id) p0=崩溃 p1:{0123} p2:{123} p3:{0123}
正确进程最终决定值 = ['CRASHED', 1, 0, 'CRASHED'] => Agreement 被违反 ✘
说明: p0 的值只传给了 p3(第 1 轮崩溃), p3 又只把该值传给了 p1(第 2 轮崩溃),
于是 p1 知道 1、p2 只能按它知道的最小编号提议者决定 0 —— 不一致。
这正是讲义归纳证明中'每一轮各需要一个崩溃'的链条: f+1 轮只能容忍 f 个崩溃。
############ 实验 4: 随机批量试验 (f <= N-1, 执行 f+1 轮) ############
随机 300 次 (N in {3,5,7,9}, 0 <= f <= N-1, 崩溃那一轮随机丢消息, 执行 f+1 轮):
Agreement 成立 300/300 次 => 全部成功 ✔ (与定理一致)
【代码做什么？】
simulate()用两个字典数组模拟每个进程的 $Values^r_i$ 与 $Values^{r-1}_i$；known[i]记录”进程 $i$ 知道谁的提议值”，键是提议者 id（这样最后才能按 id 取”一致的最小值”）。- 每一轮先让存活进程广播 $Values^{r}_i \setminus Values^{r-1}_i$（即”上一轮新知道的值”），再统一把收到的集合并入
known——顺序严格对应讲义伪代码的”先 multicast、再更新集合”。 alive_until[i]指定进程 $i$ 参与发送的最后一轮；partial_drop[(i,r)]描述”$i$ 在第 $r$ 轮崩溃，只把消息发给了这几个人”，这正是 FLP/讲义归纳证明里最关键的”定向丢失”。- 实验 1 用 $N=6, f=2$ 跑满 $f+1=3$ 轮：可以看到第 1 轮末 $p_2,\dots,p_5$ 还不知道 $p_0$ 的值（
p2:{12345}缺了 0），而第 2 轮就被 $p_1$ 补上了；第 3 轮所有人集合相同 ⇒ Agreement 成立。 - 实验 2a 只跑 $f=1$ 轮（”少一轮”）⇒ $p_1$ 决定 1、$p_2$ 决定 0，一致性被违反；实验 2b 用同样的崩溃模式跑满 $f+1=2$ 轮 ⇒ 两人都决定 1。两行输出之差就是 $f+1$ 轮的价值。
- 实验 3 让实际崩溃数达到 $f+1=2 > f$（且 $p_0$ 的值只传给 $p_3$、$p_3$ 只传给 $p_1$）⇒ 即使跑满 $f+1$ 轮，$p_1$ 与 $p_2$ 仍然不一致：“至多 $f$ 个崩溃”这个前提一旦被打破，算法就不再保证任何东西。（若 $f \ge N$，则所有进程都可能崩溃、系统里已经没有”正确进程”，共识命题本身退化——因此”突破 $f$”这一情形才是可观测的失败边界，也是本实验要展示的东西。）
- 实验 4 做 300 次随机试验（$N \in \{3,5,7,9\}$、$0 \le f \le N-1$、崩溃那一轮随机丢消息），Agreement 300/300 成立，与定理一致。
【分布式机制透视】
- 同步性是靠”轮屏障”模拟的：每一轮里，所有存活进程都先发完、再统一收，这等价于”轮长 » 最大传输延迟”——真实同步系统里由硬件/总线保证，仿真里由循环结构保证。
- “崩溃”被建模为”停止发送 + 不再更新状态”，而不是”进程对象被删除”：这很关键，因为存活进程仍然会（在它们的集合里）保留崩溃者此前发出的值——真实系统里也是如此（数据不会因为节点死掉而消失）。
- “定向丢失”（
partial_drop）是现实故障的忠实抽象：真实进程崩溃前往往已经发出了一部分消息（TCP 缓冲、异步发送队列），所以”对 A 发了、对 B 没发”是完全可能的。这正是让 $f+1$ 轮证明的链条”每一轮都需要一个新崩溃”得以实现的东西。 - 决定规则用”最小编号提议者”而不是”最小值”：与讲义注释一致（consistent minimum based on say, id (not minimum value)）。原因是决定值必须是值集合的确定性函数：只要两个人集合相同，按 id 取和按数值取都会一致；但按 id 取更”中立”，不会因为值域本身偏向某个数而引入偏差（在非二值共识里这一点很重要）。
【与理论的对应】
- 代码中的
for r in range(1, rounds+1)与delta计算，逐行对应 15.3.1 伪代码的步骤 1/2； - 实验 2a 的失败正是 15.3.1 中 Agreement 归纳证明链条的第 5–6 步（”每一轮需要一个不同的崩溃，共需 $f+1$ 次”）被反向使用的样子：崩溃只有 1 个、轮数也只有 1，于是”$v$ 只到 $p_1$ 不到 $p_2$”的局面被保留到了最后；
- 实验 3 说明终止性证明的前提（$f$ 已知且真实）与一致性证明的前提（最多 $f$ 个崩溃）是两条独立的假设，缺一条都不能推出结论。
15.4.2 Ben-Or 随机化共识模拟器
#!/usr/bin/env python3
"""
Ben-Or 随机化共识模拟器 (CS 425 Lecture 15 = 课程 Lecture 17)
系统模型
* 异步消息传递: 没有时钟、没有超时; "收齐 n-f 条消息"是唯一的等待条件。
仿真中: 崩溃进程一律视为"从头就静默"(最坏情况), 若实际崩溃数 c < f, 则存活进程多于
n-f, 每个进程随机收集其中 n-f 条 —— 模拟"其余消息被判为慢、被无限延迟"。
* 故障模型: crash-stop, 至多 f < N/2 个进程崩溃
* 随机性: 私有硬币(每个进程自己翻) 或 共享硬币(每轮所有进程拿到同一个随机位)
算法 (Ben-Or 1983, 崩溃故障版, N >= 2f+1)
第 r 轮:
阶段1 提议: 广播 estimate; 收 n-f 条; 若收到的 n-f 条全部相同 = v => pref=v, 否则 pref=⊥
阶段2 投票: 广播 pref; 收 n-f 条; cnt(v) = 收到的 v 票数(⊥ 不计):
cnt(v) >= f+1 => 决定 v; 否则 cnt(v) >= 1 => estimate=v; 否则转阶段3
阶段3 硬币: 无足够支持时用硬币打破对称性, 以概率 1 收敛 (FLP 允许的唯一出路之一)
"""
import random
from collections import Counter
def benor_run(N, proposals, f, rng, use_shared_coin, crash_count=None,
max_rounds=20000, trace_limit=0):
"""跑一次 Ben-Or。返回 (decisions, rounds_used_or_None, trace_lines)"""
c = f if crash_count is None else crash_count
crashed = set(rng.sample(range(N), c)) # 崩溃进程: 从头静默
est = list(proposals)
decided = {}
lines = []
rounds_used = None
for r in range(1, max_rounds + 1):
alive = [i for i in range(N) if i not in crashed]
# ---------- 阶段 1: 提议 ----------
pref = {}
for i in alive:
others = [j for j in alive if j != i]
got = rng.sample(others, N - f - 1) if len(others) > N - f - 1 else others
vals = ([est[i]] + [est[j] for j in got])[:N - f]
pref[i] = vals[0] if len(set(vals)) == 1 else None # 一致才采纳, 否则 ⊥
# ---------- 阶段 2: 投票 + 决定 ----------
coin = rng.randint(0, 1) if use_shared_coin else None
for i in alive:
others = [j for j in alive if j != i]
got = rng.sample(others, N - f - 1) if len(others) > N - f - 1 else others
votes = ([pref[i]] + [pref[j] for j in got])[:N - f]
cnt = Counter(v for v in votes if v is not None)
top = max(cnt.items(), key=lambda kv: (kv[1], -kv[0]), default=(None, 0))
if top[1] >= f + 1: # 决定阈值 D = f+1
decided.setdefault(i, top[0])
est[i] = top[0]
elif top[1] >= 1: # 采纳阈值 A = 1
est[i] = top[0]
else: # ---------- 阶段 3: 硬币
est[i] = coin if use_shared_coin else rng.randint(0, 1)
if trace_limit and r <= trace_limit:
def fmt(i, v):
return "X" if i in crashed else ("." if v is None else str(v))
lines.append(f" 第{r}轮: 估计={[fmt(i, est[i]) for i in range(N)]} "
f"pref={[fmt(i, pref.get(i)) for i in range(N)]} "
f"硬币={'共享=' + str(coin) if use_shared_coin else '各自翻转'}"
f"{' => 全部决定 ' + str(decided[alive[0]]) if all(i in decided for i in alive) else ''}")
if all(i in decided for i in alive): # 所有正确进程都已决定
rounds_used = r
break
decisions = {i: decided.get(i) for i in alive}
return decisions, rounds_used, lines
def histogram(data, width=46):
"""按对数区间分桶, 便于看清'绝大多数很快 + 偶尔很久'的重尾形状"""
buckets = [(1, 1), (2, 2), (3, 4), (5, 8), (9, 16), (17, 32), (33, 64), (65, 128), (129, 10 ** 9)]
counts = {b: 0 for b in buckets}
for d in data:
for b in buckets:
if b[0] <= d <= b[1]:
counts[b] += 1
break
mx = max(counts.values())
lines = []
for b in buckets:
if counts[b] == 0:
continue
label = f"{b[0]}" if b[0] == b[1] else (f"{b[0]}-{b[1]}" if b[1] < 10 ** 9 else f">={b[0]}")
lines.append(f" {label:>7} 轮 |{'#' * max(1, int(counts[b] / mx * width)):<{width}}| "
f"{counts[b]:>4} 次 ({counts[b] / len(data) * 100:4.1f}%)")
return "\n".join(lines)
if __name__ == "__main__":
print("################ 1) 单次运行全过程 (N=3, f=1, 私有硬币) ################\n")
prop = [1, 0, 0]
dec, ru, lines = benor_run(3, prop, 1, random.Random(7), False, trace_limit=40)
print(f" 提议值={prop} (X=崩溃进程, .=⊥ 未表态)")
for ln in lines:
print(ln)
print(f" => 决定: {dec} 共 {ru} 轮\n")
print("################ 2) 共享硬币 (N=7, f=2) 全程 ################\n")
dec2, ru2, lines2 = benor_run(7, [1, 0, 1, 0, 0, 1, 0], 2, random.Random(11), True, trace_limit=40)
for ln in lines2:
print(ln)
print(f" => 决定: {dec2} 共 {ru2} 轮\n")
print("################ 3) Agreement / Validity 检验 (每配置 200 次, 私有硬币) ################\n")
print(f" {'N':>3} {'f':>3} {'f/N':>6} {'N-f':>5} {'Agreement':>11} {'Validity':>10} "
f"{'平均轮数':>9} {'最长轮数':>9} {'未终止':>7}")
for (N, f) in [(3, 1), (5, 1), (5, 2), (7, 2), (7, 3), (9, 2), (9, 4), (11, 5)]:
agree = valid = trunc = 0
rl = []
for t in range(200):
rg = random.Random(50_000 + 97 * t + N * 7 + f)
proposals = [rg.randint(0, 1) for _ in range(N)]
crash_count = rg.randint(f // 2, f) # 实际崩溃数 <= f
dec, ru, _ = benor_run(N, proposals, f, rg, False, crash_count=crash_count)
vals = list(dec.values())
agree += (len(set(vals)) == 1)
valid += all(v in proposals for v in vals)
if ru is None:
trunc += 1
else:
rl.append(ru)
mr = sum(rl) / len(rl) if rl else float("nan")
print(f" {N:>3} {f:>3} {f/N:>6.2f} {N-f:>5} {agree:>8}/200 {valid:>7}/200 "
f"{mr:>9.1f} {max(rl) if rl else 0:>9} {trunc:>7}")
print("\n Agreement 与 Validity 全程 200/200 成立 (安全性不依赖随机性);")
print(" 平均轮数随正确进程数 N-f 增大而迅速上升 —— 私有硬币下'所有硬币恰好相同'的概率是")
print(" 2^-(N-f)+1, 因此轮数分布是重尾的几何分布。\n")
print("################ 4) 轮数分布直方图: 私有硬币 vs 共享硬币 (N=7, f=2) ################\n")
for label, shared in [("私有硬币", False), ("共享硬币", True)]:
data = []
for t in range(400):
rg = random.Random(9_000 + 13 * t)
proposals = [rg.randint(0, 1) for _ in range(7)]
_, ru, _ = benor_run(7, proposals, 2, rg, shared, max_rounds=4000)
if ru:
data.append(ru)
print(f" --- {label}: 平均 {sum(data) / len(data):.2f} 轮, 最长 {max(data)} 轮, "
f"样本 {len(data)}/400 ---")
print(histogram(data))
print()
print("################ 5) 共享硬币下逐步放大 N (每配置 200 次) ################\n")
print(f" {'N':>3} {'f':>3} {'平均轮数':>9} {'最长轮数':>9} {'Agreement':>11}")
for (N, f) in [(4, 1), (7, 2), (10, 3), (13, 4), (16, 5)]:
rl, agree = [], 0
for t in range(200):
rg = random.Random(777 + 31 * t + N)
proposals = [rg.randint(0, 1) for _ in range(N)]
dec, ru, _ = benor_run(N, proposals, f, rg, True, max_rounds=500)
if ru:
rl.append(ru)
agree += (len(set(dec.values())) == 1 and all(v in proposals for v in dec.values()))
print(f" {N:>3} {f:>3} {sum(rl) / len(rl):>9.2f} {max(rl):>9} {agree:>8}/200")
print("\n 结论: 共享硬币把'所有进程拿到同一个随机位'变成免费事件, 因此轮数降到常数级;")
print(" 这正是 Ben-Or 期望 O(1) 轮、但需要 common coin 这一额外同步原语的原因。")
print()
运行输出（真实运行结果）
################ 1) 单次运行全过程 (N=3, f=1, 私有硬币) ################
提议值=[1, 0, 0] (X=崩溃进程, .=⊥ 未表态)
第1轮: 估计=['0', 'X', '1'] pref=['.', 'X', '.'] 硬币=各自翻转
第2轮: 估计=['0', 'X', '0'] pref=['.', 'X', '.'] 硬币=各自翻转
第3轮: 估计=['0', 'X', '0'] pref=['0', 'X', '0'] 硬币=各自翻转 => 全部决定 0
=> 决定: {0: 0, 2: 0} 共 3 轮
################ 2) 共享硬币 (N=7, f=2) 全程 ################
第1轮: 估计=['1', '1', '1', 'X', 'X', '1', '1'] pref=['.', '.', '.', 'X', 'X', '.', '.'] 硬币=共享=1
第2轮: 估计=['1', '1', '1', 'X', 'X', '1', '1'] pref=['1', '1', '1', 'X', 'X', '1', '1'] 硬币=共享=1 => 全部决定 1
=> 决定: {0: 1, 1: 1, 2: 1, 5: 1, 6: 1} 共 2 轮
################ 3) Agreement / Validity 检验 (每配置 200 次, 私有硬币) ################
N f f/N N-f Agreement Validity 平均轮数 最长轮数 未终止
3 1 0.33 2 200/200 200/200 2.0 11 0
5 1 0.20 4 200/200 200/200 6.3 34 0
5 2 0.40 3 200/200 200/200 3.7 21 0
7 2 0.29 5 200/200 200/200 11.3 49 0
7 3 0.43 4 200/200 200/200 5.8 34 0
9 2 0.22 7 200/200 200/200 38.1 245 0
9 4 0.44 5 200/200 200/200 9.3 71 0
11 5 0.45 6 200/200 200/200 15.2 74 0
Agreement 与 Validity 全程 200/200 成立 (安全性不依赖随机性);
平均轮数随正确进程数 N-f 增大而迅速上升 —— 私有硬币下'所有硬币恰好相同'的概率是
2^-(N-f)+1, 因此轮数分布是重尾的几何分布。
################ 4) 轮数分布直方图: 私有硬币 vs 共享硬币 (N=7, f=2) ################
--- 私有硬币: 平均 14.77 轮, 最长 79 轮, 样本 400/400 ---
1 轮 |############# | 30 次 ( 7.5%)
2 轮 |########### | 25 次 ( 6.2%)
3-4 轮 |##################### | 47 次 (11.8%)
5-8 轮 |############################### | 69 次 (17.2%)
9-16 轮 |######################################## | 88 次 (22.0%)
17-32 轮 |##############################################| 100 次 (25.0%)
33-64 轮 |################ | 36 次 ( 9.0%)
65-128 轮 |## | 5 次 ( 1.2%)
--- 共享硬币: 平均 1.93 轮, 最长 2 轮, 样本 400/400 ---
1 轮 |### | 30 次 ( 7.5%)
2 轮 |##############################################| 370 次 (92.5%)
################ 5) 共享硬币下逐步放大 N (每配置 200 次) ################
N f 平均轮数 最长轮数 Agreement
4 1 1.73 2 200/200
7 2 1.92 2 200/200
10 3 1.98 2 200/200
13 4 2.00 2 200/200
16 5 2.00 2 200/200
结论: 共享硬币把'所有进程拿到同一个随机位'变成免费事件, 因此轮数降到常数级;
这正是 Ben-Or 期望 O(1) 轮、但需要 common coin 这一额外同步原语的原因。
【代码做什么？】
benor_run()实现 15.3.2 的三个阶段：阶段 1 广播估计并检查”收到的 $n-f$ 条是否完全一致”，阶段 2 统计票数并按阈值 $D=f+1$（决定）、$A=1$（采纳）行动，阶段 3 在”毫无支持”时抛硬币。- “收 $n-f$ 条”是这样模拟的：
others是当前存活的其他进程；若存活者多于 $n-f$，就rng.sample随机挑 $n-f-1$ 个——这代表”其余消息被无限延迟”，也顺便让代码覆盖了”实际崩溃数 $c < f$”这一更宽松的情形（此时各进程看到的子集不同，正是传播性论证 $\ge D-f$ 起作用的地方）。 - 崩溃进程用
crashed集合表示，从头就静默（最坏情况），因此它们不出现在任何alive列表里，也不会出现在别人的收件集合中。 use_shared_coin=True时，每轮用rng.randint(0,1)生成一个位并让所有进程使用它——这就是”公共硬币”的抽象（真实系统里由门限签名/VSS 实现）。- 实验 1（$N=3,f=1$，私有硬币）打印逐轮的
估计 / pref / 硬币：可以清楚看到”估计不一致 ⇒ 全体 $\bot$ ⇒ 抛硬币 ⇒ 恰好一致 ⇒ 下一轮决定”这条路径。 - 实验 3 对 8 组 $(N,f)$ 各跑 200 次，统计 Agreement（全部 200/200）与 Validity（全部 200/200），并给出平均/最长轮数——可以看到平均轮数随正确进程数 $N-f$ 迅速上升（$N-f=7$ 时平均 38.1 轮、最长 245 轮）。
- 实验 4 用对数分桶直方图展示轮数分布：私有硬币呈典型重尾（7.5% 一轮就结束，但有 1.2% 需要 65–128 轮）；共享硬币则在 1–2 轮内结束（92.5% 为 2 轮）。
- 实验 5 把 $N$ 从 4 放大到 16（$f=(N-1)/3$ 附近），共享硬币下平均轮数始终在 2 左右——“期望 $O(1)$”不是口号，是可以量出来的。
【分布式机制透视】
- “异步”的模拟方式：没有全局轮次（每个进程自己数自己的轮），等待条件只有”收到 $n-f$ 条消息”；”慢消息”通过随机子集采样来体现。真实异步系统里，这个”慢”可能是 GC、网络重排、CPU 排队。
- 崩溃与慢的不可区分性：崩溃进程不发消息，”幸存者集合”因此缩小；代码没有、也无法实现”检测谁死了”——这正是 FLP 的前提，也是算法只依赖 $n-f$ 计数的原因。
- 随机源的作用：私有硬币下每个进程独立抛硬币，因此”所有人恰好抛到同一边”的概率随 $n-f$ 指数下降；共享硬币把这一事件变成”要么全对、要么全错”的公共事件，于是收敛快得多——但代价是必须实现 common coin 这个额外原语（它本身需要一轮或多轮通信，这就是”没有免费午餐”的具体体现）。
- 决定后继续参与：代码里已决定的进程仍保留
est并继续投票（相当于把决定值当作自己的估计转发），这在工程上很常见（例如让决定”扩散”得更快）；理论上决定后退出也正确，因为 Agreement 已经由前三步不变式保证。
【与理论的对应】
- 逐行对应 15.3.2 伪代码；
top[1] >= f+1就是 $D$，top[1] >= 1就是 $A$； - 200/200 的 Agreement/Validity 结果验证的是“安全性不依赖随机性”这一论断：无论硬币怎么翻，一致性都成立（不变式 I → 传播 → 锁定 → 不可逆）；
- 轮数分布验证的是终止性只能以概率 1 成立：存在极少数运行需要几十甚至上百轮（重尾），而理论上”任何有限轮之后都仍可能未终止”——这正是 FLP 在工程上的影子：随机化算法不保证有限时间终止，只是让它”几乎总是很快”；
- 共享硬币把期望轮数从 $2^{\Theta(n)}$ 降到 $O(1)$，对应 15.3.2 里活性分析的两种情形。
15.4.3 拜占庭将军模拟器（OM(m) 与签名消息）
#!/usr/bin/env python3
"""
拜占庭将军模拟器: 口头消息 OM(m) 与签名消息 SM(m) (CS 425 Lecture 15 = 课程 Lecture 17)
模型
* 值: ATTACK=1 / RETREAT=0; 收不到消息时用默认值 RETREAT (Lamport-Shostak-Pease 的约定)
* 口头消息: 叛徒可以任意撒谎、对不同人发矛盾的值, 但"转述"只能转述自己收到的值
(不能凭空伪造一个忠诚者说过的话) —— 这正是口头消息模型的定义
* 签名消息: 忠诚者给消息签名, 叛徒无法伪造别人的签名, 因此任何忠诚者都可以把
"指挥官亲笔签名的命令"转给其他人作为证据
OM(m) (Lamport, Shostak, Pease 1982)
OM(0): 指挥官把值发给每个中尉; 中尉采用收到的值(收不到则默认值)
OM(m), m>0: 1) 指挥官把值发给每个中尉, 中尉 i 记收到的值为 v_i
2) 中尉 i 作为指挥官, 用 v_i 执行 OM(m-1), 发给其余 n-2 个中尉
3) 中尉 i 对收到的全部值(含 v_i)取多数 majority(); 平局取默认值
定理: 当 n > 3m 时 OM(m) 同时满足 IC1(忠诚者一致) 与 IC2(指挥官忠诚时大家服从)
"""
import itertools
import random
ATTACK, RETREAT = 1, 0
DEFAULT = RETREAT
def majority(vals):
ones = sum(vals)
if ones * 2 > len(vals):
return ATTACK
if ones * 2 < len(vals):
return RETREAT
return DEFAULT # 平局 => 默认 RETREAT
class Adversary:
"""叛徒的发送策略: table[(path, sender, recipient)] = 要说谎成的值"""
def __init__(self, table=None):
self.table = {} if table is None else dict(table)
self.seen = set() # 记录被查询过的键 => 得到需要搜索的键空间
self.record_only = table is None
def send(self, path, sender, recipient, honest_value):
self.seen.add((path, sender, recipient))
if self.record_only:
return ATTACK # 只用来枚举键空间, 取值任意
return self.table.get((path, sender, recipient), honest_value)
def om(commander, cvalue, group, m, traitors, adv, path=(), log=None):
"""执行 OM(m); group = 中尉列表; 返回值 {中尉: 决定值}"""
recv = {}
for l in group: # 步骤 1: 指挥官发言
recv[l] = (adv.send(path + (commander,), commander, l, cvalue)
if commander in traitors else cvalue)
if log is not None and len(path) <= 1:
tag = "第1步: 指挥官" if not path else f"第2步: p{commander} 转述(作为其 OM 子协议的指挥官)"
log.append(f" {tag} p{commander} 对 " +
", ".join(f"p{l} 说 {recv[l]}" for l in group) +
(" <== 对不同人说了不同的值(撒谎)!" if commander in traitors
and len(set(recv.values())) > 1 else ""))
if m == 0:
return dict(recv)
sub = {}
for l in group: # 步骤 2: 中尉各自当指挥官
sub[l] = om(l, recv[l], [x for x in group if x != l], m - 1,
traitors, adv, path + (commander,), log)
out = {} # 步骤 3: 多数表决
for l in group:
vals = [recv[l]] + [sub[j][l] for j in group if j != l]
out[l] = majority(vals)
if log is not None and l not in traitors and not path:
log.append(f" 根节点: 忠诚中尉 p{l} 收到的值 = {vals} => 最终决定 {out[l]}")
return out
def check(n, f, cmdr_traitor, lt_traitors, table, log=None):
"""跑一次, 返回 (是否同时满足 IC1 与 IC2, 忠诚中尉的决定)"""
traitors = set(lt_traitors) | ({0} if cmdr_traitor else set())
lieutenants = list(range(1, n))
dec = om(0, ATTACK, lieutenants, f, traitors, Adversary(table), log=log)
loyal = {l: dec[l] for l in lieutenants if l not in traitors}
ic1 = len(set(loyal.values())) == 1 # 忠诚者必须一致
ic2 = cmdr_traitor or all(v == ATTACK for v in loyal.values()) # 服从忠诚指挥官
return (ic1 and ic2), loyal
def search(n, f, trials=2500, seed=425):
"""枚举所有「谁是叛徒」的布局: 键空间小则穷举撒谎策略, 否则随机搜索"""
rng, checked = random.Random(seed), 0
layouts = [(ct, combo) for ct in (False, True)
for combo in itertools.combinations(range(1, n), f - 1 if ct else f)]
for (cmdr_traitor, lt_tr) in layouts:
adv = Adversary(None)
om(0, ATTACK, list(range(1, n)), f, set(lt_tr) | ({0} if cmdr_traitor else set()), adv)
keys = sorted(adv.seen)
checked += 1
if len(keys) <= 14: # 键空间小: 穷举所有撒谎策略
tables = [dict(zip(keys, bits)) for bits in itertools.product([0, 1], repeat=len(keys))]
else: # 键空间大: 随机采样
tables = [{k: rng.randint(0, 1) for k in keys} for _ in range(trials)]
for idx, table in enumerate(tables, 1):
ok, loyal = check(n, f, cmdr_traitor, lt_tr, table)
if not ok:
who = (f"指挥官{'叛徒' if cmdr_traitor else '忠诚'} + 叛徒中尉 "
+ (",".join(f"p{x}" for x in lt_tr) if lt_tr else "无"))
log = []
check(n, f, cmdr_traitor, lt_tr, table, log=log)
return checked, (f" [{who}] 第 {idx}/{len(tables)} 个撒谎策略就破坏了共识 "
f"(忠诚中尉决定 {loyal})\n" + "\n".join(log[:8]))
return checked, None
def three_generals_exhaustive():
"""N=3,f=1 的穷举不可能性证明: 忠诚中尉的视角 = (指挥官说的值, 同伴说的值)"""
views = [(c, p) for c in (0, 1) for p in (0, 1)]
bad = 0
for bits in itertools.product([0, 1], repeat=len(views)):
D = dict(zip(views, bits)) # 一张确定性决策表就是一种算法
sc1 = D[(1, 0)] == ATTACK # 场景1: 指挥官忠诚下令 1, 叛徒谎报 0 => 必须服从
sc3 = D[(0, 1)] == RETREAT # 场景3: 指挥官忠诚下令 0, 叛徒谎报 1 => 必须服从
sc2 = D[(1, 0)] == D[(0, 1)] # 场景2: 指挥官是叛徒(对 p1 说 1、对 p2 说 0) => 两中尉必须一致
bad += not (sc1 and sc2 and sc3)
return 2 ** len(views), bad
def sm_demo(n, cmdr_traitor, lt_traitors):
"""签名消息 SM(1): 返回忠诚将军的决定"""
traitors = set(lt_traitors) | ({0} if cmdr_traitor else set())
lieutenants = list(range(1, n))
V = {} # 第 1 轮: 指挥官签名广播(可自相矛盾)
for l in lieutenants:
V[l] = {(ATTACK if (not cmdr_traitor or l % 2 == 1) else RETREAT, (0,))}
V2 = {l: set(V[l]) for l in lieutenants} # 第 2 轮: 每人转发自己收到的签名消息
for l in lieutenants:
if l in traitors:
continue # 叛徒选择沉默(最坏情况之一)
for other in lieutenants:
if other != l:
for (val, sigs) in V[l]:
V2[other].add((val, sigs + (l,)))
dec = {}
for l in lieutenants: # 决定: 只看「指挥官签名的值」
vals = {v for (v, sigs) in V2[l] if 0 in sigs} # 叛徒伪造的签名链里没有 p0, 被丢弃
dec[l] = vals.pop() if len(vals) == 1 else DEFAULT # 两个值 => 指挥官是叛徒 => 默认值
return {l: dec[l] for l in lieutenants if l not in traitors}
if __name__ == "__main__":
random.seed(425)
print("############ 1) 口头消息 OM(m) 在 N = 3f+1 前后的成败 ############\n")
for (n, f) in [(3, 1), (4, 1), (6, 2), (7, 2)]:
checked, bad = search(n, f, trials=2500)
if bad is None:
print(f" N={n}, f={f}: 检查了 {checked} 种叛徒布局 (小键空间穷举, 大键空间随机 2500 个策略)")
print(f" => 未发现任何反例 ✔ (N={n} >= 3f+1={3 * f + 1}, 满足定理条件)\n")
else:
print(f" N={n}, f={f}: 找到反例 ✘ (N={n} < 3f+1={3 * f + 1}, 定理保证必然存在)")
print(bad + "\n")
print("############ 2) 三个将军一个叛徒: 穷举所有可能的确定性算法 ############\n")
total, bad = three_generals_exhaustive()
print(" 把「忠诚中尉的决策」看成一个函数: 输入 = (指挥官告诉它的值, 同伴告诉它的值),")
print(f" 输出 = 0/1, 一共有 2^4 = {total} 种确定性算法。逐一检验 IC1/IC2:")
print(f" => {bad}/{total} 种算法都至少违反 IC1 或 IC2 中的一条 ✘\n")
print(" 例如取 majority() 并让平局回退到 RETREAT, 看场景 1:")
log = []
ok, loyal = check(3, 1, False, (2,), {((0, 2), 2, 1): RETREAT}, log=log)
for ln in log:
print(ln)
print(f" 忠诚中尉 p1 收到 [1, 0] 平局 => 决定 {loyal[1]}, 而忠诚指挥官下的是 ATTACK=1"
f" => 违反 IC2 ✘")
print(" 若把平局改成取 ATTACK, 则值对称的场景 3(指挥官下令 0、叛徒谎报 1)会违反 IC2;")
print(" 若让两种视角都倒向同一侧, 则场景 2(指挥官是叛徒)的两名忠诚中尉必然不一致。\n")
print("############ 3) 签名消息: 用密码学把 N >= 3f+1 降为 N >= f+2 ############\n")
for (n, ct, lt, desc) in [(3, False, (2,), "N=3,f=1 指挥官忠诚、中尉 p2 是叛徒 (口头消息下违反 IC2)"),
(3, True, (), "N=3,f=1 指挥官是叛徒、对 p1/p2 说矛盾的话"),
(4, True, (3,), "N=4,f=2 < 3f+1=7: 指挥官叛徒 + 中尉 p3 叛徒"),
(5, True, (3, 4), "N=5,f=3: 指挥官叛徒 + 两个叛徒中尉")]:
loyal = sm_demo(n, ct, lt)
print(f" {desc}\n 忠诚将军决定 = {loyal} => "
f"{'一致 ✔' if len(set(loyal.values())) == 1 else '不一致 ✘'}")
print("\n 原因: 忠诚者可以把「指挥官亲笔签名的命令」当证据转发给其他人, 而叛徒无法伪造")
print(" 别人的签名; 于是自相矛盾的指挥官一定会被识破(大家回退到默认值)。")
运行输出（真实运行结果）
############ 1) 口头消息 OM(m) 在 N = 3f+1 前后的成败 ############
N=3, f=1: 找到反例 ✘ (N=3 < 3f+1=4, 定理保证必然存在)
[指挥官忠诚 + 叛徒中尉 p1] 第 1/2 个撒谎策略就破坏了共识 (忠诚中尉决定 {2: 0})
第1步: 指挥官 p0 对 p1 说 1, p2 说 1
第2步: p1 转述(作为其 OM 子协议的指挥官) p1 对 p2 说 0
第2步: p2 转述(作为其 OM 子协议的指挥官) p2 对 p1 说 1
根节点: 忠诚中尉 p2 收到的值 = [1, 0] => 最终决定 0
N=4, f=1: 检查了 4 种叛徒布局 (小键空间穷举, 大键空间随机 2500 个策略)
=> 未发现任何反例 ✔ (N=4 >= 3f+1=4, 满足定理条件)
N=6, f=2: 找到反例 ✘ (N=6 < 3f+1=7, 定理保证必然存在)
[指挥官忠诚 + 叛徒中尉 p1,p2] 第 1/2500 个撒谎策略就破坏了共识 (忠诚中尉决定 {3: 1, 4: 0, 5: 1})
第1步: 指挥官 p0 对 p1 说 1, p2 说 1, p3 说 1, p4 说 1, p5 说 1
第2步: p1 转述(作为其 OM 子协议的指挥官) p1 对 p2 说 1, p3 说 0, p4 说 0, p5 说 1 <== 对不同人说了不同的值(撒谎)!
第2步: p2 转述(作为其 OM 子协议的指挥官) p2 对 p1 说 1, p3 说 1, p4 说 0, p5 说 0 <== 对不同人说了不同的值(撒谎)!
第2步: p3 转述(作为其 OM 子协议的指挥官) p3 对 p1 说 1, p2 说 1, p4 说 1, p5 说 1
第2步: p4 转述(作为其 OM 子协议的指挥官) p4 对 p1 说 1, p2 说 1, p3 说 1, p5 说 1
第2步: p5 转述(作为其 OM 子协议的指挥官) p5 对 p1 说 1, p2 说 1, p3 说 1, p4 说 1
根节点: 忠诚中尉 p3 收到的值 = [1, 0, 0, 1, 1] => 最终决定 1
根节点: 忠诚中尉 p4 收到的值 = [1, 0, 0, 0, 1] => 最终决定 0
N=7, f=2: 检查了 21 种叛徒布局 (小键空间穷举, 大键空间随机 2500 个策略)
=> 未发现任何反例 ✔ (N=7 >= 3f+1=7, 满足定理条件)
############ 2) 三个将军一个叛徒: 穷举所有可能的确定性算法 ############
把「忠诚中尉的决策」看成一个函数: 输入 = (指挥官告诉它的值, 同伴告诉它的值),
输出 = 0/1, 一共有 2^4 = 16 种确定性算法。逐一检验 IC1/IC2:
=> 16/16 种算法都至少违反 IC1 或 IC2 中的一条 ✘
例如取 majority() 并让平局回退到 RETREAT, 看场景 1:
第1步: 指挥官 p0 对 p1 说 1, p2 说 1
第2步: p1 转述(作为其 OM 子协议的指挥官) p1 对 p2 说 1
第2步: p2 转述(作为其 OM 子协议的指挥官) p2 对 p1 说 0
根节点: 忠诚中尉 p1 收到的值 = [1, 0] => 最终决定 0
忠诚中尉 p1 收到 [1, 0] 平局 => 决定 0, 而忠诚指挥官下的是 ATTACK=1 => 违反 IC2 ✘
若把平局改成取 ATTACK, 则值对称的场景 3(指挥官下令 0、叛徒谎报 1)会违反 IC2;
若让两种视角都倒向同一侧, 则场景 2(指挥官是叛徒)的两名忠诚中尉必然不一致。
############ 3) 签名消息: 用密码学把 N >= 3f+1 降为 N >= f+2 ############
N=3,f=1 指挥官忠诚、中尉 p2 是叛徒 (口头消息下违反 IC2)
忠诚将军决定 = {1: 1} => 一致 ✔
N=3,f=1 指挥官是叛徒、对 p1/p2 说矛盾的话
忠诚将军决定 = {1: 0, 2: 0} => 一致 ✔
N=4,f=2 < 3f+1=7: 指挥官叛徒 + 中尉 p3 叛徒
忠诚将军决定 = {1: 0, 2: 0} => 一致 ✔
N=5,f=3: 指挥官叛徒 + 两个叛徒中尉
忠诚将军决定 = {1: 0, 2: 0} => 一致 ✔
原因: 忠诚者可以把「指挥官亲笔签名的命令」当证据转发给其他人, 而叛徒无法伪造
别人的签名; 于是自相矛盾的指挥官一定会被识破(大家回退到默认值)。
【代码做什么？】
om()递归实现 $OM(m)$：步骤 1 由指挥官把自己的值（叛徒则按Adversary的表格撒谎）发给所有中尉；步骤 2 每个中尉作为指挥官、用自己收到的值执行 $OM(m-1)$；步骤 3 每个中尉对自己拿到的全部值取majority()（平局回退 RETREAT），与论文/讲义完全一致。Adversary把”叛徒的策略”表示成一张表：table[(path, sender, recipient)] = 要说谎成的值。path记录递归路径，从而区分”同一个叛徒在不同层级的 OM 子协议里”的不同谎言——这是穷举”最恶劣策略”所必需的自由度。search()先枚举所有”谁是叛徒”的布局（指挥官是否叛变 × 中尉组合），再用一次”只记录”的执行收集所有可能的撒谎位置（键空间）：键数少（$\le 14$）时穷举 $2^k$ 种撒谎策略，键数多时随机采样 2500 种。只要找到一种让 IC1 或 IC2 失败，就打印完整的破坏过程。- 实验 1 的结果与 $N \ge 3f+1$ 定理严格吻合：$N=3,f=1$ 与 $N=6,f=2$（都 $< 3f+1$）第一个/第一批随机策略就破坏了一致性；$N=4,f=1$ 与 $N=7,f=2$（都 $= 3f+1$）在 4 种 / 21 种叛徒布局、合计五万余次策略检查中没有反例（$N=4$ 是小键空间，$2^9=512$ 种策略全部穷举；$N=7$ 是 21 × 2500 次随机采样）。
three_generals_exhaustive()做了一件更彻底的事：把”忠诚中尉的决策”抽象成一张从”视角 $(c,p)$”到”决定值”的函数表，穷举全部 $2^4=16$ 种确定性算法，逐一检验三个场景 ⇒ 16/16 全部违反 IC1 或 IC2。这是 $N=3,f=1$ 不可能性的机器验证版。- 实验 3 用
sm_demo()演示签名消息：忠诚者把”指挥官签名的值”转发出去，叛徒无法伪造签名（代码里体现为”决定时只统计签名链中含指挥官 $p_0$ 的消息”）。结果：连 $(N=4,f=2)$、$(N=5,f=3)$ 这类远小于 $3f+1$ 的规模，只要签名不可伪造，忠诚将军依然能达成一致。
【分布式机制透视】
- “口头消息”语义的建模：叛徒只能改变自己发出的值（
Adversary.send），而忠诚者转述的永远是它收到的值（om中递归使用recv[l]）。这精确对应”不能凭空伪造一个忠诚者说过的话”这一模型假设——如果允许伪造，那就已经越界到”签名被攻破”，而不是口头消息模型了。 majority()的平局规则是协议的一部分：平局回退到 RETREAT 不是随意选择，而是 Lamport 等论文里的默认值约定。它同时暴露了 $N=3$ 的困境：视角 $(1,0)$ 与 $(0,1)$ 都是平局，任何平局规则都会在其中一个场景违背 IC2（代码与文字都验证了这一点）。- 穷举搜索 = “最坏情况对手”：这是分布式系统验证里非常实用的技巧——把”对所有可能的对手行为都成立”变成”对枚举出来的每一张策略表都成立”。当键空间可控时，穷举能给出比随机测试强得多的证据。
- 签名的建模：签名链
sigs（如(0, 1)表示”指挥官 $p_0$ 签过、中尉 $p_1$ 又签过”）模拟”可验证的转发证据”。叛徒能做的只有”沉默”或”发自己的东西”，而这两者都无法动摇”指挥官签名的原始值”。
【与理论的对应】
- 逐行对应 15.3.4 的 $OM(m)$ 伪代码；
len(set(recv.values())) > 1的日志标记就是”叛徒对不同人发矛盾值”的直接可视化； - 实验 1 的成败分界精确落在 $N = 3f+1$（$N=4,f=1$ 与 $N=7,f=2$ 通过；$N=3,f=1$、$N=6,f=2$ 失败），验证了 15.2.13 的充分性 + 必要性；
- 实验 2 的 16/16 验证了 15.2.13 中三个场景的不可区分性论证：不是”某个算法不够好”，而是所有确定性算法的决策表都被穷尽了；
- 实验 3 验证了 15.2.14 的结论：签名把同步拜占庭将军问题所需的规模从 $3f+1$ 降到 $f+2$（并且必须记住：这一结论不适用于异步 BFT，那里 $N \ge 3f+1$ 仍然是硬下界）。
15.5 性能与可扩展性分析
15.5.1 各共识算法的复杂度与容错能力对比
| 算法 | 系统模型 | 故障模型与容错能力 | 轮数 / 时间 | 消息复杂度 | 安全性 | 活性 |
|---|---|---|---|---|---|---|
| 同步 Flooding（15.3.1） | 同步（延迟有已知上界） | crash-stop，$f < N$ | $f+1$ 轮 | $O(N^2)$/轮，总 $O(N^2 f)$ | 绝对保证 | 绝对保证（只需同步假设） |
| Ben-Or（私有硬币）（15.3.2） | 异步 | crash-stop，$f < N/2$ | 期望 $O(2^{N-f})$，最坏无界 | $O(N^2)$/轮 | 绝对保证（不依赖随机性） | 以概率 1 终止 |
| Ben-Or（共享硬币） | 异步 + common coin | crash-stop，$f < N/2$ | 期望 $O(1)$，最坏无界 | $O(N^2)$/轮 | 绝对保证 | 概率 1 终止（尾延迟远好于私有硬币） |
| Chandra–Toueg（$\Diamond S$）（15.3.6） | 异步 + 故障检测器 | crash-stop，$f < N/2$ | 轮转协调者：每轮 $O(1)$ 次广播（失败则换人重试） | $O(N^2)$/轮 | 绝对保证 | 需要 $\Diamond S$ 的”最终”保证 |
| Paxos / Raft | 部分同步 | crash-stop，$f < N/2$ | 稳定期每个决议 $O(1)$ 轮（常为 2 RTT，带流水线可 1 RTT） | $O(N)$/请求 | 绝对保证（不依赖同步） | 仅在同步期保证 |
| PBFT（15.3.5） | 部分同步 | 拜占庭，$f < N/3$ | 正常路径 3 阶段 ≈ 3 RTT | $O(N^2)$/请求 | 绝对保证 | 视图变更后恢复（依赖同步期） |
| Tendermint / HotStuff | 部分同步 | 拜占庭，$f < N/3$ | 每视图 3–4 阶段 | HotStuff 用门限签名降到 $O(N)$ | 绝对保证 | 同上 |
| $OM(m)$（15.3.4） | 同步（拜占庭将军） | 拜占庭，$N > 3m$ | $m+1$ 轮 | $O(N^{m+1})$（对叛徒数指数） | 绝对保证 | 绝对保证 |
| PoW / PoS（区块链） | 开放网络，无固定成员 | 经济假设（算力/权益多数诚实） | 按区块（分钟～小时） | 全网广播 | 概率性（$k$ 次确认后失效概率 $\sim 2^{-k}$） | 概率性 |
15.5.2 “共识的成本”：为什么不能把它用在热路径上
- 延迟下界 ≈ 1–2 个 RTT 起：要形成”多数派确认”，消息必须至少跨网络一个来回才能真正成立（Paxos 的两阶段 = 2 RTT；PBFT 的三阶段 ≈ 3 RTT；带稳定 leader 与流水线时可以把每个请求摊薄到 ~1 RTT，但首字节延迟仍受 RTT 支配）。因此跨数据中心的共识写入延迟通常是几十到几百毫秒，与”本地内存访问的百纳秒”相差 6 个数量级。
- 吞吐受限于”多数派往返”：所有写入都要经过 leader + quorum，无法像无主复制那样并行写任意节点；PBFT 还要额外付出 $O(N^2)$ 的消息与密码学运算。
- 结论（本讲最重要的工程判断）：共识只应该用在”低频但关键”的决策上。真实系统中的用法几乎完全一致：
- 配置变更 / 元数据：ZooKeeper（Zab）、etcd（Raft）、Consul（Raft）——存的是”谁是 leader”“成员列表”“锁的持有者”这类小数据；
- 领导者选举 / 故障转移：Raft 的选举、HDFS/YARN 的 HA、Kubernetes 的控制器（通过 etcd 的 watch + CAS）；
- 跨分片事务：Spanner（Paxos 组 + TrueTime 提交等待）、CockroachDB、TiDB（Raft 组 + 分布式事务）；
- 复制状态机的日志定序：Kafka 的 controller、各类分布式数据库的日志提交。
- 而不是：每条用户请求、每次 KV 读写、每次指标上报。
- “共识的复兴”与它的反面：正因为共识昂贵，过去十年出现了两条相反的路：
- 把共识做便宜：Raft（易实现、可流水线）、Multi-Paxos（批量决议）、HotStuff（$O(N)$ 消息 + 门限签名）、以及把共识组件化（etcd/Consul/ZooKeeper 成为”标准件”）；
- 干脆绕开共识：当数据操作可交换（commutative）时根本不需要定序 —— CRDT（Conflict-free Replicated Data Type） 用”可交换、可结合、幂等”的合并函数（G-Counter、PN-Counter、OR-Set、LWW-Register）实现无需协调的最终一致；因果一致性（Causal Consistency） 只要求”有因果关系的操作有序、并发操作可任意序”，用向量时钟/版本向量实现，不要求全序、也就不要求共识。这类系统（Riak、Redis CRDT、Antidote、部分 Dynamo 系系统）换来的是低延迟与分区可用性，代价是”不能表达需要全局定序的业务”（如唯一性约束、跨对象不变量）。
- 判断准则：只有当”多个副本必须对同一件事的顺序达成一致”时，才需要共识；如果操作天然可合并（加计数、加集合、并集），就用 CRDT；如果只需要”因果有序”，就用因果一致性 + 版本向量（详见本笔记”一致性模型”与”时间与顺序”两章）。
15.5.3 可解性矩阵（一张表看懂”该用什么模型”）
| 系统模型（时间假设） | 故障模型 | 算法类型 | 共识可解性 | 代表算法 / 系统 |
|---|---|---|---|---|
| 同步（延迟/时钟/步骤都有界） | crash-stop | 确定性 | 可解（$f+1$ 轮，$f<N$） | 讲义 Flooding；共享总线多处理器 |
| 同步 | 拜占庭 | 确定性 | 可解（$N \ge 3f+1$；签名下 $N \ge f+2$） | $OM(m)$、$SM(m)$ |
| 部分同步（最终有界） | crash-stop | 确定性 | 可解（安全性无条件；活性在同步期） | Paxos、Raft、Zab、Viewstamped Replication |
| 部分同步 | 拜占庭 | 确定性 | 可解（$N \ge 3f+1$） | PBFT、Tendermint、HotStuff |
| 异步 | crash-stop | 确定性 | 不可解（FLP） | —— |
| 异步 + 完美故障检测器 $P$ | crash-stop | 确定性 | 可解（等价于同步） | Chandra–Toueg |
| 异步 + $\Diamond S$ | crash-stop | 确定性 | 可解（多数正确；$\Diamond S$ 是最弱的） | Chandra–Toueg 轮转协调者共识 |
| 异步 | crash-stop | 随机化 | 可解（以概率 1 终止） | Ben-Or、Rabin（共享硬币） |
| 异步 | 拜占庭（$N \ge 3f+1$） | 确定性 | 不可解 | 需部分同步或随机化（PBFT + 随机化视图变更） |
读表要点：横着看是”模型强弱”，竖着看是”确定性 vs 随机化”与”故障类型”。FLP 只封锁了其中一格（异步 + 确定性 + crash），而工程上的全部智慧都在于”用哪一格来近似现实”：现实网络既不是同步也不是纯异步，而是”大部分时候接近同步、偶尔严重抖动”——这恰好就是部分同步模型，也正是 Paxos/Raft 的立足点。
15.6 关键要点
- 共识的三条性质必须一起记住：终止性（每个正确进程都决定）、一致性（所有决定相同）、合法性（决定值来自提议值）。FLP 违反的是第一条——在它构造的执行里，大家从来没有”不一致”，而是”永远没人决定”。
- FLP 不可能性：异步 + 确定性 + 允许 1 个崩溃（且无故障检测器）⇒ 不存在保证终止的共识算法。 惊人的地方不是”故障太多”，而是一个故障就够；因此加大副本数完全无用。证明结构是：引理 1（不相交调度可交换）+ 引理 2（存在双价初始配置）+ 引理 3（双价配置总能走到另一个双价配置）⇒ 存在一条无限双价路径 ⇒ 永远无人决定。
- FLP 的”1 个故障就够”根源是”故障进程不可区分性”：把某个进程的输入翻转、再让它一开始就崩溃，其余进程看到的执行完全相同——初始配置的”价”因此不可能在一格之间从 0 跳到 1，于是必有双价配置；而”消息可以被无限延迟而不被察觉”（异步性的本质）则让对手可以永远选择”先做别的事”，守住双价分支。
- 要绕过 FLP，必须放松三条假设之一：放松异步（部分同步 ⇒ Paxos/Raft，安全性永远保证、活性尽力而为）、放松确定性（随机化 ⇒ Ben-Or，以概率 1 终止）、或引入故障检测器（$\Diamond S$ ⇒ Chandra–Toueg，而 $\Diamond S$ 也只能近似实现）。 此外，改变故障类型（拜占庭）是另一条正交的轴，它并不让 FLP 消失：$N \ge 3f+1$、$O(N^2)$ 消息、异步下仍不可解。
- 安全性与活性的失败代价不对称：违反安全性 = 数据损坏（不可恢复），违反活性 = 暂时不可用（可恢复）。所以真实系统的设计哲学是”安全性绝对保证 + 活性尽力而为”——这让”在异步网络上造出能用的共识系统”成为可能。共识的代价是 1–2 个 RTT 起的延迟与 $O(N)$–$O(N^2)$ 的消息，因此只用于配置变更、选主、成员管理、跨分片事务这些低频关键决策；可交换的数据操作则用 CRDT + 因果一致性绕开共识。
15.7 常见陷阱与注意事项
- 陷阱：把 FLP 理解成”共识不可能实现”。
- 为什么错：FLP 只否定”同时保证一致与总终止的确定性算法在异步系统中的存在性”。它不否定”安全性永远成立、活性尽力而为”的算法（Paxos/Raft），也不否定随机化算法。
- 正确做法：把 FLP 当作一张代价清单：你必须明确说出”我放弃的是哪一条”。工程界的一句口号很好地概括了 Paxos/Raft 的立场：安全性永远保证，活性在网络表现正常时给出（safety always, liveness when the network behaves）。
- 陷阱：以为”多几个副本 / 更快的网络 / 更好的硬件”能绕过 FLP。
- 为什么错：FLP 的构造只需要一个进程崩溃（而且崩溃者由对手挑），与副本数无关；”更快的网络”只是把延迟上界变小，而异步模型恰恰假设没有任何上界——最坏情况的延迟可以任意长。
- 正确做法：要提高活性，只能改变模型（引入最终同步假设、故障检测器或随机化），而不是提高配置。
- 陷阱：把”终止性”理解成”最终达成一致”。
- 为什么错：一致性与终止性是两条独立性质。FLP 破坏的是”每个正确进程都做出决定“，而不是”大家决定的相同”。
- 正确做法：写协议规格时把三条性质逐条形式化（$\forall$ 正确进程 $\Diamond$ decided；两个决定相同；决定值 $\in$ 提议值集合），并分别给出论证。
- 陷阱：在异步系统里用”超时”当故障检测器，却把它当成完美的。
- 为什么错：Lecture 5/6 的结论是完整性与准确性不可兼得（否则就能解共识）；超时太短会误判（准确性差，可能引发不必要的重配置、甚至脑裂），太长则活性差。
- 正确做法：明确你的检测器是 $\Diamond P$ / $\Diamond S$ / $\Diamond W$ 中的哪一个，并接受”最终准确”这个只在未来成立的承诺；用自适应超时（如 Φ 累加检测器）、怀疑机制（suspicion + incarnation）来降低误判代价。
- 陷阱：把”签名消息下 $N \ge f+2$”套用到异步 BFT 上。
- 为什么错：$f+2$ 是同步、拜占庭将军问题（口头/书面消息）这一形式化的结论；在异步/部分同步的 BFT 共识里，还需要 quorum 交集来提供安全性，因此 $N \ge 3f+1$ 依然是硬下界（PBFT、Tendermint、HotStuff 全部如此）。签名只能防伪造，不能提供”何时可以安全推进”。
- 正确做法：区分”消息能否被伪造”（签名解决）与”需要多少票才能推进”（quorum 大小，由故障模型与时间模型决定）。
- 陷阱：以为共享硬币（common coin）是”免费”的。
- 为什么错：共享硬币本身是一个同步原语：它要求所有进程对”第 $r$ 轮的随机位”取得同一个值，通常要用门限签名或可验证秘密分享（VSS）实现，需要额外的通信轮次，并且在纯异步模型下也不是随手可得。
- 正确做法：比较”私有硬币（$2^{\Theta(n)}$ 期望轮数、无额外原语）”与”共享硬币（$O(1)$ 期望轮数、需要密码学与额外轮次）”的总代价（轮数 × 每轮成本 + 原语成本），而不是只比轮数。
- 陷阱：把”以概率 1 终止”当成”保证终止”。
- 为什么错：概率 1 终止只排除了”永不终止”这一零测集事件；任何有限轮之后都仍有正概率还没终止，而且分布是重尾的（本讲实验：私有硬币在 $N=7,f=2$ 时平均 14.77 轮、最长 79 轮，$N=9,f=2$ 时最长 245 轮）。
- 正确做法：工程实现里要设置”最大轮数 + 退避 + 上层超时/重试”，并把”极少数慢路径”纳入 SLO（尾延迟 p99.9 才是用户体验）。
- 陷阱：同步 Flooding 里的两个细节错误。
- 错法一：只跑 $f$ 轮（少了”把最后一个缺口补上”的那一轮）⇒ 15.4.1 实验 2a 直接违反一致性；错法二：用”最小值”作为决定规则，或忘记”$f$ 必须已知”。此外，若实际崩溃数超过 $f$，$f+1$ 轮的归纳链就断了（实验 3）。
- 正确做法：严格按 $f+1$ 轮执行；决定规则取”值集合的确定性函数“（讲义用”最小编号提议者”）；把”$f$ 是上界且真实成立”写进假设，并让运维监控实际故障率是否越界。
15.8 思考题（带答案）
Q1（计算题） 在同步 Flooding 共识中取 $N=7$、$f=2$，假设每条消息最多携带 $N$ 个提议值。求：(a) 需要多少轮？(b) 总消息条数是多少？(c) 总共传输多少个”提议值”？(d) 如果只跑 $f$ 轮会发生什么？请结合本讲实验说明。
答案：
- (a) 轮数 $= f+1 = 3$。
- (b) 每轮每个进程向其余 $N-1=6$ 个进程各发 1 条 ⇒ 每轮 $7 \times 6 = 42$ 条，总共 $42 \times 3 = 126$ 条；与公式 $O(N^2 f) = 7^2 \times 2 \approx 98$ 同量级（精确值 $N(N-1)(f+1) = 126$）。
- (c) 每条消息最多含 $N=7$ 个值 ⇒ 最多 $126 \times 7 = 882$ 个值；即 $O(N^3 f)$。
- (d) 只跑 $f=2$ 轮时，”最后一个缺口”来不及补上，两个正确进程可能掌握不同的值集合 ⇒ 决定值不同。15.4.1 实验中 $N=3,f=1$ 的”实验 2a（1 轮）对比 2b（2 轮）”就是最小实证：少一轮 ⇒ $p_1$ 决定 1、$p_2$ 决定 0；补上那一轮 ⇒ 两人都决定 1。
Q2（错误直觉题） 有同学说：”FLP 说异步下 1 个故障就解不了共识，那我们把副本从 3 个加到 5 个、再把网络升级到 100 Gbps，问题不就解决了吗？”请指出这个想法错在哪里，并说明正确的做法是什么。
答案：错的根源是把”配置”当成了”模型”。
- FLP 的结论是”不存在任何确定性算法”——它不依赖副本数：证明里只用了 1 个崩溃进程，而且崩溃者可以自由选择（让”输入值翻转导致价跳变”的那个进程沉默）。把 $N$ 从 3 加到 5、500、5000，都无法消除”慢与死不可区分”这一认识论困境；恰恰相反，$N$ 越大，”某个进程恰好卡住”的概率越高。
- “更快的网络”只降低平均延迟，而异步模型允许任意长的延迟（GC 停顿、路由抖动、虚拟机迁移、跨洲链路拥塞都可能造成秒级甚至分钟级停顿），FLP 的最坏执行正是建立在”某条消息被无限延迟”之上的。
- 正确做法：改变模型而不是配置——(1) 采用部分同步假设并用超时推进（Paxos/Raft：安全性永远保证、活性尽力而为）；(2) 采用随机化（Ben-Or/Rabin：以概率 1 终止）；(3) 引入故障检测器（$\Diamond S$：最终能识别出”谁是慢、谁是死”）。三者都是”用额外的假设换取可能性”，而不是”用更多的机器换取可能性”。
Q3（概念题） Ben-Or 的阶段 1 为什么采用”收到的 $n-f$ 条估计全部一致“（unanimity）而不是”严格多数“？如果改成严格多数，会破坏哪一条不变式？阈值 $D$ 与 $A$ 之间的不等式 $D-f \ge A$ 又是干什么的？
答案：
- $D-f \ge A$ 是传播性（propagation）要求：决定者 $p$ 看到 $\ge D$ 张 $v$ 票；任何其他正确进程 $q$ 最多漏看 $f$ 个发送者（它只收 $n-f$ 条），因此至少看到 $D-f$ 张 $v$ 票。要保证 $q$ 也把估计锁定到 $v$（否则两人的估计分叉，未来可能决定出不同的值），就必须 $A \le D-f$。取 $D=f+1, A=1$ 正好取等。
- 为什么阶段 1 用 unanimity：它保证同一轮至多一个值能获得选票（不变式 I）：两个不同值的一致集合互不相交，每个都需要 $n-f$ 个进程的估计一致，于是发送者总数 $\ge 2(n-f) \ge n+1 > n$，矛盾。有了这条不变式，”$A=1$ 的采纳规则”才有明确语义（不会出现”同时看到两个值的票、不知道该采纳哪个”的情形）。
- 改成严格多数会怎样：当实际崩溃数 $c < f$ 时（存活进程多于 $n-f$，各进程看到不同的子集），可能两个值同时各获多数（两个多数集合的大小之和可以不超过发送者总数），于是阶段 2 里同时出现两个值的票，传播性论证失效；补救办法是把采纳阈值提高到 $A \ge n-D$，而这要求 $2D \ge n+f$，把可容忍的 $f$ 压到 $f \le 2$（$n$ 为偶数时）。结论：阈值不是可以随意挑选的参数，而是一组必须联合成立的不等式——这是分布式算法设计中极常见、也极容易被忽视的一类错误。
Q4（推演题） 在 $N=3, f=1$ 的拜占庭将军场景中，请写出”忠诚中尉的视角”（即”指挥官告诉它的值”与”同伴告诉它的值”）在下列三种场景下的取值，并说明为什么任何确定性算法都必然失败：(i) 指挥官忠诚下令 1、中尉 $p_2$ 叛徒谎报 0；(ii) 指挥官是叛徒、对 $p_1$ 说 1、对 $p_2$ 说 0，两名中尉都忠诚；(iii) 指挥官忠诚下令 0、中尉 $p_2$ 叛徒谎报 1。进一步说明：加上不可伪造的签名后，为什么同样三个场景就不再是问题。
答案：
- (i) $p_1$ 的视角 $=(1, 0)$；由 IC2（指挥官忠诚 ⇒ 必须服从）⇒ 算法在此视角必须输出 1。
- (iii) $p_1$ 的视角 $=(0, 1)$；由 IC2 ⇒ 算法在此视角必须输出 0。
- (ii) $p_1$ 的视角 $=(1,0)$、$p_2$ 的视角 $=(0,1)$（两人都忠实转发）；由上面两条，$p_1$ 输出 1、$p_2$ 输出 0 ⇒ 违反 IC1。
- 为什么是”任何”算法：一个确定性算法就是从”视角”到”决定”的函数；视角只有 4 种 $(c,p) \in \{0,1\}^2$，因此全部算法只有 $2^4 = 16$ 种。逐一检验可知这 16 种全部至少违反 IC1 或 IC2（本讲 15.4.3 的实验 2 正是这个穷举，输出
16/16 种算法都至少违反 IC1 或 IC2 中的一条）。直观地说：$p_1$ 在场景 (i) 中看到的证据与场景 (ii) 完全相同，却被要求做出不同的决定——不可区分性使任何算法都无能为力。 - 签名之后为什么可以：有了不可伪造的签名，$p_1$ 与 $p_2$ 可以把”指挥官亲笔签名的命令“互相转发作为证据。在场景 (ii) 中，两人各自都会看到”$p_0$ 签名的 1”与”$p_0$ 签名的 0”两份互相矛盾的命令 ⇒ 直接判定指挥官是叛徒，于是都回退到默认值 RETREAT ⇒ 两人一致；在场景 (i)/(iii) 中，叛徒中尉无法伪造指挥官的签名，忠诚中尉只会看到一份真实签名 ⇒ 服从指挥官。这就是”签名把 $N \ge 3f+1$ 降到 $N \ge f+2$”的机制（15.4.3 实验 3 验证了 $N=3,f=1$、$N=4,f=2$、$N=5,f=3$ 在签名下都能达成一致；但再次提醒：异步 BFT 仍需 $N \ge 3f+1$）。