System Design — Vector Clock Comparison

Wall clocks cannot order events on different machines. A vector clock can: each node keeps a
counter per node, and two clocks are compared entry by entry. It is how Dynamo-style stores
know whether two versions of a value are ordered or in conflict.

solve(a, b) — a and b are clocks, objects mapping a node name to a counter. A node missing
from a clock counts as 0. Return [relation, merged]:

• relation describes `a` relative to `b`:

- "equal" — every counter is the same;
- "before" — every counter of a is <= the one in b, and at least one is < (a happened before b);
- "after" — the mirror case (b happened before a);
- "concurrent" — each clock is ahead on at least one node: neither saw the other.

• merged — the element-wise maximum, as a list of [node, counter] pairs **sorted by node

name**, covering every node that appears in a or b (even with a counter of 0).

Examples

solve({A:1}, {A:2})                 → ["before", [["A",2]]]
solve({A:2,B:1}, {A:1,B:2})         → ["concurrent", [["A",2],["B",2]]]
solve({A:1,B:1}, {A:1})             → ["after", [["A",1],["B",1]]]