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

税率已定为 10%, 新的提案不得再讨论本问题. 一致性得到了保证.

2. A5 是个无足轻重的小人物. 这时 A3 不再理会他, A1 不久后就会广播税率定为 10%.

情况三 在这个情况中, 我们将看见, 根据提案的时间及提案者的权势决定是否应答是有意义的. 在这里,时间和提案者的权势就构成了给提案编号的依据. 这样的编号符合'任何两个提案之间构成偏序'的要求.

A1 和 A5 同样提出上述提案, 这时 A1 可以正常联系 A2 和 A3; A5 也可以正常联系这两个人. 这次 A2 先收到A1 的提案; A3 则先收到 A5 的提案. A5 更有权势.

A1没有达到多数，A5达到了，于是 A5 将主持投票, 决议的内容是 A5 提出的税率 20%.

有更大的人物关注此事, 请等待他做出决定. 另外, 在这种情况下, A4 与外界失去了联系. 等到他恢复联系, 并需要得知税率情况时,他(在最简单的协议中)将提出一个提案:

税率已在之前的投票中定为 20%, 你不要再来烦我! 决议的发布 一个显而易见的方法是当 acceptors 批准一个 value时，将这个消息发送给所有 learner。但是这个方导致消息量过大。

由于假设没有 Byzantine failures，learners 可以通过别的 learners 获取已经通过的决议。因此acceptors 只需将批准的消息发送给指定的某一个 learner，其他 learners向它询问已经通过的决议。这个方法降低了消息量，但是指定 learner 失效将引起系统失效。

因此 acceptors 需要将 accept 消息发送给 learners 的一个子集，然后由这些 learners 去通知所有learners。

但是由于消息传递的不确定性，可能会没有任何 learner 获得了决议批准的消息。当 learners需要了解决议通过情况时，可以让一个 proposer 重新进行一次提案。注意一个 learner 可能兼任proposer。

Progress 的保证 根据上述过程当一个 proposer发现存在编号更大的提案时将终止提案。这意味这提出一个编号更大的提案会终止之前的提案过程。如果两个 proposer在这种情况下都转而提出一个编号更大的提案，就可能陷入活锁，违背了 Progress 的要求。这种情况下的解决方案是选举出一个leader，仅允许 leader 提出提案。但是由于消息传递的不确定性，可能有多个 proposer 自认为自己已经成为leader。Lamport 在ThePart-Time Parliament一文中描述并解决了这个问题。

其他 微软公司为简化的 Paxos 算法申请了专利。但专利中公开的技术和本文所描述的不尽相同。

谷歌公司（Google 公司）在其分布式锁服务（Chubbylock）中应用了Paxos算法。Chubbylock 应用于大表（Bigtable），后者在谷歌公司所提供的各项服务中得到了广泛的应用。

参考文献 The Part-Time Parliament ── Lamport 于1998年发表在 ACM Transactionson Computer Systems。 注：这是该算法第一次公开发表。 Paxos Made Simple，2001年。 注：Lamport觉得同行无法接受他的幽默感，于是用容易接受的方法重新表述了一遍。 Pinewiki对Paxos算法的介绍Lamport 本人在

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