algorithm - Lamport同步算法讨论中的 "partial ordering"和 "total ordering"是什么意思？

Question

我的理解是，偏序和全序是两套规则。

部分排序有三个规则:
(1) 如果a 和b 是同一进程中的两个事件，并且a 在b 之前发生，则a->b。
(2) ...
(3) ...

那什么是全序呢？

为什么这样命名？

Answer 1

这些名称源于一个事实，即在偏序中并非所有元素都是可比较的，而在全序中所有元素都是可比较的:

集合元素的偏序由 three properties 定义必须对所有元素 a、b 和 c 成立:

• Reflexivity : a ≤ a
• Antisymmetry : 如果 a ≤ b 且 b ≤ a，则 a = b
• Transitivity : 如果 a ≤ b 且 b ≤ c，则 a ≤ c

这个定义捕获了对事物排序意味着什么的共同直觉的本质:每个事物都与它自己“大小”相同，它可以比另一个“小”，但另一个不“小于”本身。最后，如果一个事物比另一个“小”，即比三分之一“小”，那么它也比第三个“小”。

全序是具有附加属性的偏序:

• Connexity : a ≤ b 或 b ≤ a

这个定义说在全序中任何两个事物都是可比较的。在偏序中，一个事物既不需要比另一个“小”，也不需要相反，在全序中，每个事物要么比另一个“小”，要么反过来。