Paxos 算法是基于消息传递且具有高度容错特性的一致性算法，是目前公认的解决分布式一致性问题最有效的算法之一，其解决的问题就是在分布式系统中如何就某个值（协议）达成一致
Paxos 算法是分布式一致性算法用来解决一个分布式系统如何就某个值达成一致的问题。一个典型的场景是，在一个分布式数据库系统中，如果各节点的初始状态一致，那么每个节点都执行相同的操作序列，那么他们最后能得到一个一致的状态。为保证每个节点执行相同的命令序列，需要在每一条指令上执行一个 “一致性算法” 以保证每个节点看到的指令一致。
分布式系统中一般是通过多副本来保证可靠性，而多个副本之间会存在数据不一致的情况。所以必须有一个一致性算法来保证数据的一致性，描述如下：
假如在分布式系统中初始是各个节点的数据是一致的，每个节点都顺序执行系列操作，然后每个节点最终的数据还是一样的
Paxos 算法就是解决这种分布式场景中的一致性问题。对于一般开发人员来说，只需要知道 paxos 是一个分布式选举算法即可。多个节点之间存在两种通讯模型：共享内存、消息传递，Paxos 是基于消息传递的
Paxos 算法的前提是不存在拜占庭将军问题，即：信道是安全的，发出的信号不会被篡改，因为 Paxos 算法是基于消息传递的
Paxos 算法的相关概念
在 Paxos 算法中，有三种角色：
Proposer
Acceptor
Learners
在具体的实现中，一个进程可能同时充当多种角色。比如一个进程既是 Proposer 又是 Learner。Proposer 负责提出议案，Acceptor 负责对提案作出裁决（accept 与否），Learner 负责学习提案结果
还有一个很重要的概念叫提案（proposal），最终要达成一致的 value 就在提案里。只要 proposal发的提案被半数以上的 acceptor 接受，proposer 就认为该提案的 value 被选定。Acceptor 告诉 Learner 哪个 value 被选定了，Learner 就认为哪个被选定。
为了避免单点故障，会有一个 Acceptor 集合，proposer 向 Acceptor 集合发送提案，Acceptor 集合中的每个成员都有可能同意该提案且每个 Acceptor 只能批准一个提案，只有当一半以上的成员同意了一个提案，就认为该提案被选定了
已经半数优胜之后为何还要提出新方案？？
Paxos 算法的过程
Paxos 算法类似于 2PC，其算法执行过程分为两个阶段。具体如下：
阶段一（prepare 阶段）
proposer 选择一个提案编号 N，然后向半数以上的 Acceptor 发送编号为 N 的 Prepare请求
如果一个 Acceptor 收到一个编号为 N 的 Prepare 请求，如果小于它已经响应的请求，则拒绝，不回应或回复 error。若 N 大于该 Acceptor 已经响应过的（如果只是进行完第一阶段，尚未选定，则拒绝该请求后续操作，转而执行编号更大的请求）所有 Prepare 编号（maxN），那么它就会将它已经接受过的（已经经过第二阶段 accept 的提案）的编号最大的提案（如果有的话，如果还没有就返回{pok,null,null}）作为响应反馈给 Proposer，同时该 Acceptor 承诺不再接受任何编号小于 N 的提案
阶段二（accept 阶段）
如果一个 Proposer 收到半数以上 Acceptor 对其发出的编号为 N 的 prepare 请求的响应，那么它就会发送一个针对 [N,V] 提案的 Accept 请求给半数以上的 Acceptor。注意：V 就是收到的响应中编号最大的提案的 value（某个 acceptor 响应的它已经通过的{acceptN,acceptV}），如果响应中不包含任何提案，那么 V 就由 Proposer 自己决定
如果 Acceptor 收到一个针对编号为 N 的提案的 Accept 请求，只要该 Acceptor 没有对编号大于 N 的 Prepare 请求做出过响应，他就接受该提案
每个阶段都有两次通信，第一阶段是 prepare、promise，第二阶段是 accept、accepted
算法演示
如何保证 Paxos 算法的活性
算法死循环的情况：
这种情况下通过选取主 proposer，就可以保证 Paxos 算法的活性