Paxos是1990年，莱利斯-兰伯特提出的，基于消息传递，且具有高度容错性的一致性算法。是目前公认的解决分布式一致性最有效的算法之一。

一、Paxos来源

1982年，兰伯特与另外两人发表了论文The Byzantine Generals Problem，提出了一种计算机容错理论，即著名的拜占庭问题：

拜占庭帝国有很多支军队，不同军队间必须制定一个统一的行动计划，从而做出进军或者撤退的决定。而且，各个军队间是被地理位置所分隔开的，依靠军队的通讯员进行通讯。然而通讯员中可能存在叛徒，中途可能篡改消息，如何保证通讯过程中消息的一致性呢？

因为我们的分布式系统大部分都是在局域网当中，因此消息被篡改很不常见。我们通常在实际工作中会假设拜占庭问题是不存在的。

1990年，兰伯特提出了一个理论上的一致性解决方案，同时给出了严格的数学证明。同样是类似拜占庭问题，采用故事的形式来描述这一算法：

在古希腊有一个叫Paxos的小岛，岛上采用议会的形式来通过法令。议会中的议员通过信使进行消息的传递。值得注意的是，议员和信使都是兼职的，他们随时会离开会议厅，设置信使传递的消息可能是重复的，或者一去不复返。因此，议会协议要求在此种情况下仍能保证法令的的正确产生，并且不会出现冲突。

Paxos算法的名字就是取自这个小岛。

兰伯特公认的令人晦涩的算法描述，知道1998年才被接受，从此Paxos 算法正是被计算机科学家接受用于解决分布式系统的一致性问题。

2001年，兰伯特发布了Paxos Made Simple，使用通俗易懂的语言重新讲述的这一算法。

二、算法解析

2.1 问题描述

假设有一组可以提成提案的进程集合，那么对于一个一致性算法来说需要保证以下几点：
1）这些被提出的提案，只有一个可以被选定。
2）如果灭有提案被提出，那么就不会有提案被选定。
3）如果一个提案被选定，进程应该可以获取被选定的提案信息。

关于安全性的条件有如下：
1）只有被提出的提案才能被选定。
2）只有一个值被选定。
3）如果进程认为提案被选定了，那么该提案就是真的被选定的那个。

在Paxos的算法中，有三种角色：
1）proposer 提案者
2）acceptor 接受者
3）learner 学习者

2.2 提案的选定

采取多acceptor的方式进行提案的选定。单acceptor存在单点问题。如何认为这个提案被选定了呢？假设有一个acceptor集合，当有多个acceptor都选定了这个提案，当acceptor达到一定的数量，我们就认定提案选定成功。

整体来说是一个类似于两阶段提交的算法执行过程：
阶段一：
1、proposer提出一个编号是M(n)的提案，然后向超过半数的acceptor发送编号为M(n)prepare请求。
2、一个acceptor接收到编号为M(n)的提案，且该编号大于其所响应的所有编号，那么它就会将它所响应过得最大编号的提案作为响应反馈给proposer，同时acceptor承诺不会再通过小于M(n)的提案。

阶段二：
1、如果proposer收到半数以上acceptor返回的编号为M(n)的响应，那么它就会发送一个针对[M(n),V(n)]提案的Accept请求。
2、如果acceptor收到这个针对[M(n),V(n)]提案的Accept请求，只要该acceptor尚未对大于M(n)的prepare请求作出响应，它就可以通过这个提案。

2.3 提案的获取

如何让learner的获取到通过提案呢？可以使用如下的方案：

让所有的acceptor将他们的提案批准情况，统一发送给一个learner，各个learner之间相互通信。通常是主learner通知其他的learner。

如上方案存在主learner的单点问题，所以需要一个learner的集合。

2.4 通过选主proposer保证算法活性

一个分布式算法通常有两个关键特性，安全性（保证一定不会发生）和活性（保证一定会发生）。

如果任何一个proposer都能提交提案，那么基于前面的实现方案，会导致整个算法死循环。

如：a提出m1的提案，发出prepare请求，acceptor接收并响应，此时b提出一个m2，acceptor同样接收并响应。当a在第二阶段发起提案时，发现m1被丢弃了，又会发出一个m3的prepare请求，导致死循环。

此时需要最proposer进行选举，只有主proposer才能和过半的acceptor通讯，只要主proposer提出一个提案，就会被接受。当proposer发现当前有一个更大的提案，则会丢弃小的提案，并最终选出一个更大的提案。

三、总结

Paxos引入了过半的概念，少数服从多数。
Paxos支持节点角色的轮换，避免分布式单点。

是目前最优秀的分布式算法之一。