spring mvc工作原理_paxos 算法_哈希(2)

约束2并不要求只批准一个提案, 暗示可能存在多个提案。只要提案的 value 是一样的，批准多个提案不违背约束2。于是可以产生约束P2：

P2：一旦一个具有 value v 的提案被批准(chosen)，那么之后批准(chosen)的提案必须具有 value v。注:通过某种方法可以为每个提案分配一个编号，在提案之间建立一个全序关系，所谓“之后”都是指所有编号更大的提案。

如果 P1 和 P2 都能够保证，那么约束2就能够保证。

批准一个value意味着多个acceptor接受(accept)了该value. 因此,可以对P2 进行加强：

P2a：一旦一个具有 value v 的提案被批准(chosen)，那么之后任何 acceptor再次接受(accept)的提案必须具有 value v。 由于通信是异步的，P2a 和 P1 会发生冲突。如果一个 value被批准后，一个 proposer 和一个 acceptor 从休眠中苏醒，前者提出一个具有新的 value 的提案。根据P1，后者应当接受，根据 P2a，则不应当接受，这中场景下 P2a 和 P1 有矛盾。于是需要换个思路，转而对 proposer的行为进行约束：

P2b：一旦一个具有 value v 的提案被批准(chosen)，那么以后任何 proposer 提出的提案必须具有 valuev。 由于acceptor能接受的提案都必须由proposer提出，所以P2b 蕴涵了 P2a，是一个更强的约束。

但是根据 P2b 难以提出实现手段。因此需要进一步加强 P2b。

假设一个编号为 m 的 value v 已经获得批准(chosen)，来看看在什么情况下对任何编号为 n（n>m）的提案都含有value v。因为 m 已经获得批准(chosen)，显然存在一个 acceptors 的多数派 C，他们都接受(accept)了v。考虑到任何多数派都和 C 具有至少一个公共成员，可以找到一个蕴涵 P2b 的约束 P2c：

P2c：如果一个编号为 n 的提案具有 value v，那么存在一个多数派，要么他们中所有人都没有接受(accept)编号小于 n的任何提案，要么他们已经接受(accpet)的所有编号小于 n 的提案中编号最大的那个提案具有 value v。可以用数学归纳法证明P2c 蕴涵 P2b：

假设具有 value v 的提案 m 获得批准，当 n=m+1 时，采用反证法，假如提案 n 不具有 valuev，根据P2c，则存在一个多数派S1，要么他们中没有人接受过编号小于 n 的任何提案，要么他们已经接受的所有编号小于 n的提案中编号最大的那个提案不具有 valuev。由于S1和通过提案m时的多数派C之间至少有一个公共的acceptor，所以以上两个条件都不成立，导出矛盾从而假设，证明了提案n 必须具有 value v；

若 (m+1)..(n-1) 所有提案都具有 value v，采用反证法，假如新提案 n 不具有 valuev，根据P2c，则存在一个多数派S2，要么他们没有接受过 0..(n-1) 中的任何提案，要么他们已经接受的所有编号小于 n的提案中编号最大的那个提案不具有 value v。由于S2和通过 m 的多数派 C 之间至少有一个公共的acceptor，所以至少有一个 acceptor 曾经接受了 m，从而也可以推出 S2 中已接受的所有编号小于 n的提案中编号最大的那个提案的编号范围在 m..(n-1) 之间，而根据初始假设，m..(n-1)之间的所有提案都具有 valuev，所以 S2 中已接受的所有编号小于 n 的提案中编号最大的那个提案肯定具有 value v，导出矛盾从而新提案 n 不具有value v 的假设。paxos 算法根据数学归纳法，我们证明了若满足P2c，则P2b一定满足。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-28610-2.html