知识卡片

普通读书笔记卡 · 1730.g

队列顺序必须合法

理解等级:中级

FIFO队列的线性化不仅要求调用返回成对、进程内部顺序保持,还要遵守先入先出的对象语义。原书反例中,候选历史把x入队排在y前面,却先出队y,所以即使满足时间偏序也不合法。判断一致性必须先写清对象规范,否则“有一个全序”本身没有足够含义。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 线性一致性与强一致性 · 查看原书依据

      这个历史S是顺序的,与历史H是等价的,保持了偏序关系,但是它不合法。一个队列结构,先入队x,那么一定要先出队x,不能像历史S那样,先出队y。本书省略了对合法的定义,采用这个例子来说明什么是合法。 因为找不到符合条件的历史S,所以历史H不是线性一致性的,图15.2所示的执行也就不是线性一致性的。

    参考来源

    - 位置:《分布式系统与一致性》第15章《线性一致性与强一致性》(来源项目:book-sources;源文件:extracted/分布式系统与一致性/_epub-src/OEBPS/Text/chapter19.xhtml) - 结论依据:原文给出上述定义、机制或具体并发场景;卡片区分实际物理执行与抽象结果,不把原书示意当本次运行结果。 - 原始内容:这个历史S是顺序的,与历史H是等价的,保持了偏序关系,但是它不合法。一个队列结构,先入队x,那么一定要先出队x,不能像历史S那样,先出队y。本书省略了对合法的定义,采用这个例子来说明什么是合法。 因为找不到符合条件的历史S,所以历史H不是线性一致性的,图15.2所示的执行也就不是线性一致性的。