兼职议会与 Paxos

破除误解：Paxos 不是 1998 年才发明的投票器#

第一层误解把发表年当成发明年。兰波特在 1989 年写成这篇寓言体文稿，1990 年投给 ACM Transactions on Computer Systems。审稿人被希腊小岛议会的写法挡住，建议删掉故事、改成普通数学论文。兰波特不肯把幽默感拿掉，稿子因此压了多年。1996 年，巴特勒·兰普森（Butler Lampson）在一篇讲如何用共识构造高可用系统的文章里，把这套协议重新介绍给系统界。

1998 年 5 月，原文几乎按寓言体刊出，卷期是 TOCS 第 16 卷第 2 期，页码 133 至 169。2001 年，兰波特另写《Paxos Made Simple》，去掉议会故事，改用提议者、接受者、学习者三个角色。后文用 2001 年的角色名讲机制，是因为它们已成为通行词汇；安全论证本身属于 1998 年那份 Synod。

第二层误解把 Paxos 读成「多数同意就赢」。多数在这里不是偏好加总。它是一个仲裁集合：任意两个多数必须共享至少一名接受者，好让已被选定的值无法被另一轮提案悄悄换掉。第三层误解把安全性和进展性捆成一句「总能达成共识」。

分布式计算理论 里的 FLP 结果已经划过边界：完全异步、再加一个可能崩溃的进程，就不存在既永远安全、又在所有合法调度下都能终止的确定性协议。

Paxos 没有推翻这条定理。它把「不会选出两个不同的值」写成始终成立的安全性质；把「终将选出一个值」留给额外假设——例如最终有一位提议者能独占一轮、多数接受者最终能与他通信。第四层误解把经典 Paxos 读成拜占庭容错。口头消息与签名消息、以及 \(3f+1\) 那道界，见 拜占庭将军问题。

《兼职议会》里的信使可以迟到、丢失、重复，但不被假定去伪造别人的话；议员可以缺席，但不被假定对两个听众说两套互相矛盾的已接受记录。

那是崩溃与遗漏的模型，不是「节点任意撒谎」的模型。把 Paxos 直接说成区块链里的拜占庭共识，会把故障模型换成另一个对象。

寓言里的议会，协议里的法令#

论文把协议写成爱琴海小岛 Paxos 的议会史。议员经常不在场，所以叫兼职议会。法令必须在这种出缺下仍能形成前后一致的序列。寓言不是装饰。它把工程里最难讲清的假设写成制度：没有全局点名，没有永不丢失的邮路，也没有一位永远在场的议长。

单次决议对应文中的 Synod。一连串编号法令对应整部议会协议，也就是后来文献里的多法令 / Multi-Paxos。本文的对象停在这条发表出来的骨架上：角色、选票、两阶段，以及「选定值不能被替换」的安全声明。这不是 Gray 1978 两阶段提交：那一页的协调者可以阻塞；本页的 Synod 要的是多数派交集上的选定值。从骨架走到可运行的复制日志，还要补领导者稳定、成员变更、磁盘与客户端语义；那是别的对象，见 分布式共识算法 与 etcd 的 Raft。

三个角色：提议、接受、学习#

《Paxos Made Simple》把参与者分成三类。一台机器可以同时扮演不止一种角色。提议者（proposer） 发起一轮选票，带一个全局唯一且可比较的编号。编号通常由轮次与提议者身份拼成，保证两轮不会撞号。提议者不是国王。更高编号的另一位提议者可以让旧一轮作废。

接受者（acceptor） 才是安全性质落在地上的那一层。他们记住两样东西：对更高编号的承诺，以及自己已经接受过的最高编号提案。崩溃后若把这两样忘掉，相交论证就断了。论文因此把稳定存储当成模型的一部分，而不是实现者事后才想起的细节。

学习者（learner） 不参与选定，只负责知道选定已经发生。一个值在某个多数接受者接受它的那一刻就被选定了。学习发生在足够多的「已接受」消息被收齐之后。中间可以隔着分区。把「已被选定」和「已被所有人知道」混成一个时刻，会把安全性质误读成广播成功。

选票：准备，然后接受#

单次 Synod 是两阶段。它不是两次投票，而是一次约束收集加一次受约束的提议。第一阶段常被叫作准备（prepare）。提议者选出编号 $n$，向接受者询问：你们能否承诺不再接受编号小于 $n$ 的提案？若接受者尚未对更大编号做过承诺，就答应下来，并汇报自己已接受的最高编号提案——如果有的话。

这一步的产品是一张不得回头的字据，外加一张关于历史的答卷。第二阶段常被叫作接受（accept）。提议者必须先从某个多数那里收齐承诺。若答卷里没有任何旧值，他可以提出自己的值。若有旧值，他必须提出答卷中编号最高的那个已接受值。

