Paxos
Paxos 算法 是莱斯利·兰伯特（英语：Leslie Lamport，LaTeX中的“La”）于1990年提出的一种基于消息传递且具有高度容错特性的共识（consensus）算法。
需要注意的是，Paxos 常被误称为“一致性算法”。但是“一致性（consistency）”和“共识（consensus）”并不是同一个概念。Paxos 是一个共识（consensus）算法。
算法的提出与证明
首先将议员的角色分为 proposers，acceptors，和 learners（允许身兼数职）。proposers 提出提案，提案信息包括提案编号和提议的 value；acceptor 收到提案后可以接受（accept）提案，若提案获得多数派（majority）的 acceptors 的接受，则称该提案被批准（chosen）；learners 只能“学习”被批准的提案。划分角色后，就可以更精确的定义问题：
- 决议（value）只有在被 proposers 提出后才能被批准（未经批准的决议称为“提案（proposal）”）；
- 在一次 Paxos 算法的执行实例中，只批准（chosen）一个 value；
- learners 只能获得被批准（chosen）的 value。
在 Leslie Lamport 之后发表的paper中将 majority 替换为更通用的 quorum (法定人数是议事程序里面规定议会要进行议事的时候需要出席议员的最低数量。罗伯特议事规则说：这样要求是防止由过小数目的议员进行完全不具代表性的行动。) 概念，但在描述classic paxos的论文 Paxos made simple（ 中使用的还是majority的概念。
决议的提出与批准
通过一个决议分为两个阶段：
- prepare阶段
- proposer选择一个提案编号n并将prepare请求发送给acceptors中的一个多数派；
- acceptor收到prepare消息后，如果提案的编号大于它已经回复的所有prepare消息(回复消息表示接受accept)，则acceptor将自己上次接受的提案回复给proposer，并承诺不再回复小于n的提案；
- 批准阶段：
- 当一个proposer收到了多数acceptors对prepare的回复后，就进入批准阶段。它要向回复prepare请求的acceptors发送accept请求，包括编号n和根据P2c决定的value（如果根据P2c没有已经接受的value，那么它可以自由决定value）。
- 在不违背自己向其他proposer的承诺的前提下，acceptor收到accept请求后即批准这个请求。
这个过程在任何时候中断都可以保证正确性。例如如果一个proposer发现已经有其他proposers提出了编号更高的提案，则有必要中断这个过程。因此为了优化，在上述prepare过程中，如果一个acceptor发现存在一个更高编号的提案，则需要通知proposer，提醒其中断这次提案。
Multi-Paxos
Paxos的典型部署需要一组连续的被接受的值（value），作为应用到一个分布式状态机的一组命令。如果每个命令都通过一个Basic Paxos算法实例来达到一致，会产生大量开销。
如果Leader是相对稳定不变的，第1阶段就变得不必要。 这样，系统可以在接下来的Paxos算法实例中，跳过第1阶段，直接使用同样的Leader。
为了实现这一目的，在同一个Leader执行每轮Paxos算法时，提案编号 I 每次递增一个值，并与每个值一起发送。Multi-Paxos在没有故障发生时，将消息延迟(从propose阶段到learn阶段)从4次延迟降低为2次延迟。
Fast-Paxos
Fast-Paxos将Basic-Paxos进行了推广，以减少端到端消息延迟。在Basic-Paxos中，从客户端发起请求开始，到Learn阶段结束的消息延迟是3个消息延迟。而Fast-Paxos允许2个消息延迟，但要求：
- (1)系统由3f+ 1个Acceptor组成，以容忍最多f个错误(而不是Basic-Paxos的2f+1)；
- (2)客户端需要直接将请求发送到多个目标。
直观上，如果Leader没有提议任何value，那么客户可以直接发送Accept消息到向接收方发。Acceptor会像Basic-Paxos一样运行，向Leader和每个Learner发送Accepted的消息，从而实现从客户端到Learner的两消息延迟。
如果Leader检测到冲突，它通过发起新一轮投票，并发送Accept消息来解决冲突，通常是一个Accepted消息。这种有协调者参与的冲突恢复机制需要4个从客户端到Learner的消息延迟。
如果Leader提前指定了一种冲突恢复机制，就可以实现另一种优化，它允许Acceptors自己执行冲突恢复。因此，无协调的冲突恢复可能实现三个消息延迟(如果所有的Learner都是接收者，那么只有两个消息延迟)。
应用
Apache ZooKeeper 使用一个类Multi-Paxos的共识算法作为底层存储协同的机制。