Paxos | Codeboy's Blog

形式陈述

Basic Paxos 在异步消息传递系统与崩溃故障模型中，为一个共识实例选择单一值。安全性允许消息任意延迟、丢失、重复或乱序；节点不会伪造消息内容，也不会表现 Byzantine 行为。活性则另需重传最终成功、正确节点持续取步等公平性条件。

协议使用全序且唯一的 ballot 编号。一个 acceptor 在某个 ballot 记录提案，称为 accepted；同一值被一个quorum接受，称为 chosen；learner 获知 chosen 事实后，才称该值为 learned。accepted 是局部状态，chosen 是跨节点事实，learned 是知识状态，三者不能混用。

角色与持久状态

Proposer 发起 ballot 并提出值，acceptor 作出承诺和接受记录，learner 收集证据得知结果。同一进程可以兼任多个角色，角色划分不改变协议逻辑。

每个 acceptor 维护两项关键状态：它承诺过的最高 ballot，以及自己编号最高的 accepted proposal (ballot,value)。在 crash-stop 模型中，停止的 acceptor 永不重新参与，状态不必经过重启；在 crash-recovery 模型中，这两项必须先写入稳定存储再回复。若重启节点遗忘 promise，便可能再次接受旧 ballot；若遗忘 accepted 记录，新 Phase 1 quorum 便可能漏掉已 chosen 值。

Phase 1：发现必须继承的值

Proposer 选择新 ballot $b$ ，向 acceptor 发送 prepare(b)。Acceptor 在尚未承诺更高 ballot 时记录对 $b$ 的 promise 并回复，同时附上自己最高 ballot 的 accepted proposal；此后它拒绝编号小于 $b$ 的 accept 请求。重复的 prepare(b) 可以重发同一承诺，不改变状态。

当 proposer 收到一个 quorum 的 promise 后，它检查这些回复。若没有 acceptor 报告已接受值，可以选择任意合法输入；否则必须采用回复中 ballot 最高的 accepted value。这个选择规则不是优化策略，而是连接新 ballot 与旧安全事实的桥梁。

Phase 2：接受与选择

Proposer 向 acceptor 发送 accept(b,v)。尚未承诺更高 ballot 的 acceptor 可以记录 (b,v) 并回复 accepted。值 $v$ 一旦在 ballot $b$ 被某个 quorum 接受，就已经 chosen；以后即使原 proposer 崩溃，这个事实也不会被撤销。

Learner 可以由 proposer 通知，也可以直接收集 acceptor 的 accepted 消息。通知方式影响消息数与故障恢复，却不改变 chosen 的定义。

直觉

安全不变量与归纳证明

Paxos 的核心不变量是：若值 $v$ 已在 ballot $m$ chosen，则每个 ballot $n>m$ 中被发出的 proposal 都携带 $v$ ，因而更高 ballot 只能选择 $v$ 。

对 $n$ 作 ballot 归纳。假设 $m<n$ 中 $v$ 已 chosen，且从 $m+1$ 到 $n-1$ 的所有 proposal 都携带 $v$ 。ballot $n$ 的 Phase 1 quorum 与选择 $v$ 的旧 Phase 2 quorum 相交，因此至少一个回复报告 ballot 不小于 $m$ 的 accepted proposal。若回复中的最高 accepted ballot 正是 $m$ ，其值为 $v$ ；若更高，归纳假设说明其值仍为 $v$ 。proposer 必须选择这个最高记录的值，所以 ballot $n$ 也只能发出 $v$ 。由此两个不同值不可能分别 chosen。

这个论证依赖 Phase 1—Phase 2 quorum 交集、ballot 单调 promise、最高 accepted 记录和 proposer 的继承规则。交集本身不够：若 $A,B$ 在 ballot 5 接受 $x$ ，共同节点 $B$ 却能在 ballot 8 无条件接受 $y$ ，则 $B,C$ 仍可形成相交多数并选择 $y$ 。

Paxos 三个 acceptor 的 ballot 5 与 ballot 8 轨迹，展示 quorum 选择 x 以及新 proposer 继承最高已接受值 — Paxos：ballot 8 必须继承 x

例子与边界

三个 acceptor 的轨迹

设 acceptor 为 $A,B,C$ ，多数 quorum 大小为二。值 $x$ 已被 $A,B$ 在 ballot $5$ 接受，因此 chosen。新的 proposer 以 ballot $8$ 联系 $B,C$ ： $B$ 回复 (5,x)， $C$ 没有旧记录。新 proposer 即使原想提交 $y$ ，也必须在 Phase 2 提议 $x$ 。

若 $A$ 随后 crash-stop， $B,C$ 仍可形成 quorum 并继续协议， $A$ 不会回来作出与旧状态矛盾的响应。若允许 $B$ 重启并重新参与，它却忘记 accepted 记录，则 $B,C$ 的回复会错误显示“没有旧值”，从而允许 $y$ 被选择；这说明稳定存储是 crash-recovery 的安全条件，而不是 crash-stop 定义自动附带的要求。

推论与应用

进展条件与边界

纯异步执行中，两个 proposer 可以不断以更高 ballot 抢占对方，使系统永远没有值 chosen。此执行没有违反 agreement：它只说明安全与进展是不同性质。通常要让某个正确 proposer 最终稳定地主导 ballot，并保证它与一个 quorum 之间的重传最终成功；最终出现的时间界与稳定领导者选举是实现这组条件的常见办法。Paxos 因而不反驳FLP 不可能性。

本页只覆盖单实例 Basic Paxos。Multi-Paxos 为许多日志槽位复用稳定 leader 和 Phase 1；复制日志还要定义缺槽、提交位置、应用位置、客户端去重和成员变更。Byzantine 节点、动态 quorum 与磁盘损坏也需要不同协议或额外假设，不能从 crash-fault 安全证明直接推出。

参考资料

Leslie Lamport, “The Part-Time Parliament,” ACM Transactions on Computer Systems 16(2), 1998, pp. 133–169，Full paper, ballots, quorums, and consistency of ledgers。
Leslie Lamport, “Paxos Made Simple,” ACM SIGACT News 32(4), 2001, pp. 51–58，§2, choosing and learning a value; §3, state-machine implementation。

形式陈述 ​

角色与持久状态 ​

Phase 1：发现必须继承的值 ​

Phase 2：接受与选择 ​

安全不变量与归纳证明 ​

三个 acceptor 的轨迹 ​

进展条件与边界 ​