在Lamport同步算法的讨论中，“部分排序”和“总排序”是什么意思？

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

这个定义说，总的顺序，任何两件事都是可比的。按部分顺序排列的东西既不需要比其他东西“更小”，也不需要反过来，总的顺序是每个东西要么比其他东西“更小”，要么相反。