知识卡片
安全不等于必然推进
Paxos的安全性要求只能选定一个合法值;它不等于任意消息调度下都很快完成。多个proposer可以不断用更高编号的prepare打断对方的accept,产生安全却不前进的活锁。选出distinguished proposer让它主要发起提议,减少这种相互抢占。唯一提议者是帮助活性和效率的安排,不是Basic Paxos安全性必须依赖的前提。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第10章 共识算法Paxos(含第3部分导读) · 查看原书依据
在图10.7所示的例子中,proposer1发送给acceptor3的accept消息被proposer2发出的prepare消息取消,proposer2发出的accept消息又被proposer1发出的第二轮prepare消息取消,如此往复进行下去,存在永远都不会达成共识的可能,也就是出现了活锁。 图10.7 活锁导致最终不能达成共识 为了避免出现这种情况,可以选出一个proposer,作为distinguished proposer,只有这个distinguished proposer才能发起提议,从而避免了活锁情况的发生,如图10.8所示。 显而易见,只有一个proposer可以发起提议不是Paxos算法的必要条件,选出一个distinguished proposer只是为了提高效率。所以我们可以采用任何一种方式来选择distinguished proposer,只要能大概率地选出一个proposer即可。 图10.8 distinguished proposer 4.学习值过程 学习值的过程,可以被理解为consensus()方法实现中的第二条语句。 学习值过程的产出是被选中的值v。
参考来源
- 位置:《分布式系统与一致性》第10章(来源项目:book-sources;源文件:extracted/分布式系统与一致性/_epub-src/OEBPS/Text/chapter14.xhtml)
- 结论依据:本章对上述机制的流程与约束说明;图表部分按本书对应图表阅读。
- 原始内容:在图10.7所示的例子中,proposer1发送给acceptor3的accept消息被proposer2发出的prepare消息取消,proposer2发出的accept消息又被proposer1发出的第二轮prepare消息取消,如此往复进行下去,存在永远都不会达成共识的可能,也就是出现了活锁。 图10.7 活锁导致最终不能达成共识 为了避免出现这种情况,可以选出一个proposer,作为distinguished proposer,只有这个distinguished proposer才能发起提议,从而避免了活锁情况的发生,如图10.8所示。 显而易见,只有一个proposer可以发起提议不是Paxos算法的必要条件,选出一个distinguished proposer只是为了提高效率。所以我们可以采用任何一种方式来选择distinguished proposer,只要能大概率地选出一个proposer即可。 图10.8 distinguished proposer 4.学习值过程 学习值的过程,可以被理解为consensus()方法实现中的第二条语句。 学习值过程的产出是被选中的值v。