Logical and Vector Clocks: Ordering Events Without a Shared Clock

What you'll learn: By the end of this lesson you will be able to define "happened before" and "concurrent" for events on different machines, apply the Lamport clock rules and say exactly what a Lamport timestamp does and does not prove, apply the vector clock rules and compare two vectors to find an ordering or a conflict, use version vectors to keep concurrent writes as siblings, explain why the identity that owns a counter matters and what pruning a vector costs, and run a Java lab that stamps one history both ways.

Two cousins each keep a copy of a family recipe card and post their changes to each other. When a card arrives you can sometimes tell at once that it is the old card plus a new line, so you throw the old one away. Sometimes the two cards have each gained a different line from the same starting card, and neither is the newer. You have to merge them by hand. No wall clock helps: either cousin may have written first, and the post may have been slow.

Distributed systems face the same question for every replicated value: is this version built on that one, or did two writers act without seeing each other? The earlier lesson IDs, clocks and ordering gives a short introduction. This lesson is the dedicated treatment: the definitions, the exact rules, a lab that runs them, and the way storage systems use them. Its partner is Quorum Reads and Writes, which needs a "newest version" rule to pick among replicas.

Verified with Java 25, Lamport's 1978 paper, Mattern's 1988 paper on vector time, the Dynamo paper (SOSP 2007) and the Riak KV documentation, on 2026-11-08.

The core idea

Order events by cause, not by wall-clock time. An event a happened before b if information could have flowed from a to b. A Lamport clock is one counter that respects that order but cannot tell you when two events were unrelated. A vector clock keeps one counter per actor and can: two vectors are either ordered or concurrent, and concurrent means the writes did not see each other. The practical use is conflict detection: a store that labels each version with a vector keeps both versions when the labels are concurrent, instead of silently dropping one.

Three illustrations run through the lesson, each labelled:

• Minimal example: three processes and nine events stamped with both clocks, in the lab.
• Realistic example: two ShopStream staff editing the same product at once, in "In practice".
• Failure example: two clients writing through one server, where a lost update looks like a normal successor.

Happened before and concurrent

Lamport's 1978 paper defines the relation "happened before", written a → b, as the smallest relation that satisfies three conditions: (1) if a and b are events in the same process and a comes before b, then a → b; (2) if a is the sending of a message and b is the receipt of that same message, then a → b; (3) if a → b and b → c then a → c. Two distinct events are concurrent if neither happened before the other. The paper's reading: a → b means it is possible for a to causally affect b, and concurrent events cannot affect each other.

Figure 1. The history the lab stamps. How to read this: time runs downward, but the vertical position of events on different lines means nothing. p2 → q2 because of m1, and p1 → r3 through p2, q2, q3. q1 and p2 are concurrent: no chain of messages links them.

No clock is needed to state the definition, and none can observe it directly: each process sees only its own events and the messages it receives. A clock is a way to attach a label that preserves the relation.

Lamport clocks

A Lamport clock is a single counter per process. The paper's two implementation rules are IR1 (a process increments its clock between any two successive events) and IR2 (a message carries the sender's clock value as its timestamp; on receipt the process sets its clock to a value greater than or equal to its present value and greater than the message timestamp). The usual code is time = max(time, message.time) + 1 on receipt.

These rules give the Clock Condition: if a → b then C(a) < C(b). The paper notes that the converse cannot hold, since it would force every pair of concurrent events to occur at the same time. So a smaller Lamport timestamp does not prove one event happened before the other; the two may be concurrent. Breaking ties by an arbitrary order on process ids turns the timestamps into a total order that extends happened-before. That total order is useful for agreeing on one sequence, and it invents an order between concurrent events.

q1 has stamp 1.Q and p2 has 2.P, so a total order puts q1 first. They are concurrent. The stamp cannot say so.

Vector clocks

A vector clock gives each actor its own counter, so a clock is a map from actor to count (a missing actor is zero). Mattern's 1988 paper states the rules: a process ticks by incrementing its own component on every event; a message carries the sender's vector; the receiver combines the two with the component-wise maximum. Vectors are compared component by component:

• u is at or before v if every component of u is less than or equal to the same component of v;
• u is before v if that holds and the vectors differ;
• u and v are concurrent if neither is at or before the other.

