该版本为Leslie Lamport的文章“Paxos Made Simple”的译文，该译文只包含了文章的主体部分，第一部分背景和最后一部分的状态机的实现没有翻译。
现在的版本为刚刚翻译好，还没有修订，今日将重新更新。
希望对研究分布式系统的学者有一定的用途。
2 一致性算法
2.1 问题
假设许多节点都可以提交提议（value），一致性算法需要保证在所有被提出的提议中只有一个能够被接受，如果没有提议被提出，那么也不会有提议被选择。如果某个提议一旦被选择，那么其他的节点能够知道所选择的提议，总之，一致性的保证需要满足以下条件：
q 提议只能被提出后才能被选择
q 算法的一次执行实例中只能选择一个提议
q 提议只能被选中后才能让其他节点（learner）所知道
该算法保证的目的是某个提出的提议能够最终被选择，而且一旦被选中后，其他节点能够最终知道这个值。
在一致性算法中有三种角色：提议者（proposers）、批准者（acceptors）、学习者（learners）。提议者提出提议，批准者负责批准提议，而学习者主要学习提议。在具体实现中，某个节点可以担当多个角色。
假设节点之间通过发送消息进行通信，这里我们使用常用的异步、非拜占庭模型，该模型中：
q 节点以任意的速度进行操作，可能因为故障而停止，也可以重新启动。并且节点所选择的值不会因为重启等其它故障而消失。
q 消息可以延迟发送、多次发送或丢失，但不会被篡改（即不存在拜占庭问题）。
2.2选择提议
选择提议的最简单的方法就是采用唯一的批准者，当提议者发送提议给批准者，批准者只需要选择他所接受到的第一个提议即可，这种方法虽然简单，但是批准者一旦发生故障，那么将无法进行之后的过程。因此，我们采用多个批准者的方法，此时提议选择规则如下：
R：当提议被大多数的批准者所批准，则表明该协议被批准。
提议者将提议发送给批准者的一部分，每个批准者都可以批准提议。如果一个批准者最多只能批准一个协议，那么将大多数设置为超过半数即可。这样一定能够保证系统只有一个协议被批准，否则将与超过半数的约束相违背。
在不发生故障或消息丢失的情况下，假如只有某个提议者提出了一个提议，如果我们希望该提议能够被接受，这就要求：
P1：一个批准者必须批准它所收到的第一个提议。
这个要求会产生一个问题：在该约束下，同一时刻不同的提议者可能会发出不同的提议，那么可能会发生每一个批准者都批准了一份提议，但是没有却没有哪一个提议被大多数人同时批准。即使只有两个提议，如果每个提议恰好被半数的批准者所批准，这时就无法判定到底哪个提议才能被选择。
在一个系统中，一个批准者应该需要被设置为可以批准多个提议。以数据存储为例，一个分部式存储系统中不可能只存在一份数据。为了区分批准者批准的提议，每个提议都分配有版本号，这样一个提议就包含了版本号（proposal number）和提议的值（value）。为了避免混淆，不同的提议拥有不同的版本号。因此，我们说某个提议被选定是指拥有该值的提议被大部分批准者所批准。
我们允许有多个提议被选中，但是必须保证这些提议拥有相同的内容，应此需要满足约束P2：
P2：如果某个提议被选定，那么之后选定的提议必须拥有相同的值。(针对系统还是节点？)
由于版本号是有序且单调增加的，那么约束P2能够保证只有一个“值”被选定。由于提议被选定至少需要一个批准者批准，因此为了安全起见，我们可以将P2修改为：
P2a：如果某个提议被选定，那么之后批准者只能批准拥有相同值的提议。
由于通信是异步的，因此某个特别的批准者可能会批准具有不同值的提议。例如一个新的提议者刚刚加入，并且提出了一个拥有高版本号但是不同值的提议。那么该提议可能会被一个从来没有接受过任何提议的批准者所批准（根据P1约束）。那么这将和P2a约束相违背。
如果想要让系统同时满足P1和P2a约束，那么P2a需要修改为：
P2b：如果某个提议被选定，那么之后任何提议者只能提出具有相同值的提议。
因为只有某个提议被批准之后新的提议才能被提出。约束P2b隐含了约束P2a，也隐含了P2。
假设一个版本号为 m 值为v的提议已经被选中，我们必须保证任何版本号为n（n>m）的提案都拥有相同的值v。既然m 已经被选中，显然最终会存在一个批准者的多数派 C，他们都批准了v。考虑到任何多数派都和 C 具有至少一个公共成员，可以找到一个蕴涵 P2b 的约束：
P2c：对于任意的v和n，如果带有值v版本号为n的提议被某个提议者提出，那么在一个批准者的大多数集S中，要么a）S中没有批准者接收到版本号小于n的提议；要么b）v是S中版本号低于n的提议中具有最高版本号提议的值。
我们可以通过保持P2c的不变性来满足P2b。
为了满足P2c的不变性，若一个想要发起版本号为n的提议者，那么它必须知道系统中已经被或将要被大多数集所批准的版本号小于n的提议。想要知道系统中已经被批准的提议是非常容易的事情，但是预测将来可能被批准的提议是非常困难的。因此在Paxos中，提议者要求批准者这不会批准任何版本号低于n的提议。该解决方案可以用如下算法来描述，表示如何来发起提议：
1 提议者选择一个新的版本号n并发送一个请求到一个批准者大多数集S中的每个成员，该请求要求：
a）每一个批准者承诺不会接受版本号低于n的提议。
b）如果批准者曾经批准过版本号低于n的提议，那么批准者需要将该信息发送给新的提议者。
我们将该请求称为版本号n的“准备请求”。
2 如果提议者接收到来自大多数集S中所有批准者的请求响应，那么该提议者可以发起一个版本号为n，值为v的提议。这里v的值为所有响应中版本号最高的提议的值，或者如果新提议者没有接收到任何回应，那么它可以自行指定提议的值。
一个提议者通过向大多数集（该大多数集不一定要和“准备请求”所涉及的大多数集相同）发送关于新提议的请求，我们将该请求称为“批准请求”。
上面是关于提议者的算法描述。那么批准者方面如何呢？批准者方面将接收到来自提议者的两类请求：准备请求和批准请求。在系统中，批准者可以忽略任何一种请求而不会给系统带来影响。如果批准者可以对请求做出相应，那么：批准者可以对任意的“准备请求”做出响应；如果批准者没有许诺过不在批准提议，那么它将可以对任意的“批准请求”作出响应，并批准该提议。也就是说：
P1a：批准者可以接受版本号为n的提议当且仅当它没有响应过版本号大于n的“准备请求”。
可以看到P1a蕴含了P1的内容。
现在我们已经有了一个满足Paxos安全特性的完整算法，我们将对其进行优化从而得出最终版本的算法。
假定一个批准者接受到了版本号为n的“准备请求”，但是它已经响应了另一个版本号大于n的“准备请求”。那么它将不会批准该版本号为n的提议，因此它也不会对任何版本号为n的新提议做出响应，即它将忽略该“准备请求”。此外，它也不会对已经批准的提议的“准备请求”做出响应。
在该优化下，一个批准者仅需要记录被它批准过的提议的最高版本号，以及曾响应过的“准备请求”所对应的最高版本号。因为P2c必须保持不变性而不用考虑故障等问题，所以一个批准者及时发生故障重启也必须要记录这些信息。注意：提议者可以随时终止自己所发起的提议并且不记录该信息，但是它不能再次发起具有与终止提议相同版本号的提议。
下面，我们将上述提议者与批准者两方面的操作合并起来，该算法将包括如下两个阶段：
阶段1：
（a） 提议者选择一个恰当的版本号n并发送一个版本号为n的“准备请求”到一个批准者的大多数集；
（b） 如果某个批准者接受到的该“版本请求”，并且n大于之前该批准者所响应过的任意准备请求的版本号，那么此批准者将向该提议者承诺不会再响应任何版本号小于n的提议，并告知批准者它曾经批准过的提议的最高版本号。
阶段2：
（a） 如果提议者接收到了来自大多数集的对于其关于版本号为n的“准备请求”的相应信息，那么它向该（或其它）大多数集发送关于“版本号为n、值为v的提议”的“批准请求”，1）如果该相应信息不为空，其中v的值为该响应信息中最高版本号提议的值；2）如果该相应信息为空，那么提议者可以自主指定新的提议的值。
（b） 如果某批准者接收到了关于版本号为n的提议的 “批准请求”，那么除非它曾响应过版本号大于n的提议的“准备请求”，否则它将批准该提议。
一个提议者可以发起多个提议，只要它的每一步操作遵循该算法。一个提议者也可以在发起提议的中间任何时刻终止该操作（即便是关于某提议的请求或响应可能会再终止操作之后很长时间才到达，这也不会系统的正确性）。因此，如果某批准者接收到了更高版本的提议，那么它应该终止关于“旧”版本提议的请求，并通知该提议的提议者以便该提议者可以终止关于该提议的操作。
2.3学习选择的提议
为了能够学习已被批准的提议，学习者需要能够找到被大多数集所批准的提议。比较直观的算法是：每当批准者批准了一个提议，该批准者将此提议信息发送给每一个学习者得知。但是此种方法产生的通讯量过大会加重系统的负担。
在非拜占庭模型下该问题比较容易解决。我们可以让批准者把批准的提议发送给不同于自己的学习者得知，然后该学习者又通知其他学习者该信息。虽然问题能够解决，但是当中间某个学习者出现故障，则之后的学习者将不能够收到该信息。
那么介于前者所提到的两个解决方案，我们可以令批准者将关于提议的信息发送给某几个不同的学习者得知，然后这些学习者在通知其他学习者该信息。
尽管使用上述方法，但是在某些特殊的情况下，学习者也可能收不到任何提议批准的信息。那么我们是否可以令学习者向批准者询问关于是否有提议被批准呢？答案是否定的，因为即使不考虑故障在内，并不是所有的批准者拥有最新的提议信息。那么如何让学习者能够主动的获取到最新提议信息呢？我们可以让学习者充当一个提议者来发起一个新的提议。
2.4其他问题
系统可能会有两个不同的提议者不短尝试提出更高版本的提议的情况发生，并且任何一个都不会被选在为提议。例如，提议者p在第一阶段提出版本号为n1的提议，另一个提议者q在第一阶段提出版本号为n2的提议，并且n2>n1。在提议者p的第二个阶段，版本号为n1的提议将被忽略，因为更高版本号为n2的提议被提出，那么提议者p可能尝试提出版本号为n3的新提议，且n3>n2。那么这将反过来导致提议者q在第二阶段的失败，然后q又尝试提出更高版本的提议，那么周二复始将一直不会有提议被批准。
为了保证程序的正常运行，系统需要能够选出某个提议者作为唯一的提议者来发出提议。如果该提议者都能够和一个大多数集进行有效的通讯，并且它所提出的提议版本号大于其他版本的提议，那么显然，这个提议将被批准。
如果某提议者在发起提议的过程中发现系统中存在比自己提议更高的版本，那么它将立即停止该提议过程。并再次尝试发起更高版本的提议，在一次或者多次尝试后，该提议者将最终成功发起提议。对于该选择过程，可以使用随机算法或根据真实时间。