Why is the 'happened before' relation on a replicated log's events a partial order rather than a total order?
answer
- some pairs simply do not compare
- three axioms, and totality is a fourth
- concurrency is not a tie
- neither event observed the other
- three verdicts, not two
basics
~20 sHappened-before relates only events that are causally linked. If neither event saw the other, they are incomparable, not equal. A partial order permits such incomparable pairs; a total order demands that every pair be comparable.
solid answer
~40 sA partial order is reflexive, antisymmetric and transitive (or in its strict form irreflexive and transitive). Happened-before has exactly those properties: an event precedes later events on the same replica, a send precedes its delivery, and the relation is closed transitively. A total order requires one more axiom, **comparability**: for any two elements, one must precede the other. The log cannot supply that. Two events written on two replicas that had not yet exchanged anything are related by none of the rules, so the relation has no opinion about them — they are `concurrent`. The key move is refusing to read incomparable as equal: equal means interchangeable, incomparable means unordered, and only the second one signals a conflict that something must resolve.
code
pseudocode · 12 lines# a and b hold one counter per replica: what each event had seen
function relate(a, b):
aWithinB = true
bWithinA = true
for each replica r:
if a[r] > b[r]: aWithinB = false
if b[r] > a[r]: bWithinA = false
if aWithinB and bWithinA: return SAME
if aWithinB: return A_BEFORE_B
if bWithinA: return B_BEFORE_A
return CONCURRENTgo deeper
Remember the shape: an order can relate some pairs and stay silent about others. Two events with no relation between them are not the same event.
Be able to state the axioms — antisymmetry and transitivity — and name comparability as the extra axiom a total order adds. Then show that a replicated log breaks exactly that one.
Show where the distinction costs money: a comparison collapsed to two verdicts silently discards one of two concurrent updates, and no alert fires because nothing ever noticed a conflict.
Frame it as a contract decision: exposing concurrency pushes merge semantics onto every consumer, hiding it pushes silent data loss onto the users. Say which one your domain can absorb.
## The axioms every order keeps An **order** is a relation on a set, and a **partial order** is one that satisfies three axioms: - **Reflexivity** — every element is related to itself, `x <= x`. Orders written strictly (`x < y`) replace this with **irreflexivity**: no element precedes itself. The two forms carry the same information; adding or dropping "or equal" converts between them. - **Antisymmetry** — if `x <= y` and `y <= x`, then `x` and `y` are the same element. Two distinct elements can never precede each other. - **Transitivity** — if `x <= y` and `y <= z`, then `x <= z`. A set together with such a relation is a **poset**. Nothing in those three axioms says that any particular pair of elements must be related at all, and that silence is the whole point. ## The axiom a total order adds A **total order** is a partial order plus **comparability**: for every pair `x, y`, either `x <= y` or `y <= x`. Every element sits somewhere on one line. | | Partial order | Total order | |---|---|---| | Antisymmetric | required | required | | Transitive | required | required | | Every pair comparable | not required | required | | Incomparable pairs | allowed | impossible | | Natural picture | a branching **Hasse diagram** | a single chain | | "Which came first?" | may have no answer | always has one | ## Why the log's relation is only partial Happened-before is generated by two rules and then closed transitively: 1. An event precedes every later event produced by the same replica. 2. Sending or writing something precedes the event that observes it elsewhere. 3. Anything reachable by chaining 1 and 2 is related; nothing else is. Now take two replicas that have been apart. Each records an event while holding no knowledge of the other's. Rule 1 does not apply — different replicas. Rule 2 does not apply — neither event observed the other. No chain connects them. The relation therefore relates neither way round, and that is exactly the definition of **incomparable**. In this setting incomparable has a name of its own: the events are **concurrent**. This is not a defect in the metadata. It is the honest content of the relation: causality genuinely did not order those two events, and no amount of extra bookkeeping inside the log can manufacture an order that causality did not create. ## Concurrent is not equal, and not unknown Two failure modes follow from confusing incomparability with something else. - **Reading it as equal.** Equality says the two events are interchangeable, so a system may keep one and drop the other. Concurrency says the opposite: both happened, neither supersedes the other, and something has to decide what the combination means. - **Reading it as missing information.** A richer clock does not fill the gap. Attaching a wall-clock reading, or routing every write through a single sequencer, imposes a total order from outside; it does not discover a causal relation that was never there. The imposed order is a **choice**, and the choice is invisible afterwards — the concurrency that was present in the data is gone from the record. The practical tests an engineer runs are all comparability tests. Given two pieces of causal metadata, there are three possible verdicts, not two: the first precedes the second, the second precedes the first, or neither does. A comparison routine that returns a two-valued answer has already destroyed the distinction before anyone can act on it. ## What the structure gives you back Once the relation is recognised as a partial order, several things become available at once: - **Conflict detection is comparability testing.** A conflict is precisely a pair with no relation between them. - **The set of mutually unrelated events is an antichain**, and its size measures how much genuine concurrency the history contains. - **Any finite partial order can be extended to a total order**, usually in many different ways. Serialising the log is therefore always possible, and always a decision about which extension to take. - **Transitivity lets you store less.** Only the direct relations need recording; everything implied by chaining them is already true, which is why a Hasse diagram draws only the covering edges and omits the ones transitivity supplies.
- Happened-before is irreflexive — no event precedes itself. Does that disqualify it as a partial order?No. It is a **strict** partial order: irreflexive and transitive, which forces asymmetry. Adding "or is the same event" produces the reflexive, antisymmetric, transitive form. The two presentations describe the same structure, and textbooks use whichever is more convenient.
- Two events carry identical wall-clock readings. Does that make them concurrent?No. Concurrency is a statement about the causal relation, not about clock values. Equal readings can be attached to events where one genuinely did observe the other, and different readings can be attached to events that are concurrent. Clock values impose an order from outside; they do not report one.
- If a comparison returns only 'before' or 'after', what has the system already lost?The concurrent case. Forced into two verdicts, an incomparable pair is reported as ordered, so a later stage treats one event as superseding the other and may discard it. Conflict detection is impossible downstream once the third verdict has been collapsed away.
Two letters posted in different cities on the same day: neither answers the other, so the post itself cannot say which came first. Stamping them on arrival gives an order, but it is the sorting office's order, not the writers'.
saying these in an interview costs you the question
- Treats concurrent events as equal, so either one may be dropped
- Says a better clock would reveal the missing causal order
- Claims a partial order means no two elements are ever comparable
- Thinks transitivity is optional for a happened-before relation
- Assumes a sequencer's position reflects real causal precedence