Vector Clocks and Causal Ordering: How Distributed Systems Track What Happened Before What

Two users update the same document millisecond apart on opposite sides of the planet. Your database receives both writes, applies them in storage order, and silently loses one. No error. No conflict marker. Just a lost update dressed up as a successful write. The machine clocks on both nodes agreed. The clocks lied.

Physical time is a consensus illusion. In a distributed system, every node has its own clock ticking at a slightly different rate, drifting by microseconds per second and periodically corrected by NTP in steps that can jump backward or forward. A timestamp of 1715603200.042 on node A and 1715603200.037 on node B tells you almost nothing about which event actually happened first. Clock skew of tens of milliseconds is normal. Skew of hundreds of milliseconds is common. In correctness-critical code, trusting wall-clock order for event ordering is a latent bug waiting for a bad NTP resync to surface.

This article covers how distributed systems solve this. We start with Lamport timestamps as the simplest logical clock, move to vector clocks for true causal ordering, then look at version vectors for conflict detection in replicated stores, and finally dotted version vectors as the modern fix for a fundamental vector clock flaw. Each section includes TypeScript implementations you can adapt for production use.

Why Physical Clocks Cannot Order Events

The root problem is that there is no global observer in a distributed system. Each process knows only its own clock and what it hears from others through messages. Two events on separate nodes with no message path between them are genuinely concurrent: neither happened before the other in any causal sense, regardless of what wall clocks say.

NTP keeps clocks synchronized to within a few milliseconds under normal conditions, but “normal” does not cover:

• Network partitions that stall NTP corrections for minutes
• VM clock drift on hypervisors under heavy load
• Leap second smearing inconsistencies across a fleet
• Hardware clock drift on embedded or edge devices

Google Spanner sidesteps this with TrueTime, which uses GPS receivers and atomic clocks in every datacenter and exposes an uncertainty interval rather than a point timestamp. Spanner commits wait out the uncertainty window before finalizing. That infrastructure costs millions to replicate. For everyone else, logical clocks are the answer.

Lamport Timestamps: The Simplest Logical Clock

Leslie Lamport’s 1978 paper “Time, Clocks, and the Ordering of Events in a Distributed System” introduced the happens-before relation, written as a → b, meaning event a causally precedes event b. The rules are:

1. If a and b are events in the same process and a comes before b, then a → b.
2. If a is a message send and b is the corresponding receive, then a → b.
3. If a → b and b → c, then a → c (transitivity).

Events that are neither a → b nor b → a are concurrent.

Lamport timestamps implement this with a single integer counter per process:

class LamportClock {
  private counter: number = 0;

  // Call before sending a message or recording a local event
  tick(): number {
    this.counter += 1;
    return this.counter;
  }

  // Call when receiving a message carrying a remote timestamp
  update(remoteTimestamp: number): number {
    this.counter = Math.max(this.counter, remoteTimestamp) + 1;
    return this.counter;
  }

  get value(): number {
    return this.counter;
  }
}

// Usage
const nodeA = new LamportClock();
const nodeB = new LamportClock();

const tA1 = nodeA.tick(); // A sends message, timestamp = 1
// Message arrives at B with timestamp tA1
const tB1 = nodeB.update(tA1); // B receives, updates to max(0, 1) + 1 = 2
const tA2 = nodeA.tick();       // A does local work, timestamp = 2

console.log(`A sent at ${tA1}, B received at ${tB1}, A continued at ${tA2}`);
// A sent at 1, B received at 2, A continued at 2

Lamport timestamps give you a total order consistent with causality: if a → b then timestamp(a) < timestamp(b). But the converse does not hold. If timestamp(a) < timestamp(b), you cannot conclude a → b. The timestamps cannot distinguish between “A happened before B” and “A and B are concurrent and A got a lower number.”

This matters in practice. A log aggregation system sorting events by Lamport timestamp gets a valid causal order, but it cannot tell you which events were truly concurrent versus which one was causally prior. For databases doing conflict resolution, that distinction is exactly what you need.

Vector Clocks: Tracking Causal History Per Node

Vector clocks fix the limitation by maintaining a counter for every process in the system. Each node tracks not just its own logical time but its last known logical time for every other node.

type NodeId = string;
type VectorClock = Map<NodeId, number>;

function createVectorClock(nodeId: NodeId): VectorClock {
  return new Map([[nodeId, 0]]);
}

function increment(clock: VectorClock, nodeId: NodeId): VectorClock {
  const next = new Map(clock);
  next.set(nodeId, (next.get(nodeId) ?? 0) + 1);
  return next;
}

function merge(a: VectorClock, b: VectorClock): VectorClock {
  const result = new Map(a);
  for (const [node, time] of b) {
    result.set(node, Math.max(result.get(node) ?? 0, time));
  }
  return result;
}

// Partial order comparison
type Ordering = "before" | "after" | "concurrent" | "equal";

