What does "synchronization actions are totally ordered" mean?

Analyzing the statement "synchronization actions are totally ordered":

• "synchronization actions" is a set S of program operations (actions)
• we have a relation R over set S : it is the happens-before relation. That is, given program statements a and b, aRb if and only if a happens-before b.

Then what the statement says, is "relation R is total over S".

"relation R is total over S", means that for every two operations a,b from set S (with a!=b), either aRb, or bRa. That is, either a happens-before b, or b happens-before a.

If we define the set S as the set of all lock acquisitions and lock releases performed on the same lock object X; then the set S is totally ordered by the happens-before relation: let be a the acquisition of lock X performed by thread T1, and b the lock acquisition performed by thread T2. Then either a happens-before b (in case T1 acquires the lock first. T1 will need to release the lock first, then T2 will be able to acquire it); or b happens-before a (in case T2 acquires the lock first).

Note: not all relations are total.

In example, the relation <= is total over the real numbers. That is, for every pair a,b of real numbers, it is true that either a<=b or b<=a. The total order here means that given any two items, we can always decide which comes first wrt. the given relation.

But the relation P: "is an ancestor of", is not a total relation over the set of all humans. Of course, for some pairs of humans a,b it is true that either aPb (a is an ancestor of b), or bPa (b is an ancestor of a). But for most of them, neither aPb nor bPa is true; that is, we can't use the relation to decide which item comes "first" (in genealogical terms).

Back to program statements, the happens-before relation R is obviously partial, over the set of all program statements (like in the "ancestor-of" example): given un-synchronized actions a,b (any operations performed by different threads, in absence of proper synchronization), neither aRb nor bRa holds.