在讨论 Lamport 同步算法时,"partial ordering"和"total ordering"是什么意思?



我的理解是,部分排序和总排序是两套规则。

偏序有三个规则:
(1)如果aa b是同一过程中的两个事件,a在b之前,那么a->b。

(3) ...

那么什么是总订购量呢?

为什么这么称呼?

这些名称源于这样一个事实,即在部分顺序中,并非所有元素都是可比的,而在总顺序中,所有元素都是可比的:

集合元素的偏序由三个属性定义,这些属性必须对所有元素abc都成立:

  • 反身性:a ≤ a
  • 反对称:如果a ≤ bb ≤ a,则a = b
  • 传递性:如果a ≤ bb ≤ c,则a ≤ c

这个定义抓住了对事物进行排序意味着什么的共同直觉的本质:每个事物都与自身具有相同的"大小",它可以比另一个"小",但另一个并不比自己"小"。最后,如果一个东西比另一个东西"小",而另一个东西比第三个"小",那么它也比第三个"小"。

总订单是具有附加属性的部分订单:

  • 连接性:a ≤ bb ≤ a

这个定义说,在一个总的顺序中,任何两个事物都是可比的。在偏序中,一个事物既不需要比另一个事物"小",也不需要相反,在总顺序中,每个事物要么比另一个事物"小",要么相反。

最新更新