Paxos

Paxos算法是一种基于消息传递且具有高度容错特性的一致性算法，是目前公认的解决分布式一致性问题。

在常见的分布式系统中，总会发生诸如机器宕机或网络异常等情况，Paxos算法需要解决的问题就是如何在一个可能发生上述异常的分布式系统中，快速且正确地在集群内部对某个数据的值达成一致，并且保证不论发生以上任何异常，都不会破坏整个系统的一致性。

问题描述

假设有一组可以提出提案的进程集合，那么对于一个一致性算法来说需要保证以下几点：

• 在这些被提出的提案中，只有一个会被选定。
• 如果没有提案被提出，那么就不会有被选定的提案。
• 当一个提案被选定后，进程就应该可以获取被选定的提案信息。

对于一致性来说，安全性需求如下：

• 只有被提出的提案才能被选定。
• 只能有一个提案被选定。
• 一个进程不会知道哪个提案被选定了，除非这个提案真的被选定了。

在该一致性算法中，有三种参与角色，我们用Proposer、Acceptor和Learner来表示。在具体的实现中，一个进程可能扮演一个或多个角色。

假设不同参与者之间可以通过收发信息来进行通信，在这里我们使用传统的异步、非拜占庭模型（即不考虑拜占庭问题，参与者之前通信可能丢失或重复，但是不会被篡改），那么：

• 参与者可以以任意速度执行，可能出错、停止，也可能重启。在一个提案被选定后，所有参与者都有可能出错并重启，因此除非这些参与者可以记录某些信息，否则将无法解决出错重启问题。
• 消息在传输过程中可能会出现不可预知的延迟，也可能会重复或丢失，但是消息不会被损坏，即消息内容不会被篡改（即非拜占庭模型）。

提案选定

只有一个Acceptor的情况是最简单的。Proposer向Acceptor发送提案，Acceptor选择接收到的第一个提案作为选定的提案。这个方案无法解决单机失效问题，如果Acceptor停机，整个系统将会无法工作。

接下来我们看看，在存在多个Acceptor的情况下，如何进行提案的选取：Proposer向一个Acceptor集合发送提案，同样，集合中的每个Acceptor都可能会批准该提案，当有足够多（大多数，一般是大于半数）的Acceptor批准这个提案的时候，我们就可以认为该提案被选定了。

在没有失败和消息丢失的情况下，如果只有一个提案被提出，我们希望选定该提案，这就要求：
P1：一个Acceptor必须批准它收到的第一个提案。
但是这个要求会引出另一个问题，多个Proposer在同一时间提出了多个提案，这可能会导致虽然每个Acceptor都批准了它收到的第一个提案，但是没有一个提案是被多数人批准的。即使只有两个提案，也有可能导致上述问题（比如2个提案，2n+1个Acceptor，这两个提案分别被n个Acceptor通过，那么最后一个Acceptor挂掉就会导致无法产生确定选哪个提案）。

P1的要求再加上一个天被选定需要半数以上的Acceptor批准的要求，暗示着一个Acceptor必须能够批准不止一个提案。我们通过使用全局唯一的编号来标识每一个被Acceptor批准的提案，因此提案由一个编号以及一个Value组成，且不同的提案有不同的编号（如何生成这种编号，这里不关注）。当一个具有Value值的提案被大多数Acceptor通过后，我们就认为该Value被选定了，此时我们也认为该提案被选定了。
我们允许多个提案被选定，但同时必须要保证所有被选定的提案都有相同的Value值。结合提案编号，该约束可以定义如下：
P2：如果一个Value=v的提案被选定了，那么所有比它编号更高的被选定的提案，其Value也必须是v。
因为提案的编号是全序的，那么P2就保证了只有一个Value值被选定这一关键安全性属性。另外，一个提案要被选定，首先必须要被只要一个Acceptor批准，因此我们可以通过满足以下条件来满足P2。
P2a：如果一个Value=v的提案被选定了，那么所有比它编号更高的被Acceptor通过的提案的Value值也必须是v。
我们仍然需要P1来保证提案会被选定，因为通信是异步的，一个提案可能会在某个Acceptor c还未收到任何提案时就被选定了。假设一个Proposer苏醒了，然后产生了一个具有另一个Value值的更高编号的提案，根据P1，就需要c通过这个提案，但是这与P2a矛盾，所以我们需要对P2a进行强化：
P2b：如果一个Value=v的提案被选定了，那么所有比它编号更高的被Proposer提出的提案的Value值也必须是v。
因为一个提案要被Acceptor批准之前必须先由Proposer提出，所以P2b包含P2a，进而隐含了P2。所以只要证明P2b成立即可：
假设某个提案[M0,V0]已经被选定了，证明任何编号Mn>M0的提案，其Value值都是V0。

数学归纳法证明