分布式系统 09：多数派交叉与单值 Paxos

A、B 已经接受 X，C 尚未收到消息，提议者又失联了。另一个提议者向 B、C 发起 Y，B 能否再接受？只规定“得到多数票即可成功”，两个值都可能拿到两票。禁止每个节点再次投票也不够：第一轮的票分散后，所有节点可能永久停在不同候选值上。

第 08 篇区分了安全性与活性。单值 Paxos 允许不断发起新一轮尝试，同时限制后续提案的取值，使所有获得多数接受的提案携带同一个值。MIT 6.5840 的 Paxos 讲义从多数派和两阶段进入这一问题；本篇以 Lamport 的原论文及课程精确伪代码为依据，推导约束，并用有限消息调度检查违反约束的后果。

MIT Paxos 讲义。

一次共识的模型和三个角色

本篇只有一个共识实例，成员固定为 A、B、C，法定集合 quorum 取任意两个 acceptor。一般多数派大小为 floor(N/2)+1。进程遵守协议，消息可以延迟、重复或丢失，但不被伪造；进程可以崩溃恢复，持久状态须在恢复后保留。这些约束不覆盖拜占庭行为和磁盘状态永久丢失。

proposer 生成提案，acceptor 持有承诺和接受记录，learner 根据接受证据得知结果。角色可以在同一进程中合并，三者仍承担不同职责。备份节点数量不等于角色数量，proposer 自己收到两个回复也不意味着所有 learner 都已得知结果。

一个提案写成 (n,v)：n 是全局唯一且有全序的轮号，v 是值。不同提议者不能复用同一个 n；同一轮一旦发出提案，不能再改 v。工程上可以使用 (递增计数器, proposer标识) 排序，但重启不能复用旧编号，标识也不能随意分配给另一个仍可能存活的进程。单独依赖墙钟无法无条件保证这些性质。

accepted、chosen、learned 表示三个不同事实。A 接受 (1,X) 是一条局部记录。A、B 都曾接受同一个 (1,X)，X 才在这一轮 chosen。learner 实际收到足够的接受证据，才 learned。若两个接受回复都丢失，X 仍已 chosen，learner 却可能完全不知道。Paxos Made Simple，§2.1–2.3。

同一提案从接受到获知，依赖的是两种证据：接受历史和实际送达的回复。图中箭头沿示例时间向下，回复丢失不会撤销已经形成的多数派。

flowchart TD
    A["A 接受 1,X<br/>accepted：一票"] --> B["B 也接受 1,X<br/>chosen：A/B 两票"]
    B --> C{"接受证据是否送达 learner？"}
    C -->|足够证据送达| D["learned<br/>learner 得知 X 已选"]
    C -->|回复全部丢失| E["X 仍 chosen<br/>learner 尚未知晓"]

chosen 是关于执行历史的性质。节点后来接受了更高轮提案，或覆盖了本地最高接受记录，都不会撤销过去已经形成的多数派。实验因此必须保留独立票据历史，不能仅检查三个节点最后各存了什么。

多数派交叉还需要承诺

三节点系统的任意两个多数派必定相交：A/B 与 B/C 共享 B。交叉提供了一条传递约束的路径，却没有规定 B 应该传递什么。若 B 随时把 X 换成 Y，多数派仍然交叉，安全性仍然失败。

每个 acceptor 保存两个有不同用途的状态：promised 是承诺不再接受更低轮的门槛；accepted 是已经接受的最高轮号和值，允许为空。门槛可能已经升到 9，而接受记录仍是 (3,X)。后来的提议者必须区分这两种信息，否则会把一次没有产生提案的 Prepare 当成已有值的证据。

本篇选择 MIT 课程的完整变体。其 Prepare 要求 n > promised；Accept 允许 n >= promised，成功时也把 promised 提升到 n。该 acceptor 不必先收到本轮 Prepare，就可以接收本轮 Accept。以下伪代码中的“持久化”表示在成功回复前，该次更新已经满足崩溃恢复契约。

Prepare(n):
    if n <= promised: reject
    persist promised = n
    reply promise(n, accepted)

Accept(n, v):
    if n < promised: reject
    persist promised = n, accepted = (n, v)
    reply accepted(n, v)