这条选择规则不是礼貌，是安全证明的铰链。接受者若尚未对更高编号做新承诺，就接受 $(n,v)$ 并记下。一个值被选定，当且仅当某个多数已经接受了带同一编号的该值。协议允许网络里同时飘着许多编号、许多提案。

它禁止的是：两个不同的值都达到「已被选定」。这里没有「把 RPC 写成怎样」「超时设多少毫秒」的配方。超时只影响谁先发起下一轮，不进入安全论证。把超时写进正确性，会把模型偷偷改成同步系统。

安全声明：相交，而不是人多#

Paxos 安全性的几何内容，几乎全部是集合相交。取 $2f+1$ 个接受者，任意多数至少 $f+1$ 人。任意两个多数至少共享一人。若值 $v$ 已在编号 $n$ 下被一个多数接受，那么任何编号更大的准备阶段，其多数里至少有一人会报告 $v$。

后来的提议者因此不能改提别的值。这不是「票数多的赢」。这是「后来者必须看见并继承已经被选定的值」。有效性是另一句：被选定的值必须是某个提议者真正提出过的，不能凭空发明。学习不改变这两句。

学习者慢、分区久，只表示知道得晚，不表示选定值可以被替换。论文给出的是安全性质，不是「集群永远可写」的可用性承诺。长期分区里，两边都凑不齐多数，进展可以停住。停住是活性失败，不是把法令改成两份。

把停住讲成攻击步骤或拆网配方，会离开这份对象。需要记住的只是：安全与进展是两条句子，多数交集只为第一条签字。

单次 Synod 与整部议会#

Synod 只决定一条法令。复制一台状态机需要的是法令的序列：先执行哪条命令、后执行哪条，所有副本必须相同。1998 年文本里的议会协议给法令编号，并把一连串 Synod 串起来。稳定的议长可以在后续编号上复用第一阶段的承诺，不必每条法令都重新准备一遍。

这就是后来所称 Multi-Paxos 的轮廓。轮廓不是实现。槽位空洞、议长更迭、成员集合更换，都会把「多数」这个词的所指改掉。旧配置的多数与新配置的多数若不相交，两边就可能各自选定冲突法令。那不是 Synod 内部的漏洞，而是配置变迁必须另写的相交条件。

把 Paxos 说成已经替 数据库与事务 保证了 ACID，会跳过这一层。共识复制的是命令顺序。隔离级别、崩溃原子性、客户端重试是否变成两次扣款，仍要事务层自己写清。Google Chubby 后来的工程经验表明：把论文里的 Synod 变成可运维服务，工作量大多不在两阶段本身，而在成员、磁盘与「客户端以为成功了吗」。那些经验属于后续文献，不把 1998 年的安全声明扩成产品保证。

进展为何更脆#

安全论证不看时钟。消息可以任意晚到，只要最终送达的内容不被篡改、接受者的稳定存储还在，相交仍然成立。进展则依赖一种「不要永远同时抢话筒」的局面。两个提议者各持越来越大的编号轮流准备，接受者不断改口承诺，接受阶段就可能永远凑不齐。

这不是实现写错，是与 FLP 同一方向的活锁。工程上常见的缓解是让提议者收敛成一位：随机退避、租约、或显式选举。缓解改变的是活性假设，不是安全定理。《Paxos Made Simple》把这一点写得很乾脆：选出一个值，需要多数接受者活着，并且最终只跟一位提议者说话。

它没有声称在任意长的异步调度下必然终止。读 1998 年论文若只记住「兼职也能立法」，却忘掉「议长打架时立法可以停」，就会把寓言读成可用性神话。Raft 把可理解的领导者写进设计，正是对这层脆性的工程回应。

回应的是教学与实现的状态空间，不是把 Paxos 的安全声明作废。要看复制日志如何变成键值存储，应去 etcd 的 Raft；不要把那条工程链回读成 Synod 的缺页。

这篇论文改变了什么#

在 Paxos 被读懂以前，容错复制常常靠主备切换、法定人数加锁，或一堆难以并列证明的特例。《兼职议会》给出一份可以单独陈述的不变量：选定值被多数的持久记忆锁住，后来的多数一定撞上那份记忆。不变量先于代码。

兰波特后来的 TLA+ 工作，与这篇论文是同一习惯：先写清允许哪些行为，再问实现是否落在集合里。工业界消化得很慢。寓言体推迟了阅读；即便 2001 年的平实版本，实现者仍常在「选定」与「学习」、以及成员变更上跌倒。

