Paxos算法是由供职于微软的Leslie Lamport最先提出的一种基于消息传递(MessagesPassing)的一致性算法。在目前所有的一致性算法中，该算法最常用且被认为是最有效的。要想了解Paxos 算法，我们首先需要知道什么是分布式系统中的一致性问题，因为 Paxos算法就是为了解决这个问题而提出的。简单地说分布式系统的一致性问题，就是如何保证系统中初始状态相同的各个节点在执行相同的操作序列时,看到的指令序列是完全一致的，并且最终得到完全一致的结果。在Lamport 提出的Paxos算法中节点被分成了三种类型:proposers、acceptors和 learners。其中proposers提出决议（Value)，acceptors 批准决议，learners获取并使用已经通过的决议。一个节点可以兼有多重类型。在这种情况下，满足以下三个条件就可以保证数据的一致性：

    1. 决议只有在被proposers提出后才能批准
    2. 每次只批准一个决议
    3. 只有决议确定被批准后learners才能获取这个决议

    Lamport通过约束条件的不断加强，最后得到了一个可以实际运用到算法中的完整约束条件：如果一个编号为n 的提案具有值v，那么存在一个多数派，要么他们中没有人批准过编号小于n 的任何提案，要么他们进行的最近一次批准具有值v。为了保证决议的唯一性，acceptors也要满足一个如下的约束条件：当且仅当acceptors没有收到编号大于n的请求时，acceptors 才批准编号为n的提案。
    在这些约束条件的基础上，可以将一个决议的通过分成两个阶段：

    1. 准备阶段：proposers选择一个提案并将它的编号设为n，然后将它发送给acceptors中的一个多数派。acceptors收到后，如果提案的编号大于它已经回复的所有消息，则acceptors将自己上次的批准回复给proposers，并不再批准小于n的提案
    2. 批准阶段：当proposers接收到acceptors中这个多数派的回复后，就向回复请求的acceptors发送accept请求，在符合acceptors一方的约束条件下，acceptors收到accept请求后即批准这个请求

    为了减少决议发布过程中的消息量，acceptors将这个通过的决议发送给learners 的一个子集，然后由这个子集中的learners去通知所有其他的learners。一般情况下，以上的算法过程就可以成功地解决一致性问题，但是也有特殊情况。根据算法一个编号更大的提案会终止之前的提案过程,如果两个proposer在这种情况下都转而提出一个编号更大的提案，那么就可能陷入活锁。此时需要选举出一个president，仅允许president 提出提案。

    image.png