Module 13 · Distributed fundamentals · Lesson 8 of 18
Logical clocks
Ordering events without trusting physical time. The happens-before relation, why causality is the only order that matters in a distributed system, counters that respect it, and the family of logical clocks (Lamport, vector.
Why it matters
The previous lesson established that physical clocks cannot be trusted to order events on different machines. Yet systems constantly need to know which of two updates came first, whether a read saw a write, whether two edits conflict. Logical clocks answer those questions from the structure of communication itself: what caused what. They are the foundation of replication conflict detection, causal consistency and collaborative editing, and the conceptual key to the two lessons that follow.
The idea
In a distributed system, the only ordering we can actually observe is causality. Event A happens before event B (written A → B) if:
- 1
Same process, earlier
A and B occur in the same process and A comes first in its program order. - 2
Send before receive
A is the sending of a message and B is the receipt of that same message. - 3
Transitivity
A → C and C → B imply A → B.
If neither A → B nor B → A, the events are concurrent: neither could have influenced the other, and no observer can say which "really" came first, because there is no fact of the matter that the system can detect. Happens-before is a partial order, and that partiality is not a weakness; it is the truth about what the system can know.
What a logical clock must do
A logical clock assigns each event a timestamp such that if A → B then timestamp(A) is less than timestamp(B). It respects causality without any reference to physical time. The simplest is a counter per process that increments on each local event and, on receiving a message, jumps to one more than the maximum of its own value and the sender's attached value. That is a Lamport clock, next lesson. It satisfies the one-way implication: causally related events have ordered timestamps. It does not satisfy the reverse: ordered timestamps do not imply causality, because concurrent events also get timestamps, and one of them is smaller.
Detecting concurrency
Many problems need the reverse direction too: given two versions of a record, were they causally related (one overwrote the other, keep the later) or concurrent (a true conflict, keep both or merge)? That requires a timestamp that captures what each process has seen from every other process, a vector clock, covered two lessons on. Vector clocks characterise causality exactly: A → B if and only if vector(A) is less than vector(B), and incomparable vectors mean concurrent.
The family at a glance
| Clock | Timestamp | Guarantees | Used for |
|---|---|---|---|
| Lamport | One integer | A → B implies L(A) < L(B) | Total ordering by (counter, node id): mutual exclusion, log ordering, versioned writes |
| Vector | One integer per process | A → B if and only if V(A) < V(B); detects concurrency | Conflict detection in replicated stores (Dynamo, Riak), causal consistency |
| Version vectors | One integer per replica | Like vector clocks but per data item, tracking replica updates | Per-key conflict tracking in key-value stores |
| Hybrid logical (HLC) | Physical time plus a logical counter | Close to wall time, still respects causality | CockroachDB, YugabyteDB: human-readable timestamps that are also safe to order by |
| Dotted version vectors | Version vector plus a dot | Precise tracking with concurrent client writes | Riak's conflict handling |
Why this matters in practice
Last-write-wins by wall clock loses data whenever clocks disagree or writes are concurrent. Causal ordering with logical clocks lets a system keep the right version when one write supersedes another and surface a conflict when two are genuinely concurrent, which is what users expect: their edit is not silently discarded because another machine's clock was ahead. Causal consistency, message ordering in chat systems, and CRDT metadata all rest on this.