Paxos算法是一种常用于分布式系统的共识一致性算法，它主要解决的问题是分布式系统中某个值(决议)如何达成一致。Paxos可以实现数据副本一致性，分布式锁，名字管理等。Paxos包括原始Paxos(basic paxos)和变种优化的multi-paxos等，其中multi-paxos更适合工程实践。
1）Basic Paxos：
Basic Paxos包含的角色：
- Proposer提出提案，可以是一个或多个proposer。
- Acceptor决策是否接受来自Proposer的提案。
- Learner最终提案的学习者。
Basic Paxos算法流程包含三个阶段：
- prepare阶段
proposer向所有acceptor广播prepare的请求，请求中带有一个全局唯一且自增的proposal num（pn），acceptor接收消息后不再接收pn<=当前pn的prepare消息或propose消息。Acceptort接收之后向proposer回复promise消息。
图 1：prepare阶段a
图 2 prepare阶段b
- accept阶段
proposer收到过半数且最大pn的提案[pn,value]，然后将提案发送给acceptor。Accept收到propose请求，大于等于本地pn，则将[pn,value]保存到本地，并且返回proposer已接收。
图 3 accept阶段a
图 4 accept阶段b
- learn阶段
Proposer收到多数Acceptors的Accept后，决议形成，将通过的提案发送给所有Learners。
图 5 learn阶段
2）Multi paxos：
原始的Paxos算法（Basic Paxos）只能对一个值形成决议，决议的形成至少需要两次网络来回，在高并发情况下可能需要更多的网络来回，极端情况下甚至可能形成活锁。如果想连续确定多个值，Basic Paxos搞不定了。因此Basic Paxos几乎只是用来做理论研究，并不直接应用在实际工程中。
实际应用中几乎都需要连续确定多个值，而且希望能有更高的效率。Multi-Paxos正是为解决此问题而提出。Multi-Paxos基于Basic Paxos做了两点改进：
1、针对每一个要确定的值，运行一次Paxos算法实例（Instance），形成决议。
2、在所有Proposers中选举一个Leader，由Leader唯一地提交Proposal给Acceptors进行表决。这样没有Proposer竞争，解决了活锁问题。在系统中仅有一个Leader进行Value提交的情况下，Prepare阶段就可以跳过，从而将两阶段变为一阶段，提高效率。
在分布式存储中Ceph monitor采用的是Multi paxos算法。
