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.
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]- 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.
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.
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.
- 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.
Explore the topic
See this challenge alongside everything else on the same subject — handbooks, system designs, algorithms and tools, in one place.