要在分布式环境下达成一致性协议，需要满足某些约束。在《Paxos Made Simple》中，Lamport 老爷子解释了如何以约束条件逐渐加强的方式推导出 Paxos 分布式一致性算法。且 Lamport 老爷子指出，为了满足这些约束，最终形成类似 Paxos 的算法几乎是不可避免的（almost unavoidably），比如同一时期（Liskov & Oki, 1988）在《Viewstamped replication》中作为数据副本存储系统实现的一部分也独立的发明了一个分布式一致性算法，但它们的基本原理是一致的（Lampson, 1996）。

下面顺着《Paxos Made Simple》论文中的思路，我们来理一理 Paxos 算法的逻辑。

达成一个共识最简单的方式就是假设只有一个决策者，这样它只须选择收到的第一个提议作为决策即可。虽然简单，但这种方式不可靠，一旦这个唯一决策者故障，后果不可预计。

所以，我们需要多个决策者。在多个决策者的情况下，由于提议者可能发送了多个提议，为了确保只选出一个值，我们需要规定只有大多数决策者都同意的提议才能最终做为被选中（chosen）的值（quorum 概念）。由于两个大多数的集合必然有一个共同者，所以在一个决策者只能选择一个值的情况下我们可以保证正确。

在没有失败或消息丢失的情况下，为了在仅有一个提议者只提出一个值的情况下也能选出提议，我们需要要求：

P1. 一个决策者必须接受它收到的第一个提议。
P1. An acceptor must accept the first proposal that it receives.

但这个要求有个问题。假设有多个提议，如果没有一个提议被超过多数决策者接受——比如最简单的，总共有 3 个决策者，有 3 个提议，分别作为第一个提议发送到 3 个决策者。即使只有 2 个提议也可能由于恰好某个决策者故障而导致剩余无法形成多数。——会导致无法选出决策。

因此，P1 + Quorum 约束隐含着要达成协议，决策者需要能接受多个提议值。而为了跟踪和区别不同的提议，我们给所有提议分配一个不同的编号。因此每个提议从此就由 2 部分组成了：（提议编号，提议内容）。

每个决策者能接收多个提议会导致多个提议被选中。我们允许多个提议被选中但必须保证选中的每个提议都具有相同的值。通过对提议编号归纳（使其有序），使其可以保证：

P2. 如果一个值为 v 的提议被选中，那提议编号大于它的所有被选中提议都具有值 v。
P2. If a proposal with value v is chosen, then every higher-numbered proposal that is chosen has value v.

那我们就可以保证只有一个值被选中。

由于一个提议被选中，至少需要被一个决策者接受，因此我们又可以通过满足如下约束来满足 P2：

P2a. 如果一个值为 v 的提议被选中，那被任何决策者接受的编号大于它的提议都具有值 v。
P2a. If a proposal with value v is chosen, then every higher-numbered proposal accepted by any acceptor has value v.

我们仍然需要维持 P1 以保证一些提议能被选中。但考虑如下场景：某个提议可能在某个决策者完全没接收到任何提议的情况下就已被选中，而此时有个新的提议者突然“醒”了过来，并签发一个更高编号且不同值的提议至这个决策者。根据约束 P1，这个决策者必须接受这个提议，但这又违背了约束 P2a。因此如果要同时维持约束 P1 和 P2a 就需要加强 P2a 至：

P2b. 如果一个值为 v 的提议被选中，那被任何提议者签发的编号大于它的提议都具有值 v。
P2b. If a proposal with value v is chosen, then every higher-numbered proposal issued by any proposer has value v.

由于一个提议被接受前必须有提议者签发，因此 P2b 保证了 P2a，而 P2a 又保证了 P2。

如何实现才能满足 P2b 呢？这个时候主要关系已经变成同一个决策多轮提议之间如何保持一致问题。我们可以顺着如何才能证明 P2b 成立的思路来看下：

求证命题：假设编号为 m，值为 v 的提议已被选中，则任何提议者签发的任何编号为 n（n>m）的提议也具有值 v。

