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?

Soapbark

The Implications section in Wikipedia might help. In general, I believe a total ordering means every pair of elements is comparable vis-a-vis the ordering relation. – Afflatus

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.

Beltran

If I understand this answer correctly, "partial ordered things might have 2 or more elements which are equal". I suspect I didn't understand correctly however. Have I totally misinterpreted this answer or is this at least somewhat along the right lines? – Blubbery

@FreelanceConsultant, partial orders might have many elements (or none at all) that are equal. But this is not the point. The key difference between a partial and a total order is that in the latter all elements are comparable with each other, where in the former there are some elements that do not compare to others. If you visualize an order as a tree, where items are smaller than their parents, then items from different branches are not comparable. In the case of a total order that tree is just one single linear branch. – Beltran

@FreelanceConsultant, take intervals as an example: you can order them by saying one interval is smaller than another if it fits inside the other. This is a partial order since intervals that do intersect without one being inside the other cannot be compared. – Beltran

@Beltran If we are given a relation on a set, how do we denote that a pair $x$, $y$ is not comparable? – Roots