目录
之前文章介绍了2PC和3PC一致性协议，本文将继续介绍另一个Paxos算法
前置知识
对于分布式一致性算法，有两个最重要的属性：
- 安全性：指那些需要保证永远都不会发生的事情
- 活性：指那些最终一定会发生的事情
问题描述
假设有一组可以提出提案的进程集合，对于一致性算法，要求：
- 这些提案最终只有一个被选定
- 当一个提案被选定后，进程可以获取被选定的提案信息
对于Paxos，安全性要求有：
- 只有被提出提案才能被选定
- 只有一个值会被选定
- 如果某个进程认为某个提案被选定了，那这个提案必须真的是被选定的那个
活性要求是：保证最终有一个提案被选定
三种参与角色：
Proposer：提案提出者
Acceptor：提案接受批准者
Learner：只获取最终被批准的提案
提案的选定
规则：Proposer向一个Acceptor集合发送提案，集合中的每个Acceptor都可能会accept（批准）该提案，当有足够多的Acceptor批准该提案的时候，就可以认为这个提案被选定了。
这里的足够多怎么界定呢？
这个“足够多”的集合是所有Acceptor的一个子集，这个可以包含Acceptor集合中的大多数成员，因为任意两个包含大多数Acceptor的子集至少有一个公共成员。（实际就是超过一半的Acceptor批准）
推导过程
在没有失败和消息丢失的情况下，如果我们希望即使在只有一个提案被提出的情况下，仍然可以选定一个提案，这就暗示如下需求：
P1:一个Acceptor必须批准它收到的第一个提案
但这个条件存在问题，即多个提案被不同Proposer同时提出，无法最终确定一个提案
还会出现不同提案被选定的Acceptor集合数量相同，也无法最终确定一个提案
因此，需要在P1的基础上，在加“一个Acceptor必须能够批准不止一个提案”的条件。
这里将每个提案抽象成一个“【编号，Value】”的结构
- 编号是全局唯一的，可以唯一标识一个被Acceptor批准的提案
- 当具有某个Value值的提案被一半以上的Acceptor批准后，我们就认为这个提案被选定了
我们约定：虽然允许多个提案被选定，但是必须保证被选定的提案都具有相同的Value值，即
P2:如果【M0，V0】的提案被选定了，那么所有编号比M0高的且被选定的提案，Value值都是V0
这里对于P2的证明需要用到数学归纳法，这里不做详述
Proposer生成提案
由于P2条件，Proposer在产生一个编号为Mn的提案时，必须知道当前某一个将要或者已经被半数以上的Acceptor批准的编号小于Mn但最大的提案。并且 Proposer会要求所有的Acceptor都不能再批准任何编号小于Mn的提案。
Prepare请求
Proposer选择一个新的提案编号Mn，然后向某个Acceptor集合发送请求，要求其作出如下响应：
- 承诺不在接受任何编号小于Mn的提案
- 如果此Acceptor批准过提案，就返回已经批准的编号小于Mn但最大的提案的Value值
Accept请求
如果Proposer收到一半以上Acceptor的响应结果，那么它就可以产生【Mn，Vn】的提案，这里的Vn是所有响应中编号最大提案的Vaule值，如果大多数Acceptor没有批准过提案，则Vn任意。之后将该提案再次发送给某个Acceptor集合，期望获得批准。
Accpetor批准提案
收到Prepare请求
Acceptor可以在任何时候响应一个prepare请求
收到Accept请求
在不违背承诺的前提下，可以任意响应Accept请求
即一个Acceptor只要未响应过任何编号大于Mn的Prepare请求，则它可以接受这个编号为Mn的提案
算法流程
阶段一
1. Proposer选择一个提案编号Mn，然后向超过半数的Acceptor子集发送编号为Mn的Prepare请求。
2.如果一个Acceptor收到一个编号为Mn的Prepare请求，且编号Mn大于该Acceptor已经响应的所有Prepare请求的编号，那么它就会将它已经批准过的最大编号的提案作为响应反馈给Proposer，同时该Acceptor会承诺不会再批准任何编号小于Mn的提案。
阶段二
1.如果Proposer收到来自半数以上的Acceptor对于其发出的编号为Mn的Prepare请求的响应，那么它就会发送一个【Mn，Vn】提案的Accept请求给Acceptor。Vn的值就是收到的响应中编号最大的提案的值，如果响应中不包含任何提案，那么它就是任意值。
2.如果Acceptor收到这个针对【Mn，Vn】提案的Accept请求，只要该Acceptor尚未对编号大于Mn的Prepare请求做出响应，它就可以通过这个提案。