Mattern's Theorem 10 says that for any two events, e → e' exactly when C(e) is before C(e'), and e and e' are concurrent exactly when their vectors are concurrent. The vector loses nothing about causality, which the Lamport counter does. The price is one counter per actor, so the clock grows with the number of actors.

Figure 2. The whole comparison in one picture. How to read this: a missing actor counts as zero. The last box is the one a Lamport clock cannot reach.

The same events with vectors: p1 {P=1}, p2 {P=2}, q1 {Q=1}, q2 {P=2, Q=2}, r3 {P=2, Q=3, R=3}. Now q1 {Q=1} against p2 {P=2}: neither is at or before the other, so they are concurrent, and p2 {P=2} against q2 {P=2, Q=2} is before, as the message says.

Version vectors in a store

The Dynamo paper (section 4.4) applies this to stored data. A vector clock is "a list of (node, counter) pairs", one attached to every version of every object. If the counters on the first object's clock are less than or equal to all of those on the second, the first is an ancestor and can be forgotten; otherwise the two are in conflict and need reconciliation. A client that updates an object passes the context it got from an earlier read, which carries the clocks, so the new version descends from everything the client saw. A read that finds branches that cannot be reconciled by clocks returns all of them, and an update with that context collapses them into one new version. The paper's example is a shopping cart: an add is never lost, but deleted items can resurface.

Figure 3. The version history of the paper's Figure 3. How to read this: D3 and D4 each descend from D2 and are concurrent, so a read returns both. D5 is written with a context that contains both clocks, so it descends from both and replaces them. The lab replays exactly these clocks.

Who owns a counter

In the paper's example the node that handles the write increases its own counter. The lab models that bare design as "server as actor" and shows what a single counter per server cannot do (part 3; a real store may add logic around it): two clients that read the same version and write through the same server get {Sx=2} and {Sx=3}, a successor relationship the second client never had, and the first write is dropped without any sign of a conflict. If each client is an actor, the same two writes get {Sx=1, alice=1} and {Sx=1, bob=1}, which are concurrent, and both are kept. The cost is that clocks grow with the number of clients.

Two bounds follow. Dynamo limits clock size by storing a timestamp with each pair and, when the number of pairs reaches a threshold ("say 10"), removing the oldest pair; the paper says this can lead to inefficiencies in reconciliation because descendant relationships can no longer be derived accurately, and that the problem had not surfaced in production. Part 4 of the lab shows what that means: after dropping Sy's entry, a clock that was a descendant looks concurrent with its ancestor, a false conflict. The Riak documentation names a different fix: dotted version vectors, which "identify each value with the update that created it", so duplicate values can be recognised and the number of siblings tracks the number of concurrent updates. It says it strongly recommends them over plain vector clocks, and that unreconciled siblings can pile up into a "sibling explosion".

Build it: clocks and versions in Java

This is the minimal example, a model you can run.

Goal. Stamp one history with a Lamport clock and a vector clock, see which pairs only the vector clock classifies, replay the Dynamo version history, and watch a concurrent write get lost or kept depending on who owns the counter.

Setup. From the repository's examples/backend folder:

cd examples/backend && ./gradlew :labs:logical-and-vector-clocks:test
./gradlew -q :labs:logical-and-vector-clocks:run

The first command runs 16 tests. The second prints the four parts below. The code is in examples/backend/labs/logical-and-vector-clocks/src/main/java/buildingai/labs/logicalclocks/ (LamportClock, VectorClock, LogicalProcess, VersionedRegister).

How the model works. VectorClock is an immutable map from actor to counter with tick, merge (component-wise maximum) and compare, which returns EQUAL, BEFORE, AFTER or CONCURRENT. VersionedRegister holds the versions of one key: a new version replaces the ones its clock descends from, and a version neither before nor after another is kept as a sibling. The comparison is the code behind Figure 2:

public Order compare(VectorClock other) {
    boolean thisCoversOther = descendsFrom(other);
    boolean otherCoversThis = other.descendsFrom(this);
    if (thisCoversOther && otherCoversThis) {
        return Order.EQUAL;
    }
    if (otherCoversThis) {
        return Order.BEFORE;
    }
    if (thisCoversOther) {
        return Order.AFTER;
    }
    return Order.CONCURRENT;
}

Steps. Run the tests, then the demo. The tests compare both clocks with an independent computation of happened-before (earlier on one process, send before receive, transitive closure) over 20 random histories: Lamport stamps satisfy the Clock Condition and not its converse, and vector clocks classify every pair of events exactly. Other tests check that merge is commutative, associative and idempotent, that replicas receiving the same versions in any order, with duplicates, end with the same siblings, and that dropping an entry can invent a conflict.

Expected output, captured from a real run (Java 25.0.3, 2026-11-08):

PART 1. One history, two kinds of clock. Processes P, Q, R. 'lamport' is the scalar clock (time.process), 'vector' the vector clock.
event        lamport  vector
p1           1.P      {P=1}
p2 send m1   2.P      {P=2}
p3           3.P      {P=3}
q1           1.Q      {Q=1}
q2 recv m1   3.Q      {P=2, Q=2}
q3 send m2   4.Q      {P=2, Q=3}
r1           1.R      {R=1}
r2           2.R      {R=2}
r3 recv m2   5.R      {P=2, Q=3, R=3}

pair         lamport says       vector says  truth
p2 vs q2     p2 first (2.P < 3.Q) before       causal: the message m1 goes from p2 to q2
p1 vs r3     p1 first (1.P < 5.R) before       causal: p1 -> p2 -> q2 -> q3 -> r3
q1 vs p2     q1 first (1.Q < 2.P) CONCURRENT   concurrent: q1 never heard from P
p3 vs r2     r2 first (2.R < 3.P) CONCURRENT   concurrent: P and R never exchange a message
q3 vs r1     r1 first (1.R < 4.Q) CONCURRENT   concurrent: no message path between r1 and q3

PART 2. Version history of the Dynamo paper's Figure 3 (servers Sx, Sy, Sz; the writing server's counter goes up).
  a client writes D1 via Sx                              -> D1{Sx=1}
  the client updates it via Sx -> D2 descends from D1    -> D2{Sx=2}
  Sx now holds [D2{Sx=2}]
  same client updates D2 via Sy                          -> D3{Sx=2, Sy=1}
  a different client updates D2 via Sz                   -> D4{Sx=2, Sz=1}
  D3 vs D4: CONCURRENT; D1 vs D4: BEFORE
  a node that sees D1, D3 and D4 keeps [D3{Sx=2, Sy=1}, D4{Sx=2, Sz=1}] (D1 is obsolete), context {Sx=2, Sy=1, Sz=1}
  the client reconciles and writes via Sx                -> D5{Sx=3, Sy=1, Sz=1}
  the node now holds [D5{Sx=3, Sy=1, Sz=1}]

