案例库 · 研发与科研 · 技术决策 · 1989–2001
Paxos 在故障网络中通过多数交集达成共识
Lamport 的 Paxos 让机器在部分故障时仍能达成一致：任意两个多数派共享一个接受者，因此只能有一个值胜出。
数字设备公司
解法
莱斯利·兰波特于1989年撰写了 Paxos 算法，题为《兼职议会》，这是一个寓言，讲述一个立法机构的成员进进出出，但其记录保持一致。他于1990年提交，但直到1998年5月才发表在《ACM 计算机系统汇刊》上。
核心问题是共识：一组机器必须选择一个值，即使进程失败、重启，消息丢失或延迟。简单的修复方案是让一个接受者决定，但该机器故障则系统失效；多数投票之所以有效，是因为任意两个多数派共享一个成员。
Paxos 利用了这种交集。提案带有递增的编号，接受者承诺忽略旧编号，当多数派接受某个值时，该值即被选定。法定人数的重叠使得算术上不可能选择两个值，因此系统在没有机器绝对可靠的情况下保持安全。
生效的原因
- 任意两个多数派共享接受者，阻止两个赢家
- 编号提案让接受者可以安全地改变主意
- 安全不需要时钟，只需要法定人数的算术
- 状态机框架使其在真实系统中可用
取得的成效任意两个多数派共享一个接受者神来之笔
可借鉴之处
让任意两个同意组重叠：相交的法定人数将无法执行的保证转变为能在崩溃、延迟和重启中存活的算术。
后续进展
Paxos 成为分布式共识的标准答案：Lamport 在2001年的论文《Paxos 简化》用通俗语言重述了这一思想，该算法被应用于生产系统，如 Google 的 Chubby 锁服务和早期 Spanner，其法定人数结构在故障下保持副本一致性。
资料来源
发现哪里写错了？告诉我们。