我们可以用数学归纳法来进行证明，这样我们可以有一个额外的假设即任何编号在 m..(n-1) 之间的签发协议也具有值 v（第二数学归纳法假设）。然后看如何才能推出编号为 n 时值为 v 也成立。

考虑一下，既然编号为 m 的提议已被选中，则此时必然已存在某个由大多数决策者组成的集合 C，并且 C 中的每个决策者都已接受了提议 m。再结合上面的额外假设，则 C 中的每个决策者都必然已接受过编号在区间 m..(n-1) 之间的提议，并且这些提议具有的值都是 v。

由于任何一个由大多数决策者组成的集合 S 都肯定至少包含一个集合 C 中的成员，因此，我们只要维持以下不变条件就能推出编号为 n 的提议也具有值 v：

P2c. 对于任意的值 v 和编号 n，如果某个时刻一个编号为 n 值为 v 的提议被签发，则此时必须存在一个由大多数决策者组成的集合 S 且（a）S 中的决策者没有任何一个曾接受过提议编号小于 n 的提议，或者（b）v 是 S 中决策者接受过的所有提议中编号小于 n 且是最大的提议的值。
P2c. For any v and n, if a proposal with value v and number n is issued, then there is a set S consisting of a majority of acceptors such that either (a) no acceptor in S has accepted any proposal numbered less than n, or (b) v is the value of the highest-numbered proposal among all proposals numbered less than n accepted by the acceptors in S.

这就完成了数学归纳法的最后一块拼板，也确立了同一决策多轮提议之间的关系。加上这个约束我们就可以通过数学归纳法证明上述命题的正确，因此也即我们只要维持约束 P2c 的不变性就能同时保证了约束条件 P2b。

根据 P2c 的约束，一个提议者在签发一个编号 n 提议之前，必须知道此时某个大多数决策者集合中是否已存在或将会存在已接受的编号小于 n 的提议。了解已经被接受的提议相对简单，但要判断今后是否仍会接受小于 n 的提议比较困难。因此我们换一种做法，不再去推测未来，而是要求决策者之后不会再接受不符合要求的提议。这样就催生了如下提议签发算法：

1. 一个提议者选择一个新的提议编号 n，并发送请求至一系列决策者，要求其响应：（a）承诺不再接受任何编号小于 n 的提议，且（b）如果已接受过编号小于 n 的提议，则返回编号小于 n 且最大的提议。我们称此请求为带编号 n 的 prepare 请求。
2. 如果提议者收到了符合大多数数量集决策者的响应，那它就可以以编号 n 值为 v 签发提议。v 是所有响应请求中编号最大的提议的值，如果所有决策者响应中都不包含已接受过的提议，则提议者可以自己选择一个任意的值。

提议者签发一个提议并发送请求给一系列决策者（可以和响应 prepare 请求的决策者集合不同）的过程我们称之为 accept 请求。

这就是全部提议者签发算法了。那关于决策者呢？决策者会收到 2 种类型请求：prepare 请求和 accept 请求。一个决策者可以忽略任何请求，而不会影响 Paxos 协议的安全性。所以，我们只需要说明它何时需要响应一个请求。对于 prepare 请求，一个决策者可以始终响应。但对于 accept 请求，它只有在没承诺过不接受此类提议的情况下，才能接受这个提议并做出响应，也即：

P1a. 一个决策者有且只有在没有响应过编号比 n 大的 prepare 请求的情况下才能接受编号为 n 的提议。
P1a. An acceptor can accept a proposal numbered n iff it has not responded to a prepare request having a number greater than n.

显然，P1a 约束包含了约束 P1。

至此，我们就拥有能满足所有约束条件要求的完整算法了！下面的介绍是对算法做一些小优化。

假设某个决策者接收到了编号为 n 提议的 prepare 请求，如果它在已响应过编号大于 n 的提议的 prepare 请求的情况下，显然它已经不会接受后续编号为 n 的 prepare 请求，因此我们可以要求决策者不响应类似 prepare 请求。另外我们也要求决策者忽略他已经接受的提议的 prepare 请求。

