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

P2c 是可以通过消息传递模型实现的。另外，引入了 P2c 后，也解决了前文提到的 P1 不完备的问题。

算法的内容 要满足 P2c 的约束，proposer 提出一个提案前，首先要和足以形成多数派的 acceptors进行通信，获得他们进行的最近一次接受(accept)的提案（prepare 过程），之后根据回收的信息决定这次提案的value，形成提案开始投票。当获得多数 acceptors 接受(accept)后，提案获得批准(chosen)，由proposer 将这个消息告知 learner。这个简略的过程经过进一步细化后就形成了 Paxos 算法。

在一个paxos实例中，每个提案需要有不同的编号，且编号间要存在全序关系。可以用多种方法实现这一点，例如将序数和 proposer的名字拼接起来。paxos 算法如何做到这一点不在 Paxos 算法讨论的范围之内。

如果一个最近一次接受(accept)的提案编号为 m 的acceptor 在 prepare 过程中回答了一个 proposer针对提案 n (n > m)的问题，但是在开始对 n 进行投票前，又接受(accept)了编号小于 n 的另一个提案（例如n-1），如果 n-1 和 m 具有不同的 value，这个投票就会违背 P2c。因此在 prepare 过程中，acceptor进行的回答同时也应包含承诺：不会再接受(accept)编号小于 n 的提案。这是对 P1 的加强：

P1a：当且仅当 acceptor 没有回应过编号大于 n 的 prepare 请求时，acceptor 接受(accept)编号为n 的提案。 现在已经可以提出完整的算法了。

决议的提出与批准 通过一个决议分为两个阶段：

实例 用实际的例子来更清晰地描述上述过程:

有 A1, A2, A3, A4, A5 5位议员, 就税率问题进行决议. 议员 A1 决定将税率定为 10%,因此它向所有人发出一个草案. 这个草案的内容是:

现有的税率是什么? 如果没有决定, 则建议将其定为 10%. 时间: 本届议会第3年3月15日; 提案者: A1 在最简单的情况下,没有人与其竞争; 信息能及时顺利地传达到其它议员处.

于是, A2-A5 回应:

税率已定为 10%, 新的提案不得再讨论本问题. 这实际上退化为二段提交协议.

现在我们假设在 A1 提出提案的同时, A5 决定将税率定为 20%:

现有的税率是什么? 如果没有决定, 则建议将其定为 20%. 时间: 本届议会第3年3月15日; 提案者: A5草案要通过侍从送到其它议员的案头. A1 的草案将由4位侍从送到 A2-A5 那里. 现在, 负责 A2 和 A3的侍从将草案顺利送达, 负责 A4 和 A5 的侍从则不上班. A5 的草案则顺利的送至 A3 和 A4 手中.

现在, A1, A2, A3 收到了 A1 的提案; A3, A4, A5 收到了 A5 的提案. 按照协议, A1, A2, A4,A5 将接受他们收到的提案, 侍从将拿着

而 A3 的行为将决定批准哪一个.

情况一 假设 A1 的提案先送到 A3 处, 而 A5 的侍从决定放假一段时间. 于是 A3 接受并派出了侍从. A1等到了两位侍从, 加上它自己已经构成一个多数派, 于是税率 10% 将成为决议. A1 派出侍从将决议送到所有议员处:

税率已定为 10%, 新的提案不得再讨论本问题. A3 在很久以后收到了来自 A5 的提案. 由于税率问题已经讨论完毕,他决定不再理会. 但是他要抱怨一句:

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