慢，不等于对象含混。含混的是把协议名称当成可以采购的正确性。说「我们用了 Paxos」而不写故障模型、仲裁相交和提交前必须持久化什么，这句话几乎没有内容。本文只把发表出来的角色、选票与安全声明讲清楚。不提供节点清单，不提供可用区拆法，也不把分区演练写成步骤。概念证据到此为止。

跨域连接#

• 社会选择理论：阿罗定理问的是如何把许多人的排序加总成社会排序；Paxos 问的是如何在缺席与丢信下锁定一个已被提出的值。多数在两边都出现，机制却不是同一个。社会选择的多数是偏好聚合规则，可以循环、可以被议程操纵；Paxos 的多数是仲裁交集，目的是让已锁定的值无法被另一轮改写。把 Synod 读成「少数服从多数的民主算法」，会把有效性（值必须被提出过）错认成福利判断。Paxos 不比较法令好不好，只保证不会选出两份互相矛盾的法令记录。
• 立法机构：真实议会用法定人数防止空场立法，用记录防止会后改口。《兼职议会》把这两条写成崩溃模型：缺席等于崩溃，信使等于不可靠信道，稳定存储等于会议纪要。寓言有效，是因为立法机构本来就在处理「人不必同时在场，法律仍须单一」。差别同样硬：议会有党派、修正案与议程控制；经典 Paxos 假定接受者不对两名听众交出两份矛盾的已接受记录。制度比喻能讲清出缺，不能把政治过程塞进安全证明。
• 集合论：安全证明几乎不谈延迟数字，只谈有限集上的族。接受者集合确定之后，多数构成一个相交族：任意两个成员集共享元素。一旦某个值被其中一个集合「记牢」，任何后来想另起炉灶的集合都不得不问到那位共享的记忆者。这是外延性意义上的记忆——记下的是已接受的编号与值，不是口头印象。把相交写成网络拓扑或机房布局，会把集合论对象误认成运维图。拓扑可以决定哪些多数暂时连得上；连得上与否改变活性，不改相交这道算术。
• 时间哲学：法令在何时成为法律？协议拒绝一个全局「此刻」。选定发生在某个多数完成接受之时，这个完成对局外人不是同时可见的。学习者的「知道」更晚，分区可以让知道再推迟。先后由消息因果给出，不由墙上时钟给出。这与「现在是薄薄一层、全局共享」的日常时间观相反：分布式里没有人人共用的现在，只有已被记录、可被后来者继承的值。把提交时刻写成统一墙钟，会把安全性质绑到校准误差上；论文绑定的是编号与相交，不是同时性。
• 认识论：接受者接受一个值，还不等于系统已经知道自己接受了它。选定是世界里的事实，学习是知识状态。没有上帝视角的节点，只能用收到的消息当证据。证据不足时，正确动作是不宣称已知，而不是猜一份法令。这不是怀疑主义游戏，而是把「真」与「知」拆开：真由多数接受构成，知由学习者收齐构成。工程事故常发生在把本地内存里的值当成已被选定的公共知识。Paxos 的角色分工本身就是一份知识论：谁有权提议，谁有权记住，谁有权宣布已经知道。

参考文献#

• Leslie Lamport, "The Part-Time Parliament", ACM Transactions on Computer Systems 16(2), 1998, pp. 133–169. DOI: 10.1145/279227.279229. —— Synod / 议会协议的原始发表文本。
• Leslie Lamport, "Paxos Made Simple", ACM SIGACT News 32(4), 2001, pp. 51–58. —— 去掉寓言后的角色与两阶段陈述。
• Butler W. Lampson, "How to Build a Highly Available System Using Consensus", in Distributed Algorithms (WDAG 1996), Springer LNCS 1151, 1996. —— 将 Paxos 重新介绍给系统共同体的关键中介。
• Michael J. Fischer, Nancy A. Lynch & Michael S. Paterson, "Impossibility of Distributed Consensus with One Faulty Process", Journal of the ACM 32(2), 1985, pp. 374–382. —— 异步确定性共识的活性边界，用以限定 Paxos 能承诺什么。

延伸阅读#

• 与 莱斯利·兰波特 对读：逻辑时钟处理的是事件偏序，Paxos 处理的是缺席下的法令锁定，不要把两篇论文收成同一个「时间」故事。
• 与 分布式计算理论 对读：先分清安全与终止，再看部分同步如何让进展重新可谈。
• Diego Ongaro & John Ousterhout, "In Search of an Understandable Consensus Algorithm", USENIX ATC, 2014. —— 后续以可理解性为目标的复制日志协议；实现路径见 etcd 的 Raft，不是 Paxos 的缺页补丁。