重复 Prepare 可以被这个版本拒绝，proposer 在收不到足够回复时改用更高轮重试；也可以另外设计同轮幂等回复，但必须连同发送方的去重逻辑一起定义。回复无论重传多少次，都只能按 acceptor 身份算一票。MIT 精确伪代码。

1998 年论文的 Basic Protocol 列出了另一套更严格的接收条件和发送集合。不能从一个版本取 Accept 的判断条件，再从另一个版本取不更新承诺的状态动作。2015 年，Lamport 在出版目录中记录过读者误读《Paxos Made Simple》某句歧义文字而产生错误实现的情况；作者没有公开指出具体句子，要求实现者参考精确协议。那条说明不等于 Paxos 安全性被推翻。The Part-Time Parliament，§2.3、作者补充说明。

Prepare 决定本轮可以提出什么

proposer 选取新轮号 n，向 acceptor 发送 Prepare。只有收到本轮、来自不同成员的多数成功 promise 回复后，才有资格进入第二阶段。拒绝回复可以提示更高门槛，但不计入成功 quorum。

成功回复中，只要有人报告了 accepted，本轮就必须采用其中 accepted 轮号最高的值。若所有成功回复都没有接受记录，才可以自由采用自己的候选值。比较对象是 accepted 的轮号；最高 promise、最多相同值、最大业务版本和最早到达的回复都不能代替它。

选值后发出固定的 (n,v)。acceptor 按接收条件决定是否接受；收到同轮同值的多数接受证据后，learner 得知 v chosen。新出现的高轮可能在两个阶段之间打断本轮，因此 phase1 成功并不保证 phase2 也成功。旧提案被拒绝时提高轮号重试，重试又需要重新收集信息并执行选值规则。

这条成功路径把 proposer 与 learner 合并为 P，只画三节点中的多数派 A/B。时间从上向下；B 接受时已形成多数派，P 收到足够回复后才得知结果。每条成功回复都在相应状态持久化之后发出。

sequenceDiagram
    participant P as P：提议与学习
    participant A as A：acceptor
    participant B as B：acceptor
    P->>A: Prepare(n)
    A-->>P: promise(n, accepted)
    P->>B: Prepare(n)
    B-->>P: promise(n, accepted)
    Note over P: 成功 promise 达多数<br/>取最高 accepted 的值 v<br/>全空才自由选值
    P->>A: Accept(n,v)
    A-->>P: accepted(n,v)
    P->>B: Accept(n,v)
    Note over A,B: B 接受后，A/B 已形成多数派<br/>v 已 chosen
    B-->>P: accepted(n,v)
    Note over P: 两条接受回复送达<br/>P learned v

为什么只有一票的旧值也要影响新轮？因为新提议者看不到全部旧消息，某条旧 Accept 可能还在途中；phase1 完成的时刻，无法证明它以后不会补齐旧多数派。承诺限制将来的接受行为，accepted 记录提供已经发生过的事实，两者合在一起才足以约束选值。

后续轮次为何不能选出另一个值

安全性要证明：如果值 X 在轮 m 获得接受多数派 C，任何其他 chosen 提案也只能携带 X。只证明“下一轮查看到已选值”不够；系统既没有一个全局 chosen 标志，也不保证轮号大小等于实际完成顺序。

取任意 n > m，对发出的更高轮提案做强归纳。假定 m 与 n 之间的所有已发提案都携带 X，考察 n 的 phase1 quorum Q。多数派交叉给出某个 a ∈ C∩Q。为了让轮 m 在 C 中取得所有票，a 必须接受 (m,X)。它一旦成功承诺 n，就不会再接受 m，所以这次接受必然发生在它回复 n 的 promise 之前。

a 的回复因此包含一个 accepted 轮号 k，且 m <= k < n。如果 k=m，值就是 X；如果 k 更大，由归纳假设也只能是 X。Q 中最高 accepted 轮号 j 至少为 k，同样处在 [m,n)；其值仍为 X。轮 n 按选值规则只能发出 (n,X)，归纳完成。

这里的“轮 m 获得多数派”可以晚于轮 n 的 phase1。证明只要求交叉点 a 的那一票先发生，不要求 C 的所有票都已经到齐。这个区别正是高轮先完成、低轮晚补票时仍然安全的原因。任意两个 chosen 轮号取小者为 m、大者为 n，便排除了异值；同轮异值则由唯一轮号及单轮单值约束排除。The Part-Time Parliament，§2.1 的 B1–B3、Lemma 与 Theorem1。

