Vibe Engines is free, interactive AI engineering & system design — runs in your browser. Pick a learning path →
Vector Clock Merge
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.
Your turn — write it
Edit the stub, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? open the hints under the problem, or Reveal solution is one click away.
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.
Examples and constraints 4 examples
local = [2,1,0], incoming = [1,3,0], pid = 0[3, 3, 0]local = [0,0,0], incoming = [0,0,0], pid = 1[0, 1, 0]local = [5,2], incoming = [3,7], pid = 0[6, 7]local = [0,0], incoming = [4,4], pid = 1[4, 5]- 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.
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.
Approach, complexity & discussion — open after you solve
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.
receive. The highlighted cells are the entries that win the max; the tick then lands on process 0’s own entry, on top of what it just learned.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.
| step | index | local[i], incoming[i] | value | merged |
|---|---|---|---|---|
| 1 | 0 | 2, 1 | max = 2 | [2] |
| 2 | 1 | 1, 3 | max = 3 | [2, 3] |
| 3 | 2 | 0, 0 | max = 0 | [2, 3, 0] |
| 4 | pid = 0 | tick own entry | 2 + 1 = 3 | [3, 3, 0] |
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)withL = [2,1,0],Lis still[2, 1, 0], because the reference builds a new list. - Clocks of different lengths are not rejected. Python’s
zipstops at the shorter one, soreceive([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-1and ticks the last entry, returning[0, 0, 1], while TypeScript’smerged[-1] += 1creates a stray property and ticks nothing. Validate0 ≤ 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
pidat 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
localin 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.
The idea has a clear lineage. Leslie Lamport’s 1978 paper “Time, Clocks, and the Ordering of Events in a Distributed System” defined the happened-before relation and the scalar clock that respects it. Vector clocks were described independently by Colin Fidge and Friedemann Mattern in 1988 to close the gap Lamport clocks leave: a scalar can say “not after”, but only a vector can say “concurrent”. Every system on this page is still answering Lamport’s question, which events could have influenced which.
The Dynamo paper shows both the value and the cost. Each version of a key carries a clock of (node, counter) pairs; when a read finds versions whose clocks do not dominate one another, it returns all of them and the application merges them. The paper’s own example is a shopping cart, merged by union, and it notes the consequence: an item deleted in one branch can reappear after the merge. To stop clocks growing as more coordinating nodes touch a key, Dynamo truncates them, dropping the oldest pair once the clock passes a size threshold, and accepts that truncation can make a descendant look concurrent with its ancestor. The trade-off is explicit: a little false concurrency in exchange for bounded metadata.
A third use is causal delivery in group messaging. If each broadcast carries the sender’s clock, a receiver can hold a message from process j until it has seen everything that message depends on: deliver it only when its entry j is exactly one more than the receiver’s entry j (it is j’s next message) and every other entry is no greater than the receiver’s (nothing it saw is missing here). Messages that arrive early wait in a buffer. That rule guarantees no one ever sees a reply before the post it answers, without any global clock.
Check yourself
What does receive([4, 0, 2], [1, 5, 3], 2) return?
[4, 5, 4]. The max is [4, 5, 3], taking entry 0 from local and entries 1 and 2 from incoming; then process 2 ticks its own entry from 3 to 4.
A buggy version ticks before merging. What do it and the reference return for receive([1, 2], [0, 5], 1)?
The reference returns [1, 6]. Ticking first turns local into [1, 3], and the max with [0, 5] gives [1, 5]: the receive carries the same entry 1 as the message it received, so the two events are indistinguishable and the receive is lost.
After the first example, process 0 is at [3, 3, 0]. Another event has clock [2, 4, 1]. Did one happen before the other?
Neither: they are concurrent. [3, 3, 0] is ahead in entry 0 and [2, 4, 1] is ahead in entries 1 and 2, so neither is ≤ the other everywhere. Compare [2, 3, 0], which is ≤ [3, 3, 0] in every entry and smaller in one, so it happened before.
A system has 1,000 processes and stores each counter in 8 bytes. How much clock does every message carry, compared with a Lamport clock?
8,000 bytes per message for the full vector, against 8 bytes for a single Lamport counter. The vector buys concurrency detection; storing it as a sparse map of only the processes that influenced the event, or bounding it by replicas rather than clients, is how real systems keep that price down.
Reference solution
Reference solution — Python
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]Reference solution — TypeScript
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]Questions about Vector Clock Merge
Why does a vector clock merge use the maximum and not the sum?
Each entry counts how many events of one process are known to have happened. A process’s events form a single sequence, so knowing its first 3 events from one source and its first 2 from another means knowing its first 3, not 5. Taking the maximum keeps the most up-to-date knowledge of each process without inventing events. Summing counts shared history twice: on the first example it gives 4 for process 0 and 4 for process 1, claiming events that never happened, and every later comparison built on those clocks is wrong.
Why increment your own entry after merging, not before?
Because the receive is a new event that happens after everything the message carried, so it has to be ordered after the merged knowledge. Merging first and then ticking guarantees the receiver’s own entry ends up one higher than anything either clock knew. Ticking first can lose the event: in the test where the incoming clock is 4, 4 and the receiver is process 1 with clock 0, 0, ticking first gives 0, 1, and the max with 4, 4 then wipes out the tick, returning 4, 4 instead of 4, 5.
What is the difference between a vector clock and a Lamport clock?
A Lamport clock is a single counter per process. It guarantees that if event a caused event b, then a has the smaller timestamp, but the converse fails: a smaller timestamp does not prove causation, so Lamport clocks cannot tell causally related events from concurrent ones. A vector clock keeps one counter per process, so two clocks can be compared entry by entry, and when neither is less than or equal to the other everywhere, the events are concurrent. The price is size: N counters per clock instead of one.
How do vector clocks detect conflicts in a distributed database?
Each stored version carries the vector clock of the write that produced it. When two versions of a key meet, the database compares their clocks. If one clock is less than or equal to the other in every entry, that version is older and can be discarded. If neither dominates, the writes were concurrent: neither writer saw the other, so the database keeps both as siblings and lets the application or a merge rule resolve them. Amazon’s Dynamo paper describes this design, and CRDTs build on the same causality tracking.
This idea in other formats
Explore the topic
See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.
More Challenges
- Circuit BreakerStop one failing dependency from taking down the fleet: trip after consecutive failures, fail fast while open, probe once after the cooldown. Implement the closed → open → half-open state machine as a pure, testable replay. Solve it in Python or TypeScript.Read →
- Consistent Hashing RingHow distributed caches decide which node owns a key — with tiny churn when nodes join or leave. Build a hash ring with virtual nodes and route keys clockwise. A provided hash keeps Python and TypeScript in sync. Hidden tests.Read →
- Raft Leader Election (Majority)The heartbeat of the Raft consensus algorithm: a candidate becomes leader only by winning a strict majority of the cluster — the rule that guarantees at most one leader per term. Decide an election round. Solve it in Python or TypeScript, with hidden tests.Read →
- CRDT: Grow-Only CounterA counter many replicas increment independently, with no coordination, that always converges to the same total after syncing — a G-Counter, the simplest CRDT. Merge per-replica payloads by element-wise max. Solve it in Python or TypeScript, with hidden tests.Read →
- Course Schedule (Cycle Detection)Can you finish every course given its prerequisites? The classic "is this dependency graph acyclic?" check a build system runs. Detect a cycle with a topological sort. Solve it in Python or TypeScript, with hidden tests.Read →
- Word LadderTransform one word into another one letter at a time, every step a real word — a shortest path in a hidden graph, so a job for BFS. Return the shortest ladder length. Solve it in Python or TypeScript, with hidden tests.Read →