function compare(a: VectorClock, b: VectorClock): Ordering {
  const allNodes = new Set([...a.keys(), ...b.keys()]);
  let aLessOrEqual = true;
  let bLessOrEqual = true;

  for (const node of allNodes) {
    const aVal = a.get(node) ?? 0;
    const bVal = b.get(node) ?? 0;
    if (aVal > bVal) bLessOrEqual = false;
    if (bVal > aVal) aLessOrEqual = false;
  }

  if (aLessOrEqual && bLessOrEqual) return "equal";
  if (aLessOrEqual) return "before";
  if (bLessOrEqual) return "after";
  return "concurrent";
}

Now you can determine true causality:

// Simulate two nodes updating a shared key
let clockA = createVectorClock("A");
let clockB = createVectorClock("B");

// A writes first
clockA = increment(clockA, "A"); // A: {A:1}
const writeA = { value: "hello", clock: new Map(clockA) };

// B receives A's write and merges
clockB = merge(clockB, writeA.clock);
clockB = increment(clockB, "B"); // B: {A:1, B:1}
const writeB = { value: "world", clock: new Map(clockB) };

// A does another write without seeing B's update
clockA = increment(clockA, "A"); // A: {A:2}
const writeA2 = { value: "hello again", clock: new Map(clockA) };

console.log(compare(writeA.clock, writeB.clock)); // "before"
console.log(compare(writeA2.clock, writeB.clock)); // "concurrent"

When compare returns "concurrent", the two writes genuinely raced. Neither node saw the other’s update before writing. This is a true conflict, and your conflict resolution logic must decide what to do: last-write-wins, merge, or surface the conflict to the application.

The key insight is bidirectional: a → b if and only if clock(a) ≤ clock(b) component-wise with at least one strict inequality. Vector clocks give you the complete causal picture.

Version Vectors: Conflict Detection in Replicated Stores

Dynamo-style databases (Riak, Cassandra’s lightweight transactions, and Voldemort before Cassandra absorbed many of these ideas) adapted vector clocks into version vectors, which attach causal metadata to replicated values rather than to individual events.

The distinction matters. A vector clock tracks events on processes. A version vector tracks which replica last updated a value and when, in logical time. The structure is the same but the semantics differ: a version vector answers “which replica’s write does this value represent?”

type ReplicaId = string;
type VersionVector = Map<ReplicaId, number>;

interface VersionedValue<T> {
  value: T;
  version: VersionVector;
}

class ReplicatedStore<T> {
  private data = new Map<string, VersionedValue<T>[]>();
  private clock = new Map<ReplicaId, number>();

  constructor(private readonly replicaId: ReplicaId) {}

  write(key: string, value: T): VersionedValue<T> {
    const current = this.clock.get(this.replicaId) ?? 0;
    this.clock.set(this.replicaId, current + 1);

    const version: VersionVector = new Map(this.clock);
    const versioned: VersionedValue<T> = { value, version };

    const existing = this.data.get(key) ?? [];
    // Keep only versions that are not dominated by this new write
    const survivors = existing.filter(
      (v) => compare(v.version, version) !== "before"
    );
    survivors.push(versioned);
    this.data.set(key, survivors);

    return versioned;
  }

  read(key: string): VersionedValue<T>[] {
    // Returns all concurrent versions (siblings) or single winner
    return this.data.get(key) ?? [];
  }

  // Merge incoming version from another replica
  receive(key: string, incoming: VersionedValue<T>): void {
    // Update our clock with the incoming version info
    for (const [replica, time] of incoming.version) {
      const current = this.clock.get(replica) ?? 0;
      this.clock.set(replica, Math.max(current, time));
    }

    const existing = this.data.get(key) ?? [];
    const dominated = existing.filter(
      (v) => compare(v.version, incoming.version) === "before"
    );
    if (dominated.length === existing.length && existing.length > 0) {
      // All existing versions are dominated by incoming: replace
      this.data.set(key, [incoming]);
    } else {
      // Keep non-dominated versions and add incoming if not dominated
      const survivors = existing.filter(
        (v) => compare(v.version, incoming.version) !== "before"
      );
      if (!survivors.some((v) => compare(v.version, incoming.version) === "equal")) {
        survivors.push(incoming);
      }
      this.data.set(key, survivors);
    }
  }
}

When read returns more than one version, you have siblings: concurrent writes that neither dominated the other. Riak called these siblings and exposed them to the application. Shopping cart merges (union the items) or last-write-wins (pick by wall clock, accepting data loss risk) are the common strategies.

Dotted Version Vectors: Fixing Sibling Explosion

Standard version vectors have a known production problem called sibling explosion. Each concurrent write creates a new sibling. Under network instability or client retries, a single key can accumulate dozens of conflicting versions, all of which must be stored and returned on every read. The problem compounds: reads return siblings, clients that do not properly handle conflicts write back without resolving them, and the sibling count grows monotonically.

The root cause is that a write that arrives without a context (no client-provided version vector) is treated as potentially concurrent with every existing version. Clients that always write fresh have no causal context to declare, so every write spawns a new sibling.

Dotted version vectors (DVVs), formalized by Vitor Sérgio Lopes and Márcio Matos in their 2013 paper, solve this by tracking the exact dot (replica, counter pair) that created each value:

type Dot = { replica: ReplicaId; counter: number };

