Paxos算法是一种分布式系统算法。
三个角色：
proposer：提案发起者。
acceptor：提案评估者。
Learners：不参与提案，只被动接受已经被通过的提案。
操作流程：
客户端(client)向任意一个proposer提交提案；然后这个proposer就充当client的代理在整个paxos网络中完成提案的所有操作：发起投票，提交提案，最后把结果返回给client。
相比较Raft算法，此时这个被任意选中的proposer就相当于Raft算法中一个leader的角色，所以在Poxos算法中并没有leader的角色，也就不存在leader选举的问题，任何proposer都可以是leader，同一时刻整个paxos网络中可能会存在多个leader，即多个客户端同时向paxos网络提交提案。
算法的两个阶段：
1. 第一阶段：准备阶段(又叫prepare阶段，或者promise阶段)
从所有的proposer中确定一个编号最高的，只有编号最高者才能进入第二阶段去提交提案。
2. 第二阶段：决议阶段或投票阶段
由第一阶段选出的编号最高的proposer提交提案，由所有的accepter表决是否通过提案；如果通过，则记录提案并持久化，如果没通过，则需要发起新的一轮提案过程。
算法过程：
以下是第一阶段过程：
1. proposer生成提案号
proposer在收到客户端的请求后，首先为该提案生成一个提案号。 如下是一个生成提案号(n)例子：
提案号：n = total * m + id
m ：是从0开始的递增正整数
total：是proposer的总个数。
id ：是当前proposer的编号。
这样每一个proposer生成的序号都不会相同，而且能够累加往上递增。
2. proposer向accepter发送promise请求
promoser向超过半数(n/2+1)，或者向所有的accepter发送一个promise请求。这个promise请求只包含提案号n，而没有提案的真正内容，其目的是为了让accepter拒绝掉所有小于此编号(n)的任何promise请求和任何accept请求。
说明一下：
- promise请求就是当前这个请求，是在第一阶段发出的请求，只包含提案号的请求。
- accept请求是在第二阶段发出的请求，就是真正的提案请求，包含提案号和提案内容。
3. accepter接受promise请求
accepter接收到一个promise请求之后，它会判断：
3.1 如果之前没有接受过promise请求，则接受当前promise请求，并返回OK
3.2 如果之前已经接受过promise请求，那么：
3.2.1 如果之前的提案号大于当前提案号(n)，那么accepter将会拒绝当前promise请求，返回Rejected。
3.2.2 如果之前的提案号小于当前提案号(n)：那么：
3.2.2.1 如果之前还没有接受过accept请求，那么接受当前promise请求，相当于作废之前的promise请求，返回OK。
3.2.2.2 如果之前已经接受过accept请求，那么返回之前接受过的accept请求内容(acceptedProposal, acceptValue)，因为已经accept了之前的提案，不能作废了，只能返回给当前promoser，返回OK。
这里：acceptedProposal是指已经接受的提案号，acceptValue是指已经接受的提案内容。
4. proposer接受accepter的promise回复
proposer收集所有的accepter的回复。
4.1 如果回复OK数没有超过半数，则promise请求失败，需重新申请新的提案号，重新发起提案请求。
4.2 如果回复OK数超过半数，判断：
4.2.1 如果在所有OK回复里没有发现有acceptedValue，则使用客户提供的提案，进入第二阶段。
4.2.2 如果在所有OK回复里发现有acceptedValue值，表示已经有认可的提案了，则保存最高的提案号acceptedProposal里面的提案acceptedValue内容到本地。然后使用这个提案acceptValue内容，进入第二阶段。
这相当于当proposer提出一个提案，虽然我的提案号是最大的，但是之前一个小提案号的提案已经被大家接受了，所以我只能放弃我自己的提案，转投去接受那个已经被大家接受的提案。
以下是第二阶段过程：
5. proposer向accepter发送accept请求
proposer向所有的accepter发送accept请求；accpet请求包括两项内容，提案号，和提案内容(n, value)：
1. 提案号是自己的之前第一阶段生成的提案号。
2. 提案内容可能是client提交的提案内容，也可能是所有promise请求返回里的提案内容；具体参见第一阶段过程描述。
如果是promise请求返回里的提案内容，那么它一定是所有promise请求返回中最大的acceptedProposal对应的acceptedValue。
6. accepter接受accept请求
accepter接收到accept请求之后，它比较accept请求里的提案编号n值和本地的minProposal值。
注：minProposal是指已经接受的最大的promise请求编号。不知道为什么取名叫min，而不叫max；要不这么理解，可以响应的提案编号的最小阈值，即如果比这个还小，那就不响应了。
6.1 如果当前accept请求的提案号n >= minProposal，那么接受这个accept请求，并记录值(acceptedProposal = minProposal=n，acceptedValue=value)持久化，返回Accepted状态，并把通知所有learners。
6.2 如果当前accept请求的提案号 n<minProposal，这说明在这期间又收到了更大提案号的promise请求，那么拒绝这个accept请求，并返回那个较大的提案号的内容(Reject, minProposal)。
7. proposer接受accept请求返回
proposer收集所有的accept请求返回消息，判断：
7.1 如果收到超过半数的Accepted状态，说明提案被接受了。
7.2 如果在accept请求返回里面发现有返回值提案号minProposal>n，表示又有新的提案了，则需要重新发起一轮提案。
这个地方有一个活锁问题：即一个proposer发现返回的编号大于自己的编号，导致整个过程重来，另一个propser又会发现又有新的编号大于自己的编号，又要整个过程重来，导致如此反复，算法永远无法结束，这叫活锁。解决的办法是要在proposer之间选出leader，由leader来做最终判断依据。
下面这张图片是来自网络，对整个过程描述的非常简洁明了，拷贝在这供参考。
