Lamport Clocks vs Vector Clocks: Detecting Concurrent Writes

The idea: same events, two kinds of clock

Replicas of a database have no shared clock, so they stamp events with logical clocks instead. A Lamport clock is one integer per process. A vector clock is one integer per process for every process. The page runs both on the same three replicas P1, P2, P3 and the same events, one panel each, and follows what each does to a replicated key: a shopping cart, the example from Amazon's Dynamo paper.

On the canvas	Meaning
two panels	the same events; Lamport clock with last-write-wins on the left (top on a phone), vector clock with siblings on the right (below)
dot with a letter	one event: yellow a client's write (Add Item), blue a send, green a receive; orange the two events being compared
arrow	a sync message carrying the sender's clock and its versions of cart
key cart rows	what each replica stores: one value with its (L, id), or every version with its vector

The merge rule

Both clocks tick on every event of their own process and merge on a receive:

• Lamport: L = L + 1 on a write or send; on a receive L = max(L, Lmsg) + 1.
• Vector: V[i] = V[i] + 1 on a write or send; on a receive take the entry-wise max, V = max(V, Vmsg), then add 1 to the own entry.

In Demo 1: the merge rule on a message, P1 writes (a: L=1, [1,0,0]) and sends (b: L=2, [2,0,0]). P2 receives at c: L = max(0, 2) + 1 = 3 and max([0,0,0], [2,0,0]) = [2,0,0], then its own entry + 1 = [2,1,0]. Entry V[j] reads "I have seen the first V[j] events of P_j".

Comparing two vectors

Two vectors compare entry by entry:

Vectors	Example	Meaning
every entry ≤, and not equal	[1,0,0] vs [2,2,2]	e happened before f (e → f)
every entry ≥, and not equal	[2,1,0] vs [2,0,0]	f → e
some entries larger, some smaller	[0,1,0] vs [2,0,0]	concurrent (e ∥ f)

This is exact: e → f if and only if V(e) < V(f). In Demo 2: a happened-before chain, P1's write a [1,0,0] reaches P3 through P2, and P3's write f is [2,2,2]: a → f.

What Lamport timestamps cannot tell

Lamport time keeps only one direction: e → f implies L(e) < L(f), but L(e) < L(f) does not imply e → f. In Demo 3: Lamport order, yet concurrent, P2's write c has L=1 and P1's write b has L=2. The numbers look ordered, but no message ever linked them: the vectors [0,1,0] and [2,0,0] are concurrent. From two Lamport numbers you can only rule out one direction; "before" and "concurrent" look the same.

Siblings in a Dynamo-style store

A replicated key-value store has to decide what to keep when two versions of a key meet during replication. Here a client's write at a replica is a read-modify-write: read the cart, add an item, write it back. The versions travel between replicas in sync messages.

• Last-write-wins (left): each version carries (L, replica id), and the larger one wins. Simple, and one value per key, but when two writes are concurrent one of them is thrown away with no error.
• Vector clocks (right), as in Dynamo, Riak and Voldemort: each version carries its vector. A version whose vector is ≤ another's is old and dropped; versions that are concurrent are all kept as siblings. The next client read gets every sibling, merges them (for a cart, the union) and writes one version whose vector is ≥ all of them, which ends the conflict.

In Demo 4: concurrent writes, LWW loses one, P1 adds milk ((1,P1), [1,0,0]) and P2 adds eggs ((1,P2), [0,1,0]) without hearing of each other. After P1 syncs to P2 and P2 back to P1, last-write-wins holds {eggs} everywhere: milk is gone. The vector side holds both as siblings. Demo 5: the next write merges siblings then adds jam at P2: the client reads both siblings and writes {eggs,jam,milk} at [2,3,0]. Demo 7: a three-way conflict leaves three siblings on P2.

A write that already saw the earlier one is not a conflict. In Demo 6: read, then write: no conflict, P2 adds eggs after milk has reached it, so its vector [2,2,0] is ≥ milk's [1,0,0] and simply replaces it, and both panels agree.

Lamport vs vector clocks

	Lamport clock	Vector clock
Size per event or version	one integer	one integer per process (or replica)
e → f ⇒	L(e) < L(f)	V(e) < V(f)
The converse	no: smaller L may be concurrent	yes: exact
Detects concurrent writes	no	yes
Total order	yes, by (L, id)	no, only a partial order
Conflict policy it fits	last-write-wins	siblings, or a merge function
Used in	total-order broadcast, mutual exclusion, LWW stores	Dynamo, Riak, Voldemort, causal consistency

Version vectors and their variants

Real stores use version vectors: one entry per replica that coordinates writes, not one per client or per event, so a vector stays small. Dynamo also truncates old entries, which can make an old version look concurrent and create a false sibling. Riak's dotted version vectors fix a related problem, siblings that pile up when many clients write through the same replica. Systems that want one number but closer to real time use a hybrid logical clock. Data types that merge concurrent updates by themselves, so no sibling needs a client, are CRDTs. The one-diagram view of both clocks, with the total order, is on Lamport clocks and vector clocks; why an always-available store faces these conflicts at all is on the CAP theorem.

What the page leaves out

Messages are delivered at once and a sync carries every version, so the page skips network delay, quorum reads and writes (N, R, W), read repair, hinted handoff and Merkle-tree anti-entropy. It keeps one key. It also skips the client-side context that Dynamo returns with a read and sends back with a write, vector pruning, dotted version vectors, and merge functions other than set union (a removed item comes back after a union merge, which is why carts use an OR-Set).

References

Leslie Lamport, "Time, Clocks, and the Ordering of Events in a Distributed System" (1978)

DeCandia et al., "Dynamo: Amazon's Highly Available Key-value Store" (SOSP 2007)

Riak KV documentation: causal context, siblings and dotted version vectors