interface DottedValue<T> {
  value: T;
  dot: Dot; // The unique event that created this value
}

type DottedVersionVector = {
  dot: Dot;
  context: VersionVector; // Causal context seen by the client before writing
};

class DottedStore<T> {
  private entries = new Map<string, DottedValue<T>[]>();
  private counters = new Map<ReplicaId, number>();

  constructor(private readonly replicaId: ReplicaId) {}

  private nextDot(): Dot {
    const current = this.counters.get(this.replicaId) ?? 0;
    const next = current + 1;
    this.counters.set(this.replicaId, next);
    return { replica: this.replicaId, counter: next };
  }

  write(key: string, value: T, clientContext: VersionVector): DottedValue<T> {
    const dot = this.nextDot();
    const newEntry: DottedValue<T> = { value, dot };

    const existing = this.entries.get(key) ?? [];
    // Discard any existing entry whose dot is dominated by the client's context
    const survivors = existing.filter((entry) => {
      const entryTime = clientContext.get(entry.dot.replica) ?? 0;
      return entry.dot.counter > entryTime;
    });

    survivors.push(newEntry);
    this.entries.set(key, survivors);
    return newEntry;
  }

  read(key: string): { values: DottedValue<T>[]; context: VersionVector } {
    const values = this.entries.get(key) ?? [];
    // Context is the maximum counter seen per replica across all stored entries
    const context: VersionVector = new Map(this.counters);
    return { values, context };
  }
}

The critical difference: a client that reads (getting back a context), then writes back with that context, will replace the values it saw rather than creating a new sibling. The context acts as an acknowledgment: “I saw everything up to this point; replace those with my new value.”

Riak switched to dotted version vectors in version 2.0. The result was that well-behaved clients converge to a single value naturally, and only genuinely concurrent writes from clients that truly raced produce siblings.

Tradeoffs

Approach	Causal ordering	Conflict detection	Storage cost	Sibling handling	Infrastructure
Physical clocks	No (clock skew)	No	Minimal (one timestamp)	None	Standard NTP
Lamport timestamps	Partial (→ implies <, not reverse)	No	One integer per event	None	None
Vector clocks	Full	Yes	O(N) per event, N = node count	Requires application logic	None
Version vectors	Full per key	Yes	O(R) per key, R = replicas	Siblings surfaced to clients	None
Dotted version vectors	Full per key	Yes, with client context	O(R) per key	Convergent under good clients	None
Hybrid logical clocks (HLC)	Full + wall-clock proximity	Partial	One 64-bit integer	None	None

Hybrid logical clocks (HLCs), used in CockroachDB and YugabyteDB, encode both physical time and a logical counter in a single 64-bit integer. They give you causality plus timestamps close to wall-clock time, which helps with time-range queries. The tradeoff is that they require careful clock synchronization and bounded skew to remain correct. Under unbounded clock drift, HLC guarantees degrade.

Production Considerations

Node set growth changes the vector. Adding a new replica means adding a new entry to every vector clock in the system. If you shard by key range, nodes come and go frequently, and your vectors grow without bound. In practice, most systems garbage-collect vector entries for nodes that no longer exist or have not participated in recent writes.

Client context discipline is mandatory for DVVs. A client that never reads before writing will always write without context, recreating the sibling explosion problem. Your API contract must enforce the read-context-write cycle, or DVVs buy you nothing. This often means a conditional write endpoint that requires a context token from the most recent read.

Causality tracking has a write amplification cost. Every write must carry and update version metadata. For small values (flags, counters), the metadata can exceed the payload. Batching events under a single clock tick (all events in a single request share one logical tick) reduces amplification at the cost of coarser granularity.

Conflict resolution policy should be defined before you have conflicts. Discovering at 3 AM that your replicated store has 40,000 sibling entries for a high-traffic key is not the time to design your merge strategy. Define it per data type during schema design: shopping carts merge by union, user profile last-write wins with explicit field-level vector clocks for critical fields, financial ledgers never use last-write-wins under any circumstances.

Vector clock comparison is not free. Comparing two vectors is O(N) where N is the number of tracked nodes. At low node counts (3-9 replicas), this is negligible. At hundreds of nodes in a peer-to-peer or edge network, the cost adds up. Bloom clock approximations and interval tree clocks are research-grade alternatives for extreme fan-out scenarios, though neither has seen wide production adoption.

Closing

Physical timestamps are a coordination shortcut that works well enough until it does not. Lamport timestamps give you a causality-consistent total order with almost no overhead, sufficient for log ordering and distributed tracing. Vector clocks give you the full picture, exposing true concurrency at the cost of O(N) metadata per event. Version vectors bring that causal tracking to replicated data stores, and dotted version vectors close the sibling explosion gap that version vectors leave open.

The choice depends on what your system needs to prove. If you only need to know “did A happen before B in the same causal chain,” Lamport timestamps are enough. If you need to know “are these two writes genuinely concurrent and require conflict resolution,” vector clocks and their variants are the minimum viable mechanism. Building on physical timestamps for correctness is not a performance optimization: it is a correctness gamble.