What does it mean by "partial ordering" and "total ordering" in the discussion of Lamport's synchronization Algorithm?

Question

What I understand is, partial ordering and total ordering are two sets of rules.

Partial ordering has Three rules:
(1) if a an b are two events in the same process and a comes before b, then a->b.
(2) ...
(3) ...

What is total ordering then?

Why are the named so?

Answer 1

Those names stem form the fact that in a partial order not all elements are comparable while in a total order all elements are comparable:

A partial order on the elements of a set is defined by three properties that have to hold for all elements a, b and c:

• Reflexivity: a ≤ a
• Antisymmetry: if a ≤ b and b ≤ a, then a = b
• Transitivity: if a ≤ b and b ≤ c, then a ≤ c

This definition capture the essence of the common intuition of what it means to order things: each thing is the same "size" as itself, it can be "smaller" than an other but then the other is not "smaller" than itself. Finally if a thing is "smaller" than an other, which is "smaller" than a third then it is also "smaller" than the third.

A total order is a partial order with the additional property:

• Connexity: a ≤ b or b ≤ a

This definition says that in a total order any two things are comparable. Wheras in a partial order a thing needs neither to be "smaller" than an other nor the other way around, in a total order each thing is either "smaller" than an other or the other way around.