Distributed systems have no shared clock. Wall time disagrees by milliseconds at best, hours at worst. So how do nodes agree on what happened first? Lamport's elegant 1978 insight: stop trying to measure time. Measure causality instead.
Two database replicas in different datacenters each accept a write at "the same moment." Both record their write with a timestamp from their local clock. Now you replay the writes elsewhere and have to decide which one to apply first. You look at the timestamps. Replica A says 14:32:01.847. Replica B says 14:32:01.831. So B came first, right? Maybe. Or maybe A's clock is fast by 20ms. Or B's NTP daemon hasn't synchronized in an hour. Or there's a clock-skew shock from the last leap second. The numbers are real. The ordering they imply may not be.
The escape hatch is to stop asking what time it is. The thing we really care about isn't "what's the timestamp," it's "if event B's outcome depends on event A, did A actually happen before B?" That question has an answer even when clocks are unreliable — because causality leaves its own trail. If A sent a message and B received it, A must have happened before B. No clock needed. Lamport's 1978 paper turned this intuition into formal mathematics, and the entire field of distributed systems has been building on it ever since.
The rest of this module unpacks how. We'll define the happens-before relation (the foundational primitive), build Lamport timestamps (a clever scheme that captures part of it), see where Lamport's elegance falls short, and upgrade to vector clocks — which capture causality completely. The lab in §04 lets you watch all of this play out across three processes exchanging messages.
Lamport's first move was definitional: he gave us a precise mathematical relation, written A → B ("A happens-before B"), that captures the only ordering that's both verifiable and meaningful in a distributed system. Three rules generate the whole relation. From these rules, everything else follows.
Within a single process, events happen in the order the program executes them. This is the only kind of ordering you can take for granted — a single CPU, a single thread, a single sequence of instructions. The bedrock everything else builds on.
A message can't be received before it was sent. Send always happens-before receive. This is the bridge between processes — the only causal link you can establish without a shared clock. If A sent something B holds, A was first.
Causality chains. If your message reached me, and I sent it on, the original sender happens-before the eventual recipient. Transitivity is what makes "happens-before" a partial order — it lets you reason about causes far down the chain from effects.
Two events are concurrent (written A || B) if neither happens-before the other. This is the new, distinctly distributed-systems concept: some events have no inherent order. They may have been "really" simultaneous, or one may have "actually" come first by physical wall time — but if no causal chain connects them, the system has no way to know, and (more importantly) their order doesn't matter to any computation. Concurrent events can be applied in any order; the result is the same.
This is the single most important conceptual upgrade in distributed systems. In a single-machine world, all events have a total order (the program executes them one at a time). In a distributed world, events have only a partial order. Some events are clearly ordered (causal chains link them); others are genuinely incomparable. Trying to force a total order on partially-ordered events is the root cause of half the bugs in distributed databases. Causal consistency from M.22 is precisely the model that respects this partial order without trying to fake a total one.
Knowing happens-before is one thing; computing it efficiently is another. You can't ship the entire event history with every message. So Lamport (and later, Mattern & Fidge) invented compact representations — logical clocks — that summarize causality in a few numbers. Two designs matter: Lamport timestamps (one integer per event) and vector clocks (one integer per process per event). They make different trade-offs.
One integer per event. Cheap to store, cheap to ship in every message. Captures the forward direction of happens-before perfectly: if A → B, then L(A) < L(B). Guaranteed.
L(A) < L(B) does NOT imply A → B. They might be concurrent. Lamport timestamps can't distinguish "causally before" from "happens to have a smaller number."
N integers per event, where N = number of processes. Tracks how much each process has "seen" from every other. Larger, but encodes the full happens-before relation.
A → B if and only if V(A) < V(B) component-wise (every entry ≤, at least one strictly <). Otherwise: concurrent. Vector clocks detect concurrency; Lamport hides it.
The trade-off is exactly what it looks like: Lamport gives you cheap, one-integer timestamps that get the easy cases right but can't tell you when events are concurrent. Vector clocks pay N integers per event for the ability to detect concurrency precisely — which turns out to be exactly what distributed databases need for conflict resolution (M.22 territory). If two replicas accepted writes whose vector clocks are incomparable, the writes are concurrent, and the system needs to merge them. Lamport timestamps would give you two different numbers and lie about whether one preceded the other.
Both algorithms share a common shape: local events bump your own counter; messages carry causality forward; receivers merge by taking max. That last move — max — is the heart of it. When you receive a message, you absorb everything the sender knew about the past. The max ensures you never go backward, and the +1 ensures your next event is strictly after every event in your causal past.
Time to make this physical. The lab below runs three processes exchanging messages across three scenarios. Toggle between Lamport and vector mode; step through events one at a time; watch the counters update via exactly these rules. By the end, you'll be able to compute either by hand.
Below: three processes (P₁, P₂, P₃) exchanging messages. Pick a scenario. Toggle between Lamport and vector clocks. Step through one event at a time and watch the timestamps update according to the rules in §03. The right panel shows the exact computation for each step — and the key insight that step is meant to teach.
Lamport's 1978 paper introduced logical clocks. Almost fifty years later, every distributed database in production uses some descendant. The specific designs vary — pure Lamport is rare; vector clocks have known scaling issues; modern systems mostly use hybrid approaches — but the foundational ideas are the same: track causality with a logical structure, optionally augmented with physical time bounds. Below: four concrete examples.
(physical_time, logical_counter). Combines wall-clock with logical advancement. Physical part stays close to NTP; logical part handles ties and out-of-order receives. Best of both: readable timestamps that respect causality. The modern default for new distributed databases.[earliest, latest] rather than a single timestamp. Spanner waits out the uncertainty before committing, ensuring external consistency — wall-clock-ordered transactions across continents. Cost: custom hardware in every datacenter. Out of reach for non-Google systems.Two things to internalize. First, the choice of clock mirrors the consistency choice from M.21 and M.22. AP systems with eventual consistency tend to use vector clocks (to detect conflicts for merging). CP systems with linearizable consistency lean on single-counter Lamport-like indices (because there's a single leader, so total order is achievable). HLC sits in between, useful for systems that want causal consistency with readable timestamps. The clock you reach for is determined by the consistency model you committed to.
Second, most application engineers will never touch clocks directly — they're implementation details of the databases and message brokers below them. But understanding them is what lets you read the docs, debug the weird cases, and choose intelligently when buying a database. The vendor's marketing copy will not say "we use HLC." The architecture diagram in their docs will. Now you can read it.
The terms that appear in every distributed systems paper from 1978 onward. These are foundational.
A || B) if neither happens-before the other. Doesn't mean "at the same wall-clock instant" — means no causal chain links them.max(local, received) + 1 on receive. Guarantees: if A → B then L(A) < L(B). Does not detect concurrency.(wall_time, logical). Used by CockroachDB, MongoDB, YugabyteDB. The modern default for new distributed databases.Test the clocks intuition. Click an answer; explanation drops in instantly.
Perfect. Happens-before, Lamport, vector — yours. Next: how do nodes actually agree on a single ordering, even with all this clock uncertainty? Consensus & Raft.
The mathematical foundation under every distributed database. These return in every module ahead.
Distributed events have only a partial order. The order that matters isn't "what time it was" but "what caused what." Lamport's reframing 50 years ago is still the foundation.
Lamport gives one number per event — captures forward causality. Vector gives N numbers — captures concurrency too. The cost vs precision trade-off is the choice.
HLC, TrueTime, single-leader Lamport. Pure schemes are rare in production. But every one is built on the foundations in this module. Recognize them in the docs.