知识卡片

普通读书笔记卡 · 1725.f

安全不等于必然推进

理解等级:中级

Paxos的安全性要求只能选定一个合法值;它不等于任意消息调度下都很快完成。多个proposer可以不断用更高编号的prepare打断对方的accept,产生安全却不前进的活锁。选出distinguished proposer让它主要发起提议,减少这种相互抢占。唯一提议者是帮助活性和效率的安排,不是Basic Paxos安全性必须依赖的前提。

这张卡片看不懂?

已有反馈 · 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。