江苏龙网

  1. 主页 > 生活百科 > >

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

Paxos算法


5. 如果牧师p 收到Q 中每个牧师q 发来的赞成票Vote(b,q) ， 则将法律d 写入他的账目中 ， 并向所有q发送Success(d) 消息 。
6. 收到Success(d) 消息后 ， 牧师q 将法律d 写入到自己的账目中 。

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

文章插图
 
说明：第一步表示发起法律的牧师p 希望下一个选举的编号是b。牧师q 用LastVote(b,v) 回应了牧师p 的请求 ， 也就是向牧师p 通过法律时保证了v=MaxVote(b,q,B) 的被改变 ， 具体来说就是不在b 和b_bal 之间的选举投赞成票 。
第三步要求法律d 需要满足B3 ， 这里我开始有点迷糊 ， 实际系统中的值是客户端决定的 ， 而不应该是B3 决定的 。这里我们还是用上面的key-value 数据库的例子来理清下思路：当某个节点/牧师第一次发起更新前相当于B为空集 ， 发起更新/选举的操作不断进行 ， 直至所有法定人数（quorum）都对法律投了赞成票（即majority set 的节点都更新了该key-value 的值则认为更新成功） ， B3对应的就是之前的更新没有成功 ， 那么新的选举值需要保持的情况 。第四步允许牧师可以不发送Vote(b,q) 或者发送几次 ， 对应的是发送的信息可能因为通信而失败而未发送或者被多次发送 。一旦牧师投了赞成票则确认可以修改该值 。
考虑到最后第六步法律d 才被牧师q 写入到账目 ， 有可能出现的情况就是在第五步的时候牧师p 将法律写入到了自己账目中 ， 接着发送Success(d) 给其他牧师 ， 其中因为通信或者牧师离开议会大厅而没有被写入到自己的账目中 ， 导致不一致 。所以真正写入到账目时机应该是在第四步牧师q 在发送给牧师p 赞成票的同时就法律写入到了各自账目中 。而不用考虑如何保证牧师q 第四步写入的法律会导致不一致 ， 因为法律如果没有通过则还有更多的选举来保证一致性 。后面也谈到了当法律第一次别写入到账目中算通过法律 。
基础协议
初始协议（Preliminary Protocol）要求每个牧师都保存 (i) 他发起的每个选举； (ii) 他投的每个赞成票； (iii) 他发送的每个$LastVote$ 。为了简化牧师需要保存的数据 ， 我们对上面的协议做一个限制 ， 得到基础（Basic Protocol）协议 。首先介绍三个新的参数：
lastTried[p] 牧师p 发起的最后一个选举
prevVote[p] 牧师p 最近一次的投票
nextBal[p] 收到的选举编号的b 的最大值 ， 即牧师p参加的最大选举编号
在初始协议中 ， 每个牧师可以同时发起任意个选举 ， 在基础协议中要求每个牧师只能发起一个选举lastTried[p] ， 一旦发起一个选举 ， 那么之前发起选举的信息就都不重要了 。在初始协议中要求每个牧师不能在b_bal 和b 之间投赞成票 ， 在基础协议中则更严格地要求不能给小于b 的选举投赞成票 。那么基础协议可以概述为下面几步：
1. 牧师p 选择一个大于lastTried[p] 的选举编号b  ， 发送NextBallot(b)给其他牧师
2. 牧师q 收到NextBallot(b) 且b>nextBal[q]后设置nextBal[q]=b  ， 接着发送LastVote(b,v) 给牧师p ， 其中v==prevBa[q]。（如果b 小于或等于nextBal[q] ， 则不回复）
3. 从满足某个大部分集合Q 中每个牧师收到了LastVote(b,v) 信息 ， 牧师p 发起一个编号为b  ， 法定人数为Q  ， 法律为d（满足B3 ）的选举 ， 并将BeginBallot(b,d) 发送给Q 中每个牧师 。（如果没有满足任意大部分集合Q 的牧师返回 ， 则返回第一步）
4. 牧师q 收到BeginBallot(b,d)  ， 决定投赞成票 ， 设置prevVote[p] 为这次投票 ， 并发送Vote(b,q) 给牧师p 。（如果在收到BeginBallot(b,d) 后发现b 不等于nextBal[q] 则忽略这条信息 ， 说明这期间牧师q 还收到了其他的编号更大的选举）
5. 牧师p 从大部分集合Q 中每个牧师q 收到了Voted(b,d)  ， 且b==lastTried[p]  ， 则认为这次选举成功 ， 将法律d 记录在账目中 ， 并向Q 中每个牧师q 发功成功消息Success(d)。
6. 每个牧师q 收到Success(d) 消息后将法律写入账目 。
基础协议是初始协议的限制版 ， 因为两者都对牧师没有行为要求 ， 所以也不保证过程（QS） 。下面介绍一个保证过程的协议— 完整议会协议（complete Synode protocol） 。
完整议会协议


推荐阅读


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

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