一、概念
首先一个很重要的概念叫提案（Proposal）。最终要达成一致的value就在提案里。
提案 (Proposal)：Proposal信息包括提案编号 (Proposal ID) 和提议的值 (Value)。
在Paxos算法中，有如下角色：
- Client：客户端客户端向分布式系统发出请求，并等待响应。例如，对分布式文件服务器中文件的写请求。
- Proposer：提案发起者提案者提倡客户请求，试图说服Acceptor对此达成一致，并在发生冲突时充当协调者以推动协议向前发展
- Acceptor：决策者，可以批准提案Acceptor可以接受（accept）提案；如果某个提案被选定（chosen），那么该提案里的value就被选定了
- Learners：最终决策的学习者，学习者充当该协议的复制因素
二、问题描述
假设有一组可以提出提案的进程集合，那么对于一个一致性算法需要保证以下几点：
- 在这些被提出的提案中，只有一个会被选定
- 如果没有提案被提出，就不应该有被选定的提案。
- 当一个提案被选定后，那么所有进程都应该能学习（learn）到这个被选定的value
三、推导过程
最简单的方案——只有一个Acceptor
假设只有一个Acceptor（可以有多个Proposer），只要Acceptor接受它收到的第一个提案，则该提案被选定，该提案里的value就是被选定的value。这样就保证只有一个value会被选定。但是，如果这个唯一的Acceptor宕机了，那么整个系统就无法工作了！因此，必须要有多个Acceptor！
多个Acceptor
多个Acceptor的情况如下图。那么，如何保证在多个Proposer和多个Acceptor的情况下选定一个value呢？
下面开始寻找解决方案。首先我们希望即使只有一个Proposer提出了一个value，该value也最终被选定。那么，就得到下面的约束：
P1：一个Acceptor必须接受它收到的第一个提案。
但是，这又会引出另一个问题：如果每个Proposer分别提出不同的value，发给不同的Acceptor。根据P1，Acceptor分别接受自己收到的第一个提案，就导致不同的value被选定。出现了不一致。如下图：
刚刚是因为『一个提案只要被一个Acceptor接受，则该提案的value就被选定了』才导致了出现上面不一致的问题。因此，我们需要加一个规定：
规定：一个提案被选定需要被半数以上的Acceptor接受
这个规定又暗示了：『一个Acceptor必须能够接受不止一个提案！』不然可能导致最终没有value被选定。比如上图的情况。v1、v2、v3都没有被选定，因为它们都只被一个Acceptor的接受。所以在这种情况下，我们使用一个全局的编号来标识每一个Acceptor批准的提案，当一个具有某value值的提案被半数以上的Acceptor批准后，我们就认为该value被选定了.根据上面的内容，我们现在虽然允许多个提案被选定，但必须保证所有被选定的提案都具有相同的value值。否则又会出现不一致。于是有了下面的约束：
P2：如果某个value为v的提案被选定了，那么每个编号更高的被选定提案的value必须也是v。
一个提案只有被Acceptor接受才可能被选定，因此我们可以把P2约束改写成对Acceptor接受的提案的约束P2a。
P2a：如果某个value为v的提案被选定了，那么每个编号更高的被Acceptor接受的提案的value必须也是v。
只要满足了P2a，就能满足P2。
但是，考虑如下的情况：假设总的有5个Acceptor。Proposer2提出[M1,V1]的提案，Acceptor2~5（半数以上）均接受了该提案，于是对于Acceptor2~5和Proposer2来讲，它们都认为V1被选定。Acceptor1刚刚从宕机状态恢复过来（之前Acceptor1没有收到过任何提案），此时Proposer1向Acceptor1发送了[M2,V2]的提案（V2≠V1且M2>M1），对于Acceptor1来讲，这是它收到的第一个提案。根据P1（一个Acceptor必须接受它收到的第一个提案。）,Acceptor1必须接受该提案！同时Acceptor1认为V2被选定。这就出现了两个问题：
- Acceptor1认为V2被选定，Acceptor2~5和Proposer2认为V1被选定。出现了不一致。
- V1被选定了，但是编号更高的被Acceptor1接受的提案[M2,V2]的value为V2，且V2≠V1。这就跟P2a（如果某个value为v的提案被选定了，那么每个编号更高的被Acceptor接受的提案的value必须也是v）矛盾了。
所以我们要对P2a约束进行强化！P2a是对Acceptor接受的提案约束，但其实提案是Proposer提出来的，所以我们可以对Proposer提出的提案进行约束。得到P2b：
P2b：如果某个value为v的提案被选定了，那么之后任何Proposer提出的编号更高的提案的value必须也是v。
由P2b可以推出P2a进而推出P2。那么，如何确保在某个value为v的提案被选定后，Proposer提出的编号更高的提案的value都是v呢？只要满足P2c即可：
P2c：对于任意的Mn和Vn,如果提案[Mn,Vn]被提出，那么肯定存在一个由半数以上的Acceptor组成的集合S，满足以下两个条件中的任意一个： * 要么S中每个Acceptor都没有接受过编号小于Mn的提案。 * 要么S中所有Acceptor批准的所有编号小于Mn的提案中，编号最大的那个提案的value值为Vn
从上面的内容，可以看出，从P1到P2c的过程其实是对一系列条件的逐步增强，如果需要证明这些条件可以保证一致性，那么就可以进行反向推导：P2c =>P2b=>P2a=>P2,然后通过P2和P1来保证一致性。