Paxos 算法是分布式系统中最著名的共识算法，由 Leslie Lamport 于 1990 年提出。它是所有现代共识算法（如 Raft, ZAB）的鼻祖，被认为是分布式系统领域最基础也最重要的算法之一。
“There is only one consensus protocol, and that’s Paxos — all other approaches are just broken versions of Paxos.” —— Mike Burrows (Google Chubby 作者)
核心设计思想
Paxos 的目标是在一个可能发生节点故障、网络延迟或丢包的分布式系统中，就某个值达成一致。它通过两阶段提交（Two-Phase Commit）的变体来确保一致性。
角色划分
在 Paxos 算法中，节点被划分为三种角色。关于为什么要区分这些角色，请参考 Paxos 为什么需要区分 Proposer 和 Acceptor？。
- Proposer (提议者)：负责发起提案（Proposal）。
- Acceptor (决策者)：负责对提案进行投票和决策。
- Learner (学习者)：不参与决策，只负责获取最终达成的共识结果。
注：在实际工程实现中，一个节点通常同时承担多个角色。
算法流程 (Basic Paxos)
Basic Paxos 达成一次共识需要经历“准备”和“接受”两个阶段。详细的步骤定义、图解及状态机说明请参考：
Paxos 的变体
由于 Basic Paxos 只能就单个值达成共识，且存在“活锁”风险，实际应用中更多使用其变体：
- Multi-Paxos：通过引入 Leader 角色，跳过第一阶段的 Prepare，直接进行 Accept，大大提高了性能。
- Fast Paxos：进一步减少消息延迟。
优缺点
优点
- 数学证明完备：在非拜占庭环境下，保证了强一致性。
- 高容错性：只要多数派存活，系统即可运行。
缺点
- 极其复杂：理解和实现都非常困难。
- 活锁问题：多个 Proposer 交替提出更高编号的提案可能导致系统无法达成共识。
工业级应用
- Google Chubby：分布式锁服务。
- Apache ZooKeeper：虽然使用的是 ZAB 协议，但其核心思想深受 Paxos 影响。
- Microsoft Autopilot：集群管理系统。