Vector Clock Merge

Start from brute force

The obvious way to track causality is to carry it explicitly. Each process keeps its causal history, the set of every event id it knows happened before now, and attaches that set to each message; on receive it takes the union of the two sets and adds an id for the receive event itself. It is correct by definition: event a happened before event b exactly when a is in b’s history. But the history only grows. A clock and every message cost O(E) space, where E is the number of events in the whole system so far, and each union costs O(E) time, so messages grow without bound as the system runs.

The approach

The compression behind vector clocks: one process’s events happen one after another, so the part of any causal history that belongs to process j is always a prefix of j’s events, and a prefix is fully described by its length. A history therefore becomes one counter per process. The union of two prefixes of the same sequence is just the longer prefix, which is why the merge is an element-wise max, not a sum. The receive is a new event of this process, so after merging, the receiver adds one to its own entry.

The reference does both in two lines. merged = [max(a, b) for a, b in zip(local, incoming)] builds a fresh list, so neither input is mutated, and merged[pid] += 1 records the receive. The order matters: merge first, then tick, so the tick lands on top of everything just learned. The invariant: merged[j] counts the events of process j that happened before, or are, this receive.

Walk through an example

On the first example, process 0 learns that process 1 has reached event 3, keeps its own count of 2, and then ticks to 3 for the receive.

Complexity

A receive costs O(N) time and O(N) space for N processes: one pass for the max and one increment, written into a fresh list. Every message carries N integers however long the system has run. The causal-history version costs O(E) time and space per receive and per message, with E the number of events so far, which grows forever.

Edge cases to test

• The incoming clock is ahead on the receiver’s own entry: receive([0,0], [4,4], 1) returns [4, 5]. Ticking before merging would return [4, 4], and the receive event would vanish under the max.
• Nothing new arrives: receive([0,0,0], [0,0,0], 1) returns [0, 1, 0]. The receive still counts as an event.
• The inputs are not mutated: after receive(L, I, 0) with L = [2,1,0], L is still [2, 1, 0], because the reference builds a new list.
• Clocks of different lengths are not rejected. Python’s zip stops at the shorter one, so receive([1,2,3], [5,5], 0) silently returns [6, 5], and TypeScript returns [6, 5, NaN]. Check the lengths first.
• A bad pid: Python accepts -1 and ticks the last entry, returning [0, 0, 1], while TypeScript’s merged[-1] += 1 creates a stray property and ticks nothing. Validate 0 ≤ pid < N.

Common mistakes

• Summing the counters on merge instead of taking the max: on the first example that gives [4, 4, 0], counting events that never happened.
• Ticking before merging. If the incoming clock already has a count for pid at least as high, the max swallows the tick and the receive event is lost, as the incoming-ahead test shows.
• Off-by-one on the local increment (a node bumps its own entry on each event).
• Mutating local in place and returning it, so a caller that kept the old clock, such as a test reusing its inputs, finds it changed.

Follow-ups an interviewer asks next

How do you compare two clocks?

A happened before B when every entry of A is ≤ the matching entry of B and at least one is strictly smaller. If neither clock is ≤ the other everywhere, the events are concurrent: [2,1,0] and [1,3,0] each lead in one entry, so neither caused the other. That concurrent case is what a replicated store uses to flag a write conflict instead of silently keeping one value.

What happens on a send or a local event?

A local event and a send only tick the process’s own entry, and a send then attaches a copy of the clock to the message. Only a receive merges. With those three rules, comparing two clocks reproduces exactly the happened-before relation between the two events they label.

There are thousands of processes. Do clocks get too big?

Store each clock as a map from process id to counter and omit zeros, so it names only the processes that actually influenced it. Designs such as dotted version vectors bound the size by the number of replicas rather than clients. When only an ordering is needed, not concurrency detection, a scalar Lamport clock costs O(1).

Why not use wall-clock timestamps instead?

Physical clocks drift and can jump backward after synchronization, so a later write can carry an earlier timestamp, and last-writer-wins then silently drops it. Timestamps also put concurrent events in an arbitrary order, hiding the conflict. Hybrid logical clocks combine physical time with a logical counter for systems that need timestamps near real time that still respect causality.

Where this shows up

Vector clocks track causality in distributed systems (Dynamo, many CRDTs): they tell you whether two updates are causally ordered or truly concurrent, which wall-clock timestamps cannot because clocks drift. Detecting concurrency is exactly what lets the system flag a conflict for resolution instead of silently losing a write.

Reference solution

def receive(local, incoming, pid):
    merged = [max(a, b) for a, b in zip(local, incoming)]  # element-wise max
    merged[pid] += 1                                        # tick own entry
    return merged


print(receive([2, 1, 0], [1, 3, 0], 0))   # -> [3, 3, 0]
print(receive([0, 0, 0], [0, 0, 0], 1))    # -> [0, 1, 0]

function receive(local: number[], incoming: number[], pid: number): number[] {
  const merged = local.map((a, i) => Math.max(a, incoming[i])); // element-wise max
  merged[pid] += 1;                                             // tick own entry
  return merged;
}

console.log(receive([2, 1, 0], [1, 3, 0], 0));  // -> [3, 3, 0]
console.log(receive([0, 0, 0], [0, 0, 0], 1));  // -> [0, 1, 0]