How vector clocks and logical timestamps work

Why you cannot trust wall clocks

NTP keeps clocks roughly synchronized, but "roughly" is the problem. Leap seconds, VM live migration, manual clock adjustments, and network asymmetry mean two machines can assign timestamps that violate causality: event B responds to event A, yet B's timestamp is earlier than A's. Sorting by Date.now() in a geo-replicated database produces impossible histories and wrong conflict resolution.

Leslie Lamport's insight in 1978 was to define a partial order over events using only message sends and local steps — no synchronized clocks required. The CAP theorem later made clear that under partition you cannot have both immediate availability and strong linearizability everywhere; logical clocks sit in the middle ground of causal consistency, where everyone sees cause before effect even if they disagree on unrelated concurrent events.

Lamport timestamps: the simplest logical clock

Each process keeps a single integer counter, initialized to zero. On a local event, increment the counter and stamp the event. On sending a message, increment and attach the timestamp to the message. On receiving, set your counter to max(local, message_timestamp) + 1.

Define happened-before (→): if A and B are on the same process and A occurs before B in program order, then A → B. If A is a send and B is the corresponding receive, then A → B. Transitivity closes the relation. If A → B, then Lamport timestamp(A) < Lamport timestamp(B). The converse is false: equal or greater timestamps do not imply causality — concurrent events can share ordering ambiguity.

Lamport clocks give a total order extension of the partial order (break ties by process ID) useful for totally ordered logs, but they cannot tell whether two events are concurrent — both might have timestamp 42 on different machines with no causal link. That gap motivates vector clocks.

Vector clocks: detecting concurrency

A vector clock is an array of integers, one entry per process in the system (or per replica ID in a fixed membership set). Process i increments only its own index on local events and merges on receive: element-wise maximum with the incoming vector, then increment V[i].

Compare two vectors V and W:

• V ≤ W (V is dominated by W): every V[k] ≤ W[k].
• V < W (V is strictly before W): V ≤ W and at least one strict inequality.
• V || W (concurrent): neither V < W nor W < V — the events have no happened-before relationship.

Concurrent detection is the payoff. Dynamo, Riak, and Cassandra-style systems attach vector clocks (or compact descendants) to object versions. On read repair or write, if two versions are concurrent, the store surfaces a sibling conflict instead of silently picking the higher wall clock — which would discard a valid write.

Cost grows with replica count: an N-node vector is O(N) per update and merge. Production systems use version vectors (one counter per replica that actually wrote, not per slot in a fixed array), dotted version vectors (track dots per writer to allow accurate pruning), or bounded structures when N reaches thousands.

Version vectors vs vector clocks

The terms are often confused. A vector clock typically tracks causality among events in a distributed computation — who knew what when. A version vector tracks how many times each replica has updated a particular object key. They share merge semantics (component-wise max) but serve different namespaces: process IDs vs replica IDs per object.

Git commit hashes form a DAG of content-addressed history — a different shape, but the same question: "Is commit A an ancestor of B?" Vector clocks answer that for live replicas without a single central log. When you need a single authoritative order anyway, consensus protocols like Raft assign one total order via a leader; logical clocks complement that model on eventually consistent paths where leaderless writes are required.

Hybrid logical clocks and tracing

Pure logical time loses correlation with human-readable duration. Hybrid Logical Clocks (HLC), used in CockroachDB and research systems, combine physical time with Lamport-style counters: on each event, set hlc = max(physical, max(incoming_hlc)) then bump the logical sub-counter if physical did not advance. You keep causal ordering while timestamps stay roughly aligned with UTC for debugging and TTL expiry.

Distributed tracing (OpenTelemetry spans) faces the same problem: span start times on different hosts are not comparable for critical-path analysis until you align by trace context propagation — causality carried by parent span IDs, not by wall clock alone. Logical ordering is the hidden layer beneath every "waterfall" view in Jaeger or Honeycomb.

What logical clocks do not solve

Detecting concurrency is not the same as resolving it. Vector clocks tell you two shopping-cart updates conflict; they do not merge "add milk" and "add eggs" into a sensible cart. For commutative merges you need CRDTs or application-specific merge functions. For atomic multi-key updates across services you need transactions — two-phase commit or saga/outbox patterns — not just bigger vectors.

Last-write-wins (LWW) by timestamp is seductively simple and silently wrong under clock skew. If your system uses LWW, document the data-loss risk; if it uses vector clocks, document the conflict UI or merge policy. Neither replaces the other — they solve different layers of the event-driven replication stack.

Practical checklist

1. Never use unsynchronized wall clock alone to order writes across regions.
2. Use Lamport clocks when you only need a total order extension, not concurrency detection.
3. Use version vectors (or dotted vectors) per object when replicas can write independently.
4. Prune vector history when replicas are retired — stale entries bloat metadata.
5. Pair conflict detection with an explicit merge strategy (CRDT, user prompt, or domain rule).
6. Consider HLC when operators need timestamps that sort causally and look like dates in logs.

Blockchains like Solana expose a global slot clock on-chain — a strong total order for ledger events — but off-chain indexers, caches, and multi-region APIs still run as distributed systems. The same happened-before discipline applies wherever independent writers share state without a single leader.

Related on Solana Garden: CRDTs explained, CAP theorem explained, Raft consensus explained, Two-phase commit explained, Explainers hub.