The problem: ordering events without a trustworthy clock#
TL;DRthe 30-second version
- Wall-clock timestamps can't order events across machines, because clocks drift — a write on a fast clock can look newer than a genuinely later write on a slow one.
- A Lamport clock is one counter per node. You bump it on every event, send it along with each message, and on receive you set it to the larger of the two, plus one. If an event could have caused another, its counter is smaller.
- But the reverse isn't true: a smaller Lamport number doesn't prove one event came before another. Two unrelated events get numbers too, so Lamport clocks give an order but hide which events are actually concurrent.
- A vector clock keeps one counter per node. You bump your own entry on an event, and on receive you take the entry-by-entry maximum, then bump your own. Now comparing two vectors tells you happened-before or concurrent — exactly.
- The cost is size: every timestamp carries one number per node, so it grows with the cluster. That is the price of exact concurrency detection, and it's why systems like Dynamo and Riak use vector clocks and then work to keep them small.
Picture a shopping cart replicated on two servers. Alice's phone adds milk on server 1. A moment later, on server 2, the same account adds eggs. The two servers can't reach each other right then — a brief network partition. When they reconnect, each has a version of the cart the other never saw. Which one is newer? You'd like to just compare timestamps and keep the later write. But that's exactly the move clock synchronization warned you against.
Here's the naive approach in full: stamp every event with the local wall-clock time, and to order two events, compare their stamps. The trouble is that the two servers keep time with separate quartz clocks that drift apart. Say server 2's clock runs 50 milliseconds behind server 1's. The eggs write genuinely happens 30 milliseconds after the milk write, but on server 2's slow clock it gets a smaller timestamp. Order by timestamp and you conclude eggs came first — the wrong answer, produced with total confidence. Last-write-wins conflict resolution makes this concrete and dangerous: it silently discards the write with the smaller timestamp, so a fast clock can clobber a real, later update.
The forced first step: count events, not seconds#
Throw out real time. Give each node a single counter that only ever goes up, and bump it by one before every event the node does. Now a bigger counter means a later event — on that one node. The counters are honest there because a single node does its events in order and never drifts against itself.
The hard part is tying the nodes together, and messages are the only thread between them. So make each message carry the sender's counter. When a node receives a message, it has learned about everything the sender had done up to that send. Its own counter must jump past the sender's, or the receive would look like it happened before the send that caused it. If it merely copied the sender's number it would tie with the send — so it takes the larger of its own counter and the message's, and then adds one. That single rule is what makes the counters agree with cause and effect across nodes.
- On a local event, a node adds one to its counter.
- On sending a message, the node adds one to its counter and attaches that value to the message.
- On receiving a message, the node sets its counter to the larger of its own value and the message's value, then adds one.
This is a Lamport clock, named for Leslie Lamport, who introduced it in 1978 in one of the most-cited papers in the field. It defines the happened-before relation: an event happened before another if they're on the same node in program order, or if one is a send and the other is its matching receive, or by chaining those together through a message path. The clock's guarantee is exactly this: if an event happened before another, its Lamport number is strictly smaller. That's enough to give every event in the whole system a single consistent order — pick any tie-break for equal numbers and you have a total order no message ever violates.
Where Lamport clocks fall short#
The guarantee runs one way only, and that turns out to matter enormously. Lamport promises that if an event happened before another, its number is smaller. It does not promise the reverse. A smaller number does not mean one event happened before the other — it might, or the two events might have nothing to do with each other and simply drew those numbers independently.
Make it concrete. Node A does a local event and gets counter 1. Node C, off on its own, having received no messages, does a local event and gets counter 1 as well. These two events are concurrent: neither node had any way of knowing about the other's work, so neither could have caused it. Lamport gives them the same number and has to break the tie arbitrarily to line them up. Now nudge the trace: give C a bit of prior history so its event lands on counter 3 while A's sits on 1. Lamport now reports 1 before 3, a clean order — but it's fiction. The events are still concurrent. The number ordered them anyway, and nothing in the number tells you the order isn't real.
Vector clocks: one counter per node#
The loss happened when we squeezed everything into one number. A single counter can't record who knew what — it only records how many events have piled up. So keep more. Instead of one counter, each node keeps a whole row of them, one entry per node in the system. Read node A's vector as: how many of A's own events A has done, how many of B's events A has heard about, how many of C's, and so on. This row is the node's vector clock.
- On a local event, a node adds one to its own entry, and leaves the others untouched.
- On sending, the node adds one to its own entry, then attaches a copy of its whole vector to the message.
- On receiving, the node takes the entry-by-entry maximum of its own vector and the message's, then adds one to its own entry.
The entry-by-entry maximum on receive is the heart of it. The sender's vector says how much of the world the sender had seen; taking the maximum folds all of that into the receiver's own knowledge without ever losing a count. Then the receiver bumps its own entry, because receiving is itself an event. Follow a short trace on three nodes A, B, and C. A does a local event and its vector becomes [1, 0, 0]. A sends to B, so A first goes to [2, 0, 0] and stamps the message with that. B receives: it takes the maximum of its [0, 0, 0] and the message's [2, 0, 0], getting [2, 0, 0], then bumps its own entry to [2, 1, 0]. B's vector now openly records that it has seen two of A's events and done one of its own.
Now the payoff — comparison. To compare two events, compare their vectors entry by entry. If every entry of the first is less than or equal to the matching entry of the second, and at least one is strictly less, then the first happened before the second. If every entry of the second is less than or equal to the first the other way around, the second happened before the first. And if neither of those holds — the first vector leads somewhere and the second leads somewhere else — then neither could have caused the other, and the two events are concurrent. That last case is the one Lamport could never surface, and here it falls right out of the numbers.
| Compare these two events | Their vectors | Entry by entry | Verdict |
|---|---|---|---|
| A's first event vs B's receive | [1, 0, 0] and [2, 1, 0] | every entry of the first is less than or equal to the second, one strictly less | the first happened before the second |
| A's first event vs C's lone event | [1, 0, 0] and [0, 0, 1] | the first leads in entry A, the second leads in entry C | concurrent — neither caused the other |
That is a vector clock, described independently by Colin Fidge (1988) and Friedemann Mattern (1989). It captures the happened-before relation completely: the ordering of two events is fully determined by their vectors, with no ambiguity and no arbitrary tie-break. Where a Lamport number gave you a hint, a vector gives you a verdict — happened-before, or concurrent, every time.
What it costs: a timestamp that grows with the cluster#
The extra power isn't free, and the cost is easy to name: a vector holds one entry per node, so its size grows with the number of nodes. A Lamport clock is a single integer forever. A vector clock is as wide as the cluster, and every event, every message, and often every stored version carries a full copy.
PredictA cluster has 50 nodes, and each vector entry takes 4 bytes. Roughly how much does one vector timestamp weigh, and how does that compare to a single Lamport counter?
Hint: One entry per node, times the bytes per entry.
Fifty entries at 4 bytes each is about 200 bytes per timestamp, versus 4 bytes for a Lamport counter — roughly fifty times larger, and that weight rides on every event, message, and stored version. Grow to 1000 nodes and each timestamp is around 4 kilobytes. This is why vector clocks shine in small, stable groups and strain in large or churning ones, and why the size, not the logic, is the thing real systems fight.
- Comparing two vectors is one pass over the entries, so a single comparison costs on the order of the number of nodes.
- Storage and network cost scale the same way: every timestamp is one number per node, everywhere it travels or rests.
- The entries must be keyed by a stable node identity, not a position that shifts as nodes come and go — otherwise two nodes could write into the same slot and quietly corrupt the ordering.
- Real systems bound the growth: they prune entries for nodes that have left, cap the vector and fall back to timestamps when it overflows, or switch to a compressed variant such as dotted version vectors.
When to reach for which clock
Every clock here answers a different question, and the trade is between how much the clock tells you and how much it costs to carry. Pick the weakest one that still answers the question you actually have.
- A plain wall-clock timestamp is tiny and means a real calendar time, but it can't order events across machines because clocks drift. Fine for logs and rough ordering; unsafe for deciding which write wins.
- A Lamport clock is a single integer and gives a consistent total order, which is all some algorithms need. But it can't tell concurrency from causality, so it can't detect conflicts.
- A vector clock detects concurrency exactly, which is what conflict resolution needs, but its timestamp grows with the cluster.
- A hybrid logical clock keeps a bounded size and stays close to real time while still respecting causality — a middle path when you want causal ordering and a timestamp that looks like a clock, without a full vector per event.
Lamport vs vector vs hybrid, side by side
| Lamport clock | Vector clock | Hybrid logical clock | |
|---|---|---|---|
| Size | One integer | One entry per node | Fixed, small (physical time plus a short counter) |
| Orders causal events | Yes | Yes | Yes |
| Detects concurrency | No | Yes | No (bounds size instead) |
| Relates to real time | No | No | Yes — stays close to the wall clock |
| Best for | A cheap total order | Conflict detection in a small, stable group | Causal order plus a real-time-like stamp |
Where vector clocks run in the wild
- Amazon Dynamo attaches a vector clock to every version of every object. On a read, if one version's vector is less than or equal to another's, the older one is dropped; if the vectors are concurrent, both are kept as siblings and handed back to the application to reconcile — the design that traded automatic conflict resolution for never silently losing a write.
- Riak followed Dynamo directly, exposing sibling versions on concurrent writes, and later moved to dotted version vectors — a refinement that fixes false-concurrency and sibling-explosion problems in the plain scheme while keeping the same happened-before verdicts.
- Voldemort, LinkedIn's Dynamo-style store, used vector clocks for the same versioning and client-side reconciliation.
- Hybrid logical clocks, which keep causality without a full vector, back the timestamps in CockroachDB, YugabyteDB, and MongoDB's cluster time — the practical answer when a per-event vector is too heavy but wall-clock timestamps are too weak.
PredictDynamo's paper notes that a version's vector clock can keep growing over time. Why would that happen, and why is it a problem worth engineering against?
Hint: A new entry appears whenever a new node coordinates a write to that object.
Each time a different node coordinates a write to an object, the object's vector gains an entry for that node. Under failures and rebalancing, many nodes can end up touching the same object, so the vector accumulates entries and the timestamp bloats — inflating every read, write, and stored copy of that object. Dynamo caps the vector and drops the oldest entries when it overflows, accepting a rare, tiny chance of a wrong ordering in exchange for bounded size. Riak's dotted version vectors attack the same growth more precisely.
Common misconceptions & gotchas
Do vector clocks tell me the real time an event happened?
No. Like Lamport clocks, they carry no notion of seconds or wall-clock time at all. They only order events relative to each other by cause and effect. If you need a real timestamp too, that's what hybrid logical clocks are for.
Isn't a Lamport clock just useless, then?
Not at all. When all you need is a single consistent total order — for example, to break ties deterministically or to give every operation a unique rank — a Lamport clock does it in one integer. You reach for a vector only when you specifically need to tell concurrency from causality, which is a stronger and more expensive requirement.
Does concurrent mean the two events conflict?
Concurrent means neither happened before the other — neither could have caused the other. Whether that's a conflict depends on the application. Two concurrent reads don't conflict; two concurrent writes to the same key usually do. Vector clocks find the concurrency; the application decides what to do about it.
Why increment your own entry again on receive, after taking the maximum?
Because receiving a message is itself an event on that node, and every event has to advance the node's own count. Skip the increment and two different receives could end up with the same vector, which would make genuinely ordered events look concurrent.
QuizTwo events have vectors [2, 1, 0] and [0, 0, 1]. What is their relationship?
- The first happened before the second
- The second happened before the first
- They are concurrent
- They are the same event
Show answer
They are concurrent — Compare entry by entry. In the first entry the first vector leads (2 against 0); in the third entry the second vector leads (0 against 1). Since each vector leads somewhere the other doesn't, neither is less than or equal to the other, so neither could have caused the other — the events are concurrent.
In an interview
Lead with the problem, not the definition: you can't order events across machines by wall-clock time because clocks drift, and often you don't need real time anyway — you need to know which event could have caused which. Then define happened-before in plain terms and introduce the Lamport clock: one counter per node, bump on every event, carry it on messages, and on receive take the larger value and add one. State its guarantee crisply — if one event happened before another, its number is smaller — and immediately name the catch: the reverse doesn't hold, so a Lamport clock can't tell concurrency from causality.
That catch is the setup for vector clocks, and the interviewer is usually waiting for it. Explain the shift from one counter to one entry per node, the entry-by-entry maximum on receive, and the comparison rule that yields happened-before or concurrent. Be ready to work a tiny three-node trace on the whiteboard and read off a concurrent pair. Close on the trade-off — vectors detect concurrency exactly but grow with the cluster — and land it in a real system: Dynamo and Riak keep concurrent versions as siblings for the client to merge, and hybrid logical clocks are the bounded-size compromise behind CockroachDB and friends. Mentioning the size problem, and how systems bound it, is what signals you've used this rather than just read about it.
References & further reading
- Lamport — Time, Clocks, and the Ordering of Events in a Distributed System (1978) — the origin of happened-before and the Lamport logical clock
- Fidge — Timestamps in Message-Passing Systems That Preserve the Partial Ordering (ACSC 1988) — one of the two independent introductions of vector clocks
- Mattern — Virtual Time and Global States of Distributed Systems (1989) — the other independent introduction, and the standard formulation cited today
- DeCandia et al. — Dynamo: Amazon's Highly Available Key-value Store (SOSP 2007) — vector clocks for versioning, sibling reconciliation, and bounding vector growth
- Kulkarni et al. — Logical Physical Clocks (Hybrid Logical Clocks, 2014) — combining causality with physical time in a bounded-size clock
- Kleppmann — Designing Data-Intensive Applications, Ch. 5 (Detecting Concurrent Writes) — version vectors, happens-before, and concurrent-write handling in replicated stores
Ready to try it?
The simulator is a real, deterministic implementation — pick a scenario and step through it, scrubbing the timeline forward and backward through every change.