Что означает «частичное упорядочение» и «полное упорядочение» в обсуждении алгоритма синхронизации Лампорта?

Question

Я понимаю, что частичное упорядочение и полное упорядочение - это два набора правил.

Частичное упорядочение имеет три правила:
(1) если a a b - это два события в одном и том же процессе и aпредшествует b, затем a-> b.
(2) ...
(3) ...

Что такое общее упорядочение тогда?

Почему именованныетак?

Answer 1

Эти имена основаны на том факте, что в частичном порядке не все элементы сопоставимы, а в общем порядке все элементы сопоставимы:

Частичный порядок элементов набора определяется тремя свойствами , которые должны выполняться для всех элементов a, b и c:

• Отражательная способность : a ≤ a
• Антисимметрия : если a ≤ b и b ≤ a, то a = b
• Транзитивность : если a ≤ b и b ≤ c, то a ≤ c

Это определение отражает суть общей интуиции того, что значит упорядочивать вещи: каждая вещь имеет тот же «размер», что и сама, она может быть «меньше», чем другая, но тогда другая не «меньше», чем сам. Наконец, если вещь «меньше», чем другая, которая «меньше», чем треть, то она также «меньше», чем третья.

Общий заказ - это частичный заказ с дополнительным свойством:

• Связность : a ≤ b или b ≤ a

Это определение говорит о том, что в общем порядке любые две вещи сравнимы. Если в частичном порядке вещь не должна быть ни «меньше», ни другой, ни наоборот, в общем порядке каждая вещь «меньше», чем другая, или наоборот.