另外还需要保证 Progress。这一点以后再讨论。 作者通过不断加强上述3个约束(主要是第二个)获得了 Paxos 算法。 批准 value 的过程中,首先 proposers 将 value 发送给 acceptors,之后 acceptors 对 value 进行批准。为了满足只批准一个 value 的约束,要求经"多数派(majority)"批准的 value 成为正式的决议(称为"通过"决议)。这是因为无论是按照人数还是按照权重划分,两组"多数派"至少有一个公共的 acceptor,如果每个 acceptor 只能接受一个 value,约束2就能保证。 于是产生了一个显而易见的新约束:
P1:一个 acceptor 只能批准它接收到的第一个 value。
注意 P1 是不完备的。如果恰好一半 acceptor 批准 value A,另一半批准 value B,那么就无法形成多数派,无法批准任何一个值。 P1 暗示可能存在多个提案。约束2并不要求只通过一个提案。只要提案的 value 是一样的,通过多个提案不违背约束2。通过某种方法可以为每个提案分配一个编号,在提案之间建立一个全序关系,后提出的提案编号大。于是可以产生约束 P2:
P2:一旦一个 value 被通过,那么之后通过的 value 必须和这个 value 一样。
如果 P1 和 P2 都能够保证,那么约束2就能够保证。 对 P2 进行加强:
P2a:一旦一个 value v 被通过,那么之后任何 acceptor 再批准的 value 必须是 v。
P2b:一旦一个 value v 被通过,那么以后 proposer 提出的新提案必须具有 value v。
P2b 蕴涵了 P2a,是一个更强的约束。 但是根据 P2b 难以提出实现手段。因此需要进一步加强 P2b。 假设一个编号为 m 的 value v 已经获得通过,来看看在什么情况下对任何编号为 n(n>m) 的提案都含有 value v。因为 m 已经获得通过,显然存在一个 acceptors 的多数派 C,他们都批准了 v。根据 P2b,所有编号 m..(n-1) 的提案都具有 value v。考虑到任何多数派都和 C 具有至少一个公共成员,可以找到一个蕴涵 P2b 的约束 P2c:
P2c:如果一个编号为 n 的提案具有 value v,那么存在一个多数派,要么他们中没有人批准过编号小于 n 的任何提案,要么他们进行的最近一次批准具有 value v。
可以用数学归纳法证明 P2c 蕴涵 P2b:假设具有 value v 的提案 m 获得通过,当 n=m+1 时,根据 P2c,由于任何一个多数派中至少有一个批准了 m,因此提案具有 value v;若 (m+1)..(n-1) 所有提案都具有 value v,根据 P2c,若反设新提案 n 不具有 value v 则存在一个多数派,他们没有批准过 m..(n-1) 中的任何提案。但是我们知道,他们中至少有一个人批准了 m。于是我们导出了矛盾,获得了证明。 P2c 是可以通过消息传递模型实现的。另外,引入了 P2c 后,解决了前文提到的 P1 不完备的问题。