Vector Clocks & Logical Timestamps

The Problem: Ordering Events Without a Global Clock

In a distributed system, nodes don't share a physical clock. Network Time Protocol (NTP) syncs clocks to within ~100 ms, but that's not accurate enough to order events that happen milliseconds apart. If node A writes a record at 12:00:00.001 and node B writes the same record at 12:00:00.002 on separate machines, their clocks may disagree about which happened first — making wall-clock ordering unreliable.

Logical clocks solve this by tracking causal relationships (happened-before) rather than real time. If event A causally influences event B (A sent a message that B received), we can safely say A happened before B — regardless of wall-clock time.

Lamport Timestamps

Leslie Lamport (1978) defined the happened-before relation (→) and introduced logical clocks. The rules are simple: each node maintains a counter `C`. On a local event, increment `C`. When sending a message, attach the current `C`. On receiving a message, set `C = max(local_C, received_C) + 1`.

// Lamport Timestamp rules
// Each node maintains integer counter C, initially 0

// Rule 1: Local event
function onLocalEvent():
  C = C + 1
  event.timestamp = C

// Rule 2: Send message
function onSend(message):
  C = C + 1
  message.timestamp = C
  send(message)

// Rule 3: Receive message
function onReceive(message):
  C = max(C, message.timestamp) + 1
  process(message)

Vector Clocks

Vector clocks extend Lamport timestamps to capture the full happened-before relation. Each node maintains a vector of counters — one per node in the system. Node i's vector clock `VC` is updated as: increment `VC[i]` on local events and sends; on receive, take element-wise max of local and received vectors, then increment `VC[i]`.

Comparing two vector clocks `VC_a` and `VC_b`: if every element of `VC_a` is ≤ every corresponding element of `VC_b`, then a → b (a happened before b). If neither dominates the other (some elements of `VC_a` are greater, some of `VC_b` are greater), the events are concurrent — no causal relationship.

type VectorClock = number[];

function happensBefore(a: VectorClock, b: VectorClock): boolean {
  // a → b: every element of a <= b AND at least one is strictly less
  const allLeq = a.every((val, i) => val <= b[i]);
  const someStrict = a.some((val, i) => val < b[i]);
  return allLeq && someStrict;
}

function concurrent(a: VectorClock, b: VectorClock): boolean {
  return !happensBefore(a, b) && !happensBefore(b, a);
}

// Example:
// VC_a = [2, 1, 0]  VC_b = [1, 2, 0]
// happensBefore(a, b) = false (a[0]=2 > b[0]=1)
// happensBefore(b, a) = false (b[1]=2 > a[1]=1)
// concurrent(a, b) = true — a and b are concurrent!

Version Vectors and Conflict Detection

Version vectors are a closely related concept used specifically for tracking data version causality (rather than event causality). DynamoDB and Cassandra use version vectors (sometimes called vector clocks in their documentation) to detect write conflicts on the same key.

When two clients concurrently update the same key (their version vectors are concurrent), the system cannot automatically resolve the conflict — it must surface both versions to the application or use a last-write-wins policy. Amazon's DynamoDB paper showed this in action: shopping cart additions from two offline clients would both be preserved.