IT 论文精读 · PAPER 44
Leslie Lamport · Microsoft Research · ACM SIGACT News · 2001
2001 年，Leslie Lamport 用大白话重讲了他自己发明的 Paxos——一个让一群分布在各地、彼此只能靠不靠谱的网络通信的计算机，就「某一件事」达成唯一、且永不反悔的一致决定的方法。今天你用的几乎每个大型在线服务背后都有它的影子：数据库怎么选出主节点、一条数据到底写没写、集群里谁说了算——这类「所有机器必须认同同一个答案」的问题，靠的就是 Paxos 这类共识（consensus）算法。
想象一群朋友要靠打电话约同一家餐厅，但电话会随机掉线，有人会突然睡着、过一会儿又醒来（对应机器崩溃重启），消息可能迟到、重复。要求很苛刻：最后大家必须定在同一家，而且一旦定了，就绝不能有人以为定的是另一家。难点在于：没有一个「所有人都信的中心」，消息又不可靠，怎么保证不会出现「一半人以为定了 A、一半人以为定了 B」？（有个前提：这里没人撒谎，机器只会崩溃、不会故意发假消息——会撒谎是另一个更难的问题。）
Paxos 的办法是两轮沟通 + 排队号。谁想提议，先领一个越来越大的号码牌（后领的号一定比先领的大）。第一轮他拿着号去问「过半数」的人：「能答应我吗？」；第二轮才把自己想定的餐厅正式推上去，让过半数人「接受」。一家餐厅被过半数人接受，就算「定了」。
两条规矩顶住了一切。第一条：每个人只认号大的——一旦你答应了 5 号，就不再理睬任何号更小的人。第二条、也是最妙的一条：提议者在第二轮"推自己的餐厅"之前，必须先问一圈；只要有人说"我已经接受过某家了"，他就必须改推那一家、放弃自己原本想定的。
再加上「过半数」这个设计的妙处——任意两拨「过半数」的人，必然至少有一个人重叠。于是只要一家餐厅已经被定过，后来的任何人在问那一圈时，总会撞上那个"重叠的人"、从他嘴里听说这家已定，从而乖乖沿用它。决定因此永远唯一、永不翻案。
这套「先问一圈、再推、认大号、沿用旧值」的规矩，成了几乎所有需要强一致的分布式系统的地基：谷歌的 Chubby 锁服务、Spanner 全球数据库，以及各种数据库的主从选举，骨子里都是它。后来更好懂的 Raft，也是同一套思想的重新包装。
让一群不可靠的机器就一件事达成唯一决定：领个只增的号码牌、先问过半数人一圈、谁号大听谁的；而且在推自己的值之前，必须先沿用别人已接受的值——靠「任意两个过半数必然重叠」，被定过的值就再也翻不了案。诚实说：它出了名地难懂，且只扛机器崩溃、不扛撒谎，纯 Paxos 还会因两人互相抢号而卡住（要靠选一个"领头的"来解决）。
想看两阶段协议的流程图、过半数为何必然重叠、以及它怎么变成真实系统？ → 切到精读版
Paxos 是一个在「消息会丢失、重复、延迟，机器会崩溃重启、但没人撒谎」的异步分布式系统里，让多个进程就单个值达成一致的共识算法。它用提案编号 + 过半数（quorum）两个机制，保证安全性永远成立（最多只有一个值被选定、且选定后不再更改），而把无法与之两全的活性（一定选出某值）交给「选一个领头提议者」来兜底。这篇 2001 年的《Paxos Made Simple》，是 Lamport 对自己 1998 年那篇晦涩的《The Part-Time Parliament》的白话重写，是几乎所有强一致分布式系统（Chubby、Spanner…）的共识内核。
作者 Leslie Lamport（微软研究院）。《Paxos Made Simple》发表于 2001 年 ACM SIGACT News，是他 1998 年论文《The Part-Time Parliament》——用希腊小岛议会作寓言、几乎没人读懂——的极简重述（算法其实早在 1990 年前后就成形）。它上承 Lamport 自己的逻辑时钟（1978）与共识问题、绕开 FLP 不可能性（1985）；下启工业界大量落地（Chubby、ZooKeeper 的 Zab、Spanner），并直接催生了 2014 年以「可理解」为卖点的 Raft。Lamport 也因这一系列分布式工作获 2013 年图灵奖。
分布式系统里最基础的难题之一：一组机器如何就「某一个值」达成一致——比如谁是主节点、日志的下一条该是什么。看似简单，难在环境极端不友好：网络会丢包、乱序、重复；机器会崩溃、重启（重启后还得记得崩溃前的承诺）。人们想要三条铁律：只有被提出过的值才可能被选中；最终只有一个值被选中；没被选中，就不能让谁误以为选中了。
更糟的是理论天花板——FLP 不可能性证明：纯异步下只要有一个进程可能崩溃，就不存在既保证「一定选出结果」又保证「绝不选错」的确定性算法。于是现实的取舍是：安全性（绝不选错）绝不能破，活性（一定选出）可以在网络恢复正常时再兑现。Paxos 正是这一取舍的经典答案。此前虽有两阶段提交等方案，但它们要么无法容忍协调者崩溃、要么会阻塞；Paxos 第一次给出一个能容忍少数崩溃、且被严格证明安全的最小协议。
Paxos 把进程分成三种角色（一个进程可同时兼任）：提议者（proposer）提出候选值；接受者（acceptor）投票；学习者（learner）得知结果。核心规定极简：一个值被"过半数"接受者「接受」，就算被"选定"（chosen）。
用过半数、而非全体，是全篇的关键设计：任意两个过半数集合，必然至少有一个共同成员。这个重叠点像一个「见证人」——它一旦参与过某个决定，就能在后来的询问里把这个决定捅出来，从而不可能有两个不同的值各自凑齐过半数、还互不知情。
每个提案带一个唯一且递增的编号 n。协议分两轮（见图 2）：
prepare(n)。接受者若没答应过比 n 更大的编号，就承诺：今后不再接受编号小于 n 的提案；并回报自己已接受过的、编号最高的提案值（若有）。accept(n, v)。这里的 v 有一条铁规：若任何一份承诺里带回了"已接受的值"，v 必须取其中编号最高的那个；只有当所有人都没回报任何值时，提议者才能填自己想要的值。接受者收到 accept(n,v)，只要期间没答应过更大的编号，就接受它。把上面两条合起来看，第二阶段填值的规则其实是：v = 过半数回报里编号最高的已接受值（若有），否则自选。正是这条「推自己的值前，先问一圈、并沿用已被接受的值」的规则，加上"过半数必重叠"，共同保证了——一旦某值 v 被选定（过半数接受），此后任何更高编号的提案也只会带 v。于是"选定的值唯一、且不可更改"。（论文用一串不变式 P1 / P2a / P2b / P2c 严谨推出这一点；但直觉就是上面这句话。）
每个接受者只要把两样东西写进持久存储：答应过的最大 prepare 编号、已接受的最高编号提案及其值。崩溃重启后，凭这两个数就能恢复之前的承诺、不会反悔——这是容错的关键。
安全归安全，Paxos 会卡活性：两个提议者可能反复抢号——p 用 n1 拿到承诺，q 用 n2>n1 抢先、作废了 p 的第二阶段；p 再用 n3>n2 抢回……如此拉锯，谁也定不下来（这正是 FLP 说的躲不掉的情形）。解法是选出一个"领头提议者"（leader），只让它发提案。领头选举不必完美——选错只影响效率、不影响安全；只要最终有一段时间只有一个稳定 leader，就能定下来。
上面只定「一个值」。真实系统要定的是一长串命令（一份日志）：给日志的每个槽位跑一个独立的 Paxos 实例即可。优化在于——一个稳定的 leader 可以为一整段未来槽位一次性做完第一阶段，之后每条新命令只需第二阶段一个来回，这就是 Multi-Paxos。把它套在「确定性状态机」上（各副本按同一顺序执行同一串命令），就得到状态机复制：一个能容忍少数机器崩溃、对外却像单机一样强一致的服务。这才是 Paxos 在工业界真正的用法。
这是一篇理论论文，没有数据集、没有基准跑分——它的"结果"是一个被严格证明的正确性保证，以及推出它的方式。论文从「安全性到底要什么」出发，一步步逼出 prepare / accept 两阶段是必要且充分的最小机制，证明：在任意消息丢失 / 重复 / 延迟、任意少数接受者崩溃下，安全性恒成立（最多一个值被选定、选定不可更改）；而活性则在「有唯一稳定 leader + 网络最终送达」时达成。它同时坦白 FLP 的边界——纯异步下无法保证一定终止，这不是缺陷、而是理论必然。这种「从需求反推算法」的写法，本身也是它被反复引用、成为教科书范本的原因之一。
Paxos 是分布式共识的奠基算法，几乎定义了"如何在会崩溃的机器上做强一致"这件事。谷歌的 Chubby 锁服务、Spanner 全球数据库、Megastore 等核心系统的共识内核都是 Paxos；ZooKeeper 的 Zab、etcd / Consul 用的 Raft，都是它的近亲或再包装。可以说，今天几乎所有"强一致 + 高可用"的分布式存储，其容错骨架都能追溯到这里。它也是 Lamport 2013 年图灵奖的代表作之一。
① 问题：让一群会崩溃、只能靠不可靠网络通信、但不会撒谎的机器，就单个值达成唯一且不反悔的一致。
② 取舍：受 FLP 限制无法两全——Paxos 让安全性永远成立、活性在网络恢复时兑现。
③ "选定"的定义：一个值被过半数接受者接受，即为选定。
④ 关键设计一：过半数——任意两个过半数必重叠，那个重叠者是防止两值并存的"见证人"。
⑤ 关键设计二：两阶段（prepare/promise → accept/accepted）+ 递增提案编号；接受者只认更大的号。
⑥ 安全的心脏：提议者推自己的值前，必须先问一圈、并沿用已被接受的最高编号值——于是被选定的值此后不可更改。
⑦ 容错细节：接受者只需持久化"最大承诺号"和"最高接受提案"两样，重启不反悔。
⑧ 活性靠 leader：选一个领头提议者破解"决斗抢号"；选举不必完美，不影响安全。
⑨ 实用形态：Multi-Paxos（每槽一个实例、稳定 leader 省掉第一阶段）+ 状态机复制，是工业界真正用法。
⑩ 影响与局限：Chubby / Spanner 的地基、Raft 的前身；但难懂、与落地有鸿沟、只扛崩溃不扛撒谎。