Lamport同步算法讨论中的“偏序”和“全序”是什么意思？

Question

我的理解是，部分排序和全排序是两组规则。

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

那么什么是全序呢？

为何如此命名？

Answer 1

这些名称源于这样一个事实：在部分顺序中，并非所有元素都具有可比性，而在全序中，所有元素都具有可比性：

\n\n

集合元素的偏序由三个属性定义，这些属性必须适用于所有元素a、b和c：

\n\n

\n
• 自反性：a \xe2\x89\xa4 a
\n
• 反对称性：如果a \xe2\x89\xa4 b和b \xe2\x89\xa4 a，那么a = b
\n
• 传递性：如果a \xe2\x89\xa4 b和b \xe2\x89\xa4 c，那么a \xe2\x89\xa4 c
\n

\n\n

这个定义抓住了对事物进行排序的普遍直觉的本质：每个事物都与其自身具有相同的“大小”，它可以比另一个事物“更小”，但另一个事物并不比它自己“更小”。最后，如果一个事物比另一个事物“小”，而另一个事物又比第三个事物“小”，那么它也比第三个事物“小”。

\n\n

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

\n\n

\n
• 连接性： a \xe2\x89\xa4 b或b \xe2\x89\xa4 a
\n

\n\n

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

\n