CODING CHALLENGE · N°50

Vector Clock Merge

Easy Distributed SystemsCausalityConsistency

Vector clocks let processes with no shared time agree on which event caused which. The key operation is the merge on message receive: take the element-wise maximum of what you knew and what the message carried, then tick your own entry. Get it right and causality is preserved. Solve it in Python or TypeScript, with hidden tests.

The problem

Each process keeps a vector clock: a list with one counter per process. On receiving a message, a process updates its clock local using the message’s attached clock incoming by taking the element-wise maximum of the two, then incrementing its own entry (at index pid) by one. Implement receive(local, incoming, pid) returning the process’s new vector clock.

EXAMPLE 1

Input local = [2,1,0], incoming = [1,3,0], pid = 0

Output [3, 3, 0]

max([2,1,0],[1,3,0]) = [2,3,0], then +1 at index 0

EXAMPLE 2

Input local = [0,0,0], incoming = [0,0,0], pid = 1

Output [0, 1, 0]

nothing to merge; just tick your own entry

CONSTRAINTS

The two clocks have the same length (one entry per process).
Merge first (element-wise max), then increment your own entry — the increment records this receive event.
Element-wise max keeps the most up-to-date knowledge of every process’s progress; the self-increment orders this event after everything merged in.

SOLVE IT YOURSELF

Your turn — write it

Edit the stub, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? the hints are right above and Reveal solution is one click away.

YOUR TASK

Implement receive(local, incoming, pid): build a new clock whose i-th entry is max(local[i], incoming[i]), then add 1 to entry pid. Return it.

HINTS — 4 IDEAS

Take the element-wise maximum: merged[i] = max(local[i], incoming[i]) for every index.
After merging, increment the receiver’s own counter: merged[pid] += 1.
Do not mutate the inputs if the tests reuse them — build a fresh list.
On a local (non-message) event you would only do the increment; the merge is what makes a receive special.

CPython · WebAssembly

Approach, complexity & discussion — open after you solve

The approach

A vector clock maps each node to a counter. To merge two clocks, take the element-wise max of their counters. To compare: clock A happens-before B if every entry of A is ≤ B and at least one is strictly <; if neither dominates the other, the events are concurrent — a genuine conflict.

Complexity

Time O(N) in the number of nodes, for both merge and compare.

Common mistakes

Summing the counters on merge instead of taking the max.
Declaring an ordering when the clocks are concurrent — you must detect the conflict, not pick a winner.
Off-by-one on the local increment (a node bumps its own entry on each event).

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.

Finished this one? 0 / 75 Challenges done

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

Distributed Systems