PART 3. Alice and Bob both read cart {milk} and add an item at the same moment.
  3a. The server Sx is the actor, so its counter is the only one that moves.
      Alice writes milk,eggs{Sx=2}, Bob writes milk,bread{Sx=3}
      cart holds [milk,bread{Sx=3}]  (Alice's eggs are gone, and nothing reported a conflict)
  3b. The client is the actor, so each write carries its own counter.
      Alice writes milk,eggs{Sx=1, alice=1}, Bob writes milk,bread{Sx=1, bob=1}
      cart holds [milk,eggs{Sx=1, alice=1}, milk,bread{Sx=1, bob=1}]  (siblings: true)
      Alice reconciles with the read context -> milk,eggs,bread{Sx=1, alice=2, bob=1}
      cart holds [milk,eggs,bread{Sx=1, alice=2, bob=1}]
  3c. Last-write-wins on a Lamport stamp instead of a clock per version.
      Alice's write is stamped 1.alice, Bob's 1.bob: the larger stamp, 1.bob, wins and the other write is discarded without any sign of a conflict

PART 4. Pruning a clock to bound its size can invent a conflict.
  {Sx=2, Sy=1} vs {Sx=2, Sy=1, Sz=1}: BEFORE
  drop Sy's entry from the newer clock -> {Sx=2, Sz=1}
  {Sx=2, Sy=1} vs {Sx=2, Sz=1}: CONCURRENT  (a descendant now looks like a sibling)

Break it. In VectorClock.merge, replace Math::max with Math::min: the random-history test and the merge-law test fail. In LogicalProcess.receive, drop the merge so a receive forgets what the message carried: the random-history test fails because vector clocks stop ordering causal pairs.

Stretch. Add per-client actors with a size limit that drops the oldest entry and count the false conflicts in a random history. Implement dotted version vectors so part 3a keeps both writes. Add a hybrid logical clock and compare it with the Lamport clock under skewed physical clocks.

What the model leaves out. Real networks, replication between replicas (receive stands in for it), pruning policies, dotted version vectors and any claim about how a particular product chooses its actors.

Choosing a clock

In practice: two staff edit one product at once

This is the realistic example, an educational scenario on the course's running example ShopStream; nothing in it describes a real company.

This is a realistic scenario, not a case history.

The situation

Store staff update products: the store manager changes the price on the back-office app while a shelf stacker marks the same product's stock on a tablet. Both edits start from the same version. The catalogue replicas live in more than one zone and accept writes during a partition, so both edits can reach different replicas before either sees the other.

Starting architecture

Figure 4. The design: clocks decide, a merge resolves. How to read this: every edit carries the context from the client's last read. Replicas compare vectors. Ordered versions replace each other; concurrent ones go to the conflict queue instead of overwriting.

Options considered

The decision

Option C for products, with the actor being the editing session and a merge rule per field: price and stock are different fields, so concurrent edits to different fields merge without a human, and concurrent edits to the same field go to the conflict queue. The merge writes a new version with the read context, which collapses the siblings. Orders and payments stay on one writer each, as in the CAP lesson.

Rollout and verification

A rollout would replay recorded edit pairs through the lab's register and check that every concurrent pair produced two siblings and every ordered pair one version. Verification tracks the siblings count per product, the age of the oldest unmerged sibling set, and the number of actors per vector.

The 2 a.m. failure

The page reads: a manager reports that a price change from yesterday has reverted. The catalogue API used the coordinating server as the only actor, so the manager's edit and the stacker's edit, made from the same version through the same server, got {Sx=2} and {Sx=3}. The second looked like a successor and replaced the first, as in part 3a of the lab.

Figure 5. The lost update. How to read this: both writers hold the same context, so neither saw the other. One counter makes the second write look like a successor of the first, so the server discards the first version instead of keeping two siblings.

The check is the audit trail: find edits whose read context did not contain the version that was stored when they arrived. The mitigation is to restore the lost value from the log. The lasting fix is to make the editing session an actor, or to use dotted version vectors, and to alert whenever an edit arrives with a context that does not cover the stored version.

Architect's notes

• Ask who the actor is. The identity that owns a counter decides which writes are seen as concurrent.
• Keep the context round trip. A read must return the context and a write must send it back; without it every write looks like a successor.
• Concurrent is not wrong. It means a merge is needed. Decide the merge rule per field before the first conflict, not after.
• Bound and watch clock size. Count actors per vector, and know what pruning does before you enable it.
• Prefer one writer per key when conflicts cannot be merged without losing intent.

Common mistakes

• Treating a smaller Lamport stamp as proof of causality. It proves nothing about concurrent events.
• Comparing vectors with a single number. Two vectors can each be ahead somewhere.
• Using the server as the only actor for multi-client writes. A lost update looks like a normal successor.
• Dropping the context. A write without the context it was built on cannot be ordered against what it never saw.
• Pruning without knowing the cost. A descendant can appear concurrent, producing false conflicts.
• Choosing last-write-wins by default. It hides every concurrent write behind a timestamp.

Key takeaways

• Happened-before is defined by process order, messages and transitivity; concurrent means neither happened before the other.
• A Lamport clock satisfies a → b implies C(a) < C(b) and nothing in the other direction.
• A vector clock orders a pair exactly when they are causally related and marks the rest concurrent.
• Version vectors label each stored version; ordered versions replace each other and concurrent ones are kept as siblings.
• The actor that owns a counter, and any pruning of the vector, decide how many conflicts you detect and how many you invent.

Practice exercises

Exercise 1 (20 min). Stamp a history of your own with three processes and six events by hand, with both clocks, and list every pair the Lamport stamps would order wrongly as causal.

Exercise 2 (45 min). Run the lab and explain parts 3a and 3b in terms of which actor's counter moved.

Exercise 3 (1 hour). Run "Break it" twice and say which test caught each change and why.

Exercise 4 (2 hours). For ShopStream's product edits, write the merge rule for each field (name, price, stock, description) and say which concurrent edits need a human.

Related reading

• IDs, Clocks and Ordering: wall clocks, Lamport and hybrid logical clocks in a wider setting.
• Quorum Reads and Writes: where the "newest version" rule is used.
• CAP Theorem and PACELC: the available side of a partition and why merges are needed.
• Replication: leaderless replication and conflicts.

Official documentation

• Lamport, Time, Clocks, and the Ordering of Events in a Distributed System (Communications of the ACM, 1978).
• Mattern, Virtual Time and Global States of Distributed Systems (1988).
• DeCandia et al., Dynamo: Amazon's Highly Available Key-value Store (SOSP 2007): section 4.4.
• Riak KV documentation, causal context.