algorithm - Lamport同步算法讨论中的“部分排序”和“全排序”是什么意思？

Question

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

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

那么什么是全排序呢？

为什么会这样命名？

标签： algorithmsynchronizationdistributed-computingsystem-clock

Answer 1

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

集合元素的偏序由所有元素必须持有的三个属性a定义，b并且c：

• 反身性：a ≤ a
• 反对称：如果a ≤ b和b ≤ a，那么a = b
• 传递性：如果a ≤ b和b ≤ c，那么a ≤ c

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

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

• 连接性： a ≤ b或b ≤ a

这个定义说，在总的顺序上，任何两件事都是可比的。而在部分顺序中，事物既不需要比另一个“小”，也不需要相反，在总顺序中，每个事物要么比另一个“小”，要么相反。