形式陈述

Paxos 是异步消息传递、崩溃故障模型下选择单一值的共识协议族。基本 Paxos 使用相交的多数派 quorum 和递增 ballot。Phase 1 中 proposer 请求 acceptor 承诺不再接受更小 ballot，并收集其已接受的最高 ballot 值；Phase 2 必须提议这些回复中最高 ballot 的值，若无则可选新值。一个值被 quorum 接受即被选择。quorum 交集与“继承最高已接受值”共同保证任何两个被选择值相同。

直觉

新一轮领导者先询问多数派过去可能已经承诺了什么，再继续最先进的已有决定；任何两个多数派相交，所以已成形的决定不会被后续轮次覆盖。

例子与边界

少数 acceptor 崩溃时，只要仍能形成多数派，协议可继续。多个 proposer 竞争可能反复抢占而不进展，但安全性仍保持；活性通常依赖最终稳定领导者和足够及时的通信。Paxos 容忍崩溃和消息延迟、丢失、重复，不自动容忍 Byzantine 篡改。Multi-Paxos 在稳定 leader 下复用第一阶段，为日志每个槽位执行后续共识。

推论与应用

Paxos 是复制状态机、配置服务和一致日志的基础。理解它必须分开 safety 与 liveness：前者在任意异步执行中维持，后者依赖附加公平性或最终同步条件。

参考资料

• 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。