全空回复也有精确含义：若过去某低轮已 chosen，交叉点本应报告不低于该轮的 accepted，因此不可能得到这样的全空 quorum；若旧消息未来试图补齐低轮多数派，交叉点的 promise 又会阻止它。它不表示“全系统从未有节点接受过值”。

一条消息交错与错误选值

A、B、C 初始都没有接受记录。P、Q 交替发起三个轮次，消息交付按下列顺序控制。

时刻	动作	已发生的接受
t1	轮1向A/B完成Prepare，提出X，只交付给A	A:(1,X)
t2	轮2向B/C完成Prepare，提出Y，只交付给C	C:(2,Y)
t3	轮3向A/C完成Prepare	收到(1,X)与(2,Y)
t4	轮3向A/C发送选出的值	轮3形成多数派
t5	把此前延迟的轮2 Accept(Y)交付给B	轮2的B/C也形成多数派

t3 时尚未有值 chosen。正确规则仍然选 Y，因此两个形成多数派的轮次都选择 Y。若错误地取最低 accepted，t4 会 chosen X，t5 又 chosen Y。B 没参与轮3 Prepare，仍能接收轮2消息；仅观察新轮的多数派会漏掉这个冲突。

两条执行只改变轮3的选值规则。t5 的轮2多数派由 B 的新接受和 C 在 t2 留下的历史接受组成；C 此时已经更新到轮3，也不会删除那张历史票。

flowchart TD
    R["t3：轮3收到 A/C 回复<br/>A 报 1,X；C 报 2,Y<br/>B 未参与轮3 Prepare"]
    R -->|正确：取最高轮2| H["t4：A/C 接受 3,Y<br/>轮3 chosen Y"]
    R -->|错误：取最低轮1| L["t4：A/C 接受 3,X<br/>轮3 chosen X"]
    H --> H2["t5：迟到 2,Y 交付给 B<br/>B 新票 + C 旧票<br/>轮2 chosen Y"]
    L --> L2["t5：迟到 2,Y 交付给 B<br/>B 新票 + C 旧票<br/>轮2 chosen Y"]
    H2 --> OK["两轮均为 Y<br/>本历史无冲突"]
    L2 --> BAD["历史中 X 与 Y 均 chosen<br/>安全性冲突"]

此后把轮1的延迟 Accept(X)交付给 B，它会因已承诺轮2而拒绝。协议没有取消网络中所有旧消息，它通过节点状态使不再允许的消息失效。

崩溃恢复必须保留哪些状态

只持久化已经接受的值不能代替承诺。假设轮1在 A/B 完成 Prepare，两个 X 的 Accept 都延迟；轮2在 B/C 完成 Prepare，只让 C 接受 Y。此时 B 没有 accepted，却已经承诺轮2。若 B 重启丢掉 promise，它会和 A 一起接受迟到的轮1 X，之后再和 C 接受轮2 Y，两个值均 chosen。正确恢复 promise2 时，B 会拒绝 X。

反过来，只保存 promise 也不够。轮1已经在 A/B 接受 X，learner 的回复全部丢失。若 B 重启保留 promise1 却丢掉 accepted，轮2向 B/C Prepare 会收到两个空记录，错误地自由选择 Y。B/C 再接受 Y 就破坏了已经 chosen 的 X。

因此 promise 与 accepted 都必须跨故障保留，成功回复前完成相应持久化。accept 更新两者时，还要避免崩溃产生一个协议不允许的恢复组合。文件写入、同步、校验和恢复记录属于存储实现责任；本篇的内存模型只展示丢状态造成的逻辑后果，不声称验证过断电或真实磁盘原子性。Paxos Made Simple，§2.5。

多数派可用为什么还不保证结束

A、B、C 都正常时，P 可以用轮1完成 Prepare，Q 随即用轮2抢先提高门槛；P 的 Accept 被拒绝后换轮3，Q 又换轮4。若调度一直让双方在对方 phase2 前完成更高轮 Prepare，所有节点持续运行，仍没有提案得到足够接受。

超时会触发重试，却不能证明竞争已经结束。常见进展安排是让一个稳定提议者持续负责、其他提议者最终停止抢占，并使它与某个多数派之间的消息最终能够交付、处理和重传。这依赖额外的时序与选主条件，与第08篇的异步共识边界一致。若多数派长期不可达，可以继续保安全，却无法保证产生新决定。Paxos Made Simple，§2.4。

唯一活跃 proposer 便于推进，协议安全性仍须承受不同轮号的 proposer 并发。一次实验中三种调度都结束，只说明那些有限历史结束，无法据此证明所有允许执行都终止。

运行有限调度实验

代码位于仓库 examples/distributed-systems/paxos09/main.go，仅使用 Go 标准库。它显式调用 Prepare、Accept 和模型恢复，不开启网络端口、不杀进程，也不写模拟持久化文件。A/B/C 的可变状态与只增不减的历史票据分开保存。

go run examples/distributed-systems/paxos09/main.go
go run examples/distributed-systems/paxos09/main.go -scenario max
go run examples/distributed-systems/paxos09/main.go -scenario promise -mutate
go run examples/distributed-systems/paxos09/main.go -scenario accepted -mutate

默认运行包括三条正常历史、对应的三条错误历史以及回复校验。正常模式应没有冲突；错误模式分别采用最低 accepted、丢 promise、丢 accepted，历史检查器应各发现 X/Y 多数派。默认驱动器把“错误被成功检出”作为负例通过条件；单独加 -mutate 则应打印冲突并以程序退出码1结束。go run 自身可能把程序退出码包装在 exit status 文本中，不能据 shell 返回值反推所有程序细节。

检查器按 (ballot,value) 分组，按 acceptor 身份去重，只在同组至少两票时认定 chosen。learner 另存实际交付给它的回复，因而“历史已chosen、learner未知”能够同时出现。辅助检查还限制了 phase1 少数票、重复回复、错轮回复、未知成员，以及未先收到 Prepare 的 C 接受高轮后是否提升 promise。

本地默认运行完成了三条安全历史及三种冲突反例，回复去重、轮号匹配和 Accept 提升 promise 的检查通过；go vet 和带 -race 的默认运行也通过。帮助参数运行成功。另两次单独启动坏参数与变异命令时，进程被系统终止，未观察到预期退出分支，因此不能把它们记为 CLI 验证通过。完整输出与这次运行限制一并保存在附件中。

有限调度没有穷举消息队列，也没有运行形式化模型检查器。研究记录中读取过滚动 TLA+ 示例，但未取得可验证固定提交，未执行 TLC 或 TLAPS；本篇规则由论文与明确的课程变体支撑。

两道推导题

题一：相同值能跨轮凑票吗？ A 只接受 (4,X)，B 只接受 (7,X)，C 没有接受。能否据此认定 X 已 chosen？如果两张回复都到了 learner，判断会改变吗？

不能。两个不同轮次各有一票，都没有形成一个提案的 quorum。回复抵达改变 learner 的知识，不改变原始票所属的提案。协议以后可能仍只能提出 X，但“未来取值受约束”也不等于当前已经持有 chosen 证据。

题二：没人得知结果，能否重新选择？ 轮5的 (5,X) 已被 A/B 接受，所有回复丢失；B 随后处理轮8 Prepare 并返回 (5,X)，C 返回空记录。新提议者希望提出 Y，理由是没有 learner 宣布成功。这是否合法？

不合法。轮5的接受历史已经形成多数派，公告不是 chosen 的成立条件。轮8在 B/C 获得 promise 后必须继承 X；即使实际上轮5只有 B 的一票，新提议者仍要按最高 accepted 规则处理，因为它不能排除迟到消息补齐旧多数派。

单值 Paxos 固定了一次决定的结果。KV 服务需要一串决定，还要处理领导者恢复未完成的日志槽、空洞、重复请求和按序执行。第10篇将把每个日志位置映射到独立共识实例，并继续区分 accepted、chosen 与 applied。

参考资料

• Leslie Lamport，The Part-Time Parliament，ACM TOCS 16(2)，May1998。正文使用作者托管论文中的安全性不变量与精确协议；PDF 自带修订说明：作者PDF。
• Leslie Lamport，Paxos Made Simple，PDF日期2001-11-01，SIGACT News 32(4)，December2001：作者PDF。
• MIT 6.5840，Spring2026：课程日程、Paxos精确伪代码。课程网页为滚动材料，读取日期2026-09-19。
• Lamport 出版目录，第140项中的2015歧义事件说明：Paxos Made Simple补充说明。

证据记录保存逐项论断及核验边界；验证记录保存本地命令与真实输出。