在这个优化之后，一个决策者只需要记住它曾接受过的编号最高的提议以及它响应过的 prepare 请求的最高编号。因为 P2c 约束要求即使在故障的情况也要保持不变性，因此决策者要求即使在故障或重启等情况下也要记住这些信息。需要注意的是提议者可以随时丢弃它的提议，只要它不会以相同的编号来签发其他提议。

把提议者和决策者的操作放在一起，我们就得到了下面两阶段的算法：

阶段1. （a）提议者选择一个提议编号 n 并发送 prepare 请求至大多数决策者。（b）决策者收到 prepare 请求并发现 n 大于任何它已经响应过的请求情况下，做出不再接受任何编号小于 n 的提议的承诺并返回他曾经接受过的编号小于 n 且最大的提议（如果有的话，没有则返回空）。

阶段2. （a）如果提议者从符合大多数数量集决策者中接收到了编号 n 的 prepare 请求的响应，那他可以发送编号为 n 值为 v 的 accept 请求到决策者，其中 v 是响应中编号最大的提议的值，或者可以是任意值如果没有相关提议返回。（b）决策者接收到编号为 n 的 accept 提议请求，除非它已经响应了编号大于 n 的提议的 prepare 请求，否则它接受这个协议。

只要遵照此算法，提议者可提出多个提议。并且它可以在协议过程中随时放弃提议，因为正确性也能得到保证。因此另一个可以优化的点是当某个决策者因为已经收到了比这个提议者提议编号更高的 prepare 请求而忽略当前提议的 prepare 或 accept 请求时，可以通知提议者放弃提议。当然这只是一个不影响正确性上的性能优化。

学习者想知道哪个是被选中的值，需要先找出被大多数决策者接受的提议。学习选中提议的算法比较简单，比如可以让一个决策者在接受某个提议后就通知所有的 learner 或通知某个 learner 或通知部分 learner，这个主要从性能及可靠性（多个 learner 更可靠但性能更低）等方面去考虑。一个 learner 通过让某个提议者执行一遍上述的共识算法也能获取到哪个值被选中了。

算法活性或进展性方面，如果有两个提议者 p 和 q，比如 p 通过阶段 1 发了编号 n1，q 又通过阶段 1 发了编号 n2 > n1，这个时候 p 因为阶段 2 无法通过又执行阶段 1 发了编号 n3 > n2… 这样一直下去就陷入了死循环，使程序无法取得进展。因此为了保证进展性，需要选择一个唯一的提议者进行提议。这样它就可以较快的选定一个可用的编号，并且在系统大多数功能正常的情况下正常的工作下去。不过著名的 FLP不可能原理告诉我们，即使选举唯一的提议者，也可能无法取得进展，因此需要使用一些随机性技术或时钟技术——比如超时机制。当然，不管选举 leader 是否能够成功，安全性是始终能够得到保证的。

具体实现方面，我们以分布式确定状态机系统为例子。这个例子里有提议者（proposer）、决策者（acceptor）和学习者（learner）3 个角色，每个进程会都同时扮演这 3 个角色，另外还会选举出唯一的 leader 和唯一的 learner。Paxos 算法就是如上所述。请求响应都是普通消息（且不会有拜占庭错误），数据都保存在可靠的设备上。选择提议编号时使用了各自不同的数据集所以不会有两个提议共用同一个提议编号的情况，每个提议者在签发下一个提议时都会使用更高的一个提议编号。

首先有一组服务器，每个机器上都实现了一个确定状态自动机，因此只要输入相同的命令则状态机的输出也必然相同。为了保证所有服务器上状态机都执行相同序列的状态机命令，我们需要实现一系列独立的 Paxos 算法 instance（我们称 Paxos 算法通过多轮 prepare/accept 来确定一个值的过程为一个 instance），第 i 个 instance 选中的值就作为状态机命令序列中的第 i 个命令。当前，我们先假定这个集群服务器集合是固定的，不会有新机器加入和机器离开。

正常情况下，某个服务器会被选为 leader（选举过程可能实在太简单，老爷子并未提，微信 PhxPaxos 实现者 LynnCui 提了一个比较好的思想可参考），由 leader 进行提议以及决定命令放在序列中的哪个位置。在正常情况下，leader 的操作都能成功，只有在故障或其他也有机器认为自己是 leader 并和它产生了不一致意见的情况下可能会失败。不过失败都不会影响 Paxos 算法的一致性。

上面都是正常状态的描述，下面看下故障情况下会发生什么事，比如之前 leader 失效并选出了一个新的 leader（系统刚启动时是一个特殊情况，因为此时还没有任何提议被提出）。

新的 leader，之前作为 learner，应该已经学习到了大部分已经被选中的命令。假设它已知道命令 1-134，138 和 139 ——也就是 Paxos 算法中第 1-134，138 和 139 个 instance 中选出的值（我们一会再来看如何会产生命令序列中的这些间隔）。然后 leader 执行 135-137，以及所有大于 139 的 instance 阶段 1，假设 135 和 140 这两个 instance 返回了接受过的提议的值，其他 instance 都未返回（也即不受约束，可以选择任意值），于是 leader 为 135 和 140 两个 instance 执行阶段 2，从而选出命令值。

到此时，所有已经学习到 1-135 命令的机器都可以执行这些命令了，但 138-140 号命令还不行，即使他们可能也已经知道了，因为命令 136 和 137 还没有选出。这个时候，leader 可以等待客户端再发送两个请求来作为这两个序号的命令，也可以直接使用一些无用操作比如“no-op”来填上这些间隙以便快速执行（no-op 操作是指不会改变状态机状态的命令，为什么可以使用 no-op 填充是因为当前 leader 执行阶段 1 时 136 和 137 未返回任何已接受提议的值（ MaxVote 值），也即之前的 leader 并未等这两个提议产生 accept 请求就已经执行 137 后面的 instance 了，也就是说之前的 leader 认为 136 和 137 的顺序对后续命令不重要，所以现在的 leader 也理所当然可以填补其他命令值或直接填一个空命令。关于这部分解释及 MaxVote 概念等可以参考《The Part-Time Parliament》里面有解释说明）。一旦 136 和 137 的间隙被填上，则 138-140 号命令也可以接着被执行了。

接下来 leader 就可以选一个客户端发过来的值作为下一个命令—— 141 号命令 instance 这样正常执行下去。leader 也可以在 141 还没确定被选中的情况下又开始提议 142 号命令，但这时可能 141 号命令数据会丢失导致 142 被选出来的情况下 141 仍未选出。如果 leader 正好故障，那就此产生了一个间隔。假设 leader 可以提前提议 a 个命令，就可能会产生 a-1 大小的间隔。

由于 leader 的失效通常是小概率事件，因此算法的效率方面主要消耗在达成协议方面，也就是共识算法的阶段 2。而阶段 2 基本上可以证明是有故障情况下达成共识的最高效方式了，因此，整个 Paxos 算法也基本上已经是最优的了（关于 Paxos 效率优化，可以参考《Paxos Made Live》中 Multi-Paxos 等改进）。

当前讨论的都是假设有一个唯一的 leader，在没有唯一 leader 的情况下，可能没有提议者发起提议或多个提议者可能发起多个提议，由于有 Paxos 算法保证，安全性不会受影响，选举出一个 leader 只是为了保障可进展性（以及性能，注意和 master 区别）。

如果服务器的集合发生了变更，那就需要有方法能确定哪些服务器执行了哪些共识算法的 instance（Paxos 算法是基于服务器集合不变的前提之下的，因此一个 instance 执行期间服务器集合不能变。不过每个 instance 都是独立的 Paxos 算法，所以多个 instance 之间服务器集合可变更）。一种最简单的方式就是使用当前的状态机机制本身，服务器集合变更作为状态机的命令来执行。

参考资料：
[1] Paxos made simple 及中文翻译版（dsdoc.net, by oldratlee & duanple）
[2] The part-time parliament 及中文翻译版（Paxos算法中文翻译）
[3] Paxos理论介绍(1-4). by LynnCui
[4] Time, clocks, and the ordering of events in a distributed system
[5] Paxos Made Live
[6] Impossibility of distributed consensus with one faulty process
[7] 分布式系统领域经典论文翻译集. by duanple
[8] Leases 一种解决分布式缓存一致性的高效容错机制