江苏龙网

  1. 主页 > 生活百科 > >

Paxos算法被认为是类似算法中最有效的( 四 )

Paxos算法


基础协议保证了一致性却没有保证任何过程 ， 因为它只阐述了牧师可能做什么 ， 没有要求牧师应该做什么 。为了达到之前谈到的过程需求（Qrogress Requirements） ， 我们需要添加一些额外的要求使得牧师们尽快执行完2-6 步 。
考虑一种情况如果牧师q 第二步收到的选举编号b 都比之前收到的要大 ， 那么他就要放弃之前收到的所有选举 。可是在选举编号为b 的选举在未确认前 ， 可能又会收到更大编号的选举b’  ， 这样就无法通过任何法律 ， 过程也不能保证 。所以为了达到过程需求则需要一个选举成功后再发起另一个选举 。而首先应该知道服务员传递消息和牧师处理消息的时间 ， 在网络中常常通过设置timeout 来实现 ， 同样的如果超过了一定时间牧师没有收到服务员的回复 ， 则认为该服务员或者对应的牧师离开了议会大厅 。
假设牧师执行一个动作在7 分钟以内 ， 服务员传递一个消息在4 分钟以内 ， 那么一个牧师p 发送消息给牧师q  ， 希望其回复的时间应该是在22 分钟内（7+4+7+4 分钟） 。
有了上面时间的假设 ， 再考虑上面讨论过的情况 ， 如果发起选举的牧师p 会在第二步和第四步期望22 分钟内收到其他牧师的回复 ， 如果没有则可能是一些牧师或者服务员离开了议会大厅 ， 或者还有一些牧师发起了编号更大的选举 。遇到这两种情况都牧师p 应该终止本次选举 ， 而重新开始发起一个新的选举 ， 为了不至于新发起的选举编号还是太小而仍不能执行 ， 需要从其他牧师哪里获取最新的选举编号 ， 从而选取一个更大的编号发起选举 。
进而假设牧师p 是唯一能够发起选举的牧师且议会大厅内有大部分集合的牧师 ， 那么可以保证在99分钟内通过一条法律：22 分钟内发现了有更大编号的法律 ， 22 分钟内获取最大编号并选择个更大的编号 ， 55 分钟内完成1-6 步完成一次成功的选举（疑问：既然只有牧师p 能够发起选举 ， 那么编号都是由其控制的 ， 前两步发现并选择更大的编号似乎就没有必要了 。答：并不是所有的选举都是president发起的 ， 其他牧师发起选举 ， president向其他希望发起选举的牧师配发选举编号） 。从上面的过程我们发现完整议会协议需要一个选举president的过程 ， president的选举算法不是文章重点 ， 所以文章中仅用T 分钟代替了选举president的时间 ， 这样T+99 分钟内可以通过一部法律 。
文中选择president的方法是谁的姓在字母表中最后 ， 并将自己的姓发送给议会大厅内所有牧师 ， 如果在T-11 分钟内某个牧师没有收到比自己姓在字母表中更靠后的姓 ， 则认为自己是president（我觉得广播体重也应该不错 ， 不是说体重更重的呆在议会大厅会更久么？^_^） 。还有一个细节：在选举president的时候每个牧师p 需要将自己的lastTried[p] 发送给其他牧师 ， 以使得president能够在第一次选举时选择一个足够大的编号 。
至此 ， 通过选举president和设置超时 ， 完整议会协议就可以保证过程了 。
多法律议会协议
上节的完整议会协议（complete Synod protocol）中 ， president被选举出来后 ， 每个希望发起选举的牧师通知他 ， president给牧师配发选举编号 ， 每次仅通过一部法律 。多法律议会协议（The Multi-Decree Parliment）选择一个president通过一系列法律 ， 且只需要执行前两步一次即可 。
具体方法是president第一步发送NextBallot(b,n) 代替NextBallot(b)  ， 表示希望通过n-b 之间的所有的法律 ， 在president 的账目上 ， 编号n 之前的法律都是连续记录了的 ， b>n。其他牧师q 收到消息后将每部已经出现在其账目中编号大于$n$的法律都返回给president ， 不在账目上的返回正常的LastVote 信息 。
下面谈到多法律国会协议有关性质 ， 首先是法律的顺序 ， 不同法律编号的选举同时进行 ， 发起选举的每个牧师都认为自己是president（不知道president 是怎么选举出来的 ， 也不知道法律通过的顺序） 。在完整议会协议第三步中法律被提议 ， 第一次写入到账目上时称法律被通过 。当一个president需要提出新的法案时 ， 他必须从大部分集合牧师中学习到那么法律他们都投了赞成票 ， 每部法律都被大部分集合牧师中至少一个牧师投了票 ， 所以president发起新的选举前总能学到所有之前通过了的法律 。president不会在空缺的法律编号内填补重要的法律 。 ， 也不会乱序提议法律 ， 所以协议满足“法律有序性”：如果法律A 和法律B 都是重要的法律 ， 法律A 在法律B 提议之前通过 ， 那么法律A 有比法律B 更低的法律编号 。第二点属性是president在选举出后且没有人再进出议会大厅 ， 法律是按照下面步骤不断通过的（对应完整议会协议的3-5步）：


推荐阅读


上一篇：铁观音拉酸的特点是什么

下一篇：安溪铁观音春茶的品质特征