A vector clock is a map from each process in a distributed system to an integer event counter, used to decide whether one event happened before another or whether the two are concurrent. Real systems reach for them when there is no shared wall clock to trust: Amazon's Dynamo, Riak, and many collaborative editors stamp every update with a vector clock so a replica can later tell "this version is strictly newer" apart from "these two versions conflict." Your job is to build one.
You implement a factory vectorClocksLamport(nodeId) that returns a live clock for one process. It exposes tick (log a local event), receive (fold in a message from another process), get (read the current counters), and compare (relate this clock to another). Two pure helpers hang off the factory for working with raw states directly.
type Clock = Record<string, number>; // a missing key means 0
type Relation = 'equal' | 'before' | 'after' | 'concurrent';
function vectorClocksLamport(nodeId: string): {
tick(): Clock; // log a local event: bump your own counter
receive(other: Clock): Clock; // merge (elementwise max), then bump your own
get(): Clock; // a copy of the current counters
compare(other: Clock): Relation;
};
// Static-style helpers on the factory (pure functions over raw states):
vectorClocksLamport.merge; // (a: Clock, b: Clock) => Clock elementwise max
vectorClocksLamport.compareClocks; // (a: Clock, b: Clock) => Relationconst a = vectorClocksLamport('a');
const b = vectorClocksLamport('b');
a.tick(); // a logs an event -> { a: 1 }
const msg = a.tick(); // and another -> { a: 2 } (attach this to the message)
b.tick(); // b logs an event -> { b: 1 }
b.receive(msg); // max({ b: 1 }, { a: 2 }), then bump b -> { a: 2, b: 2 }vectorClocksLamport.compareClocks({ a: 2, b: 1 }, { a: 2, b: 2 });
// 'before' every counter is at most the other, and b is strictly less
vectorClocksLamport.compareClocks({ a: 1 }, { b: 1 });
// 'concurrent' a leads on its slot, b leads on its slot; neither dominatesreceive is max-then-tick. First take the elementwise maximum with the incoming state, then increment your own counter — receiving a message is itself a local event, so it advances your slot just like tick does.compare is a partial order. Return before when every one of this clock's counters is at most the other's and at least one is strictly less; after for the mirror image; equal when all counters match; and concurrent when each clock leads somewhere, so neither dominates.receive and compare take a raw clock object — the same shape get() returns — so a clock can be serialized and sent over the wire. Do not assume the argument is another factory instance.Date.now; every method is a plain synchronous computation.You'll build a per-process event counter that can look at two snapshots and say whether one truly came before the other — or whether they happened side by side, with no way to order them.
Three teammates edit a shared document offline. Each makes a few changes, then they reconnect and sync. Some edits clearly build on others — Bina fixed a typo that Ada had already written. But some were made in parallel: Ada and Cai both rewrote the intro without seeing each other's version. The first case has a natural order; the second is a genuine conflict.
You cannot settle this with a wall clock. Clocks drift, and "a later timestamp" does not mean "saw the earlier edit" — two machines can stamp concurrent edits in either order. What you need is a counter that tracks events and who has seen them, not seconds. A vector clock does exactly that: it counts events per process, and the counters themselves encode who knew what.
A vector clock is one integer per process. Your own slot counts the events you have generated. Every other slot records the latest event of that process you have heard about — directly, or passed along through someone else.
To relate two clocks, compare them slot by slot. If clock X is greater than or equal to clock Y in every slot and strictly greater in at least one, then everything Y knew, X also knew, and then some — X is after Y. If X trails everywhere, it is before. And if each clock leads in some slot the other trails, neither dominates: they are concurrent. That last verdict — "no order exists" — is the one a single number can never express.
The tempting shortcut is a Lamport scalar clock: track a single number instead of a whole vector. Bump it on every local event; on receive, catch up to the sender then bump.
function lamportScalar(nodeId) {
let time = 0;
return {
tick() {
return (time += 1); // a local event advances time by one
},
receive(theirTime) {
time = Math.max(time, theirTime) + 1; // catch up to the sender, then +1
return time;
},
};
}This is a real, useful clock — it guarantees that if event X causes event Y, then time(X) < time(Y). But the converse fails, and that is the whole problem. time(X) < time(Y) does not imply X caused Y. A single number is forced to lay every event out on one line, so it invents orderings that causality never established.
Read the picture through the scalar clock. The event on B and the event on C are each the first on their process, so both get scalar time 1 — equal numbers, and the scalar cannot tell "concurrent" from "the same moment." Worse, A's second event has scalar time 2 while C's event has 1, so the scalar reports 1 < 2 and calls C's event earlier than A's — even though A and C never exchanged a message. Keep a separate slot per process and the confusion evaporates: [0,0,1] and [2,0,0] are visibly incomparable, because each is ahead of the other in a different slot.
function vectorClocksLamport(nodeId) {
// The clock is a plain map: process id -> counter. A process we've never
// heard from is simply absent, which we read as 0 — we never store zeros.
const clock = {};
// A defensive copy, so callers can read (and even mutate) the result
// without reaching into our live state.
function get() {
return { ...clock };
}
// A local event bumps only our own slot.
function tick() {
clock[nodeId] = (clock[nodeId] || 0) + 1;
return get();
}
// Receiving a message does two things at once: we learn everything the
// sender knew (elementwise max), and the receive is itself a local event
// (so we bump our own slot afterwards).
function receive(other) {
const merged = merge(clock, other);
for (const id of Object.keys(merged)) {
clock[id] = merged[id];
}
clock[nodeId] = (clock[nodeId] || 0) + 1;
return get();
}
function compare(other) {
return compareClocks(clock, other);
}
return { tick, receive, get, compare };
}
// --- Pure operations over raw states: no instance, no side effects ---
// The join: for every process, keep the larger of the two counters. It is
// commutative, associative, and idempotent — the reason replicas converge.
function merge(a, b) {
const out = {};
for (const id of new Set([...Object.keys(a), ...Object.keys(b)])) {
out[id] = Math.max(a[id] || 0, b[id] || 0);
}
return out;
}
// Compare two clocks componentwise. We only need to know whether 'a' is ever
// ahead of 'b', and whether it is ever behind; the four verdicts fall out.
function compareClocks(a, b) {
let aAhead = false; // some slot where a > b
let aBehind = false; // some slot where a < b
for (const id of new Set([...Object.keys(a), ...Object.keys(b)])) {
const av = a[id] || 0;
const bv = b[id] || 0;
if (av > bv) aAhead = true;
else if (av < bv) aBehind = true;
}
if (aAhead && aBehind) return 'concurrent'; // each leads somewhere
if (aBehind) return 'before'; // a is at most b, and strictly less somewhere
if (aAhead) return 'after'; // a is at least b, and strictly greater somewhere
return 'equal'; // identical on every slot
}
// Expose the pure helpers as static-style methods on the factory.
vectorClocksLamport.merge = merge;
vectorClocksLamport.compareClocks = compareClocks;
module.exports = { vectorClocksLamport };The design splits cleanly into two halves. merge and compareClocks are pure functions over raw states — no instance, no mutation — and they are the mathematical core. The factory is a thin stateful wrapper: receive is literally merge followed by a self-tick, and compare is just compareClocks bound to the live clock. Three details earn their lines.
receive is max-then-tick. Taking the elementwise maximum folds in everything the sender knew without ever lowering a counter you already hold. Then — because receiving a message is itself an event on your timeline — you bump your own slot. Skip the max and you lose the sender's history; skip the tick and two distinct receive events collapse to the same clock.
The four-way compare from two booleans. You never need to know how far ahead or behind — only whether this clock is ever ahead and whether it is ever behind. Ahead-and-behind is concurrent; behind-only is before; ahead-only is after; neither is equal. Iterating the union of both key sets, with a missing slot read as 0, is what makes { a: 2 } and { a: 2, b: 1 } compare correctly instead of ignoring b.
Absent means zero, and stays that way. tick and receive only ever write values that are at least 1, so the map stays sparse. Reading clock[id] || 0 everywhere means an absent slot behaves exactly like a zero one — without you having to seed every process's counter up front.
Take replica B, which has already logged two of its own events and earlier heard A's first event — so its clock is { a: 1, b: 2 }. A message now arrives from A carrying the state { a: 3, c: 1 }. Run b.receive({ a: 3, c: 1 }):
merge step (elementwise max, union of a,b,c)
a: max(1, 3) = 3
b: max(2, 0) = 2 <- incoming had no b, read as 0; we keep our larger 2
c: max(0, 1) = 1
-> { a: 3, b: 2, c: 1 }
tick own slot (b)
b: 2 + 1 = 3
-> { a: 3, b: 3, c: 1 }
Now compare B's old state against its new one:
compareClocks({ a: 1, b: 2 }, { a: 3, b: 3, c: 1 })
a: 1 < 3 -> behind
b: 2 < 3 -> behind
c: 0 < 1 -> behind
aAhead = false, aBehind = true -> 'before'
The old clock is before the new one — the receive event causally follows everything B previously knew, exactly as it should. Contrast two replicas that never talked: compareClocks({ a: 1 }, { b: 1 }) finds a ahead on its slot and behind on b, so it returns concurrent.
receive. Writing clock[id] += other[id] double-counts shared history — the same event gets tallied on every hop it travels. Fix: take the maximum, which is idempotent, so re-receiving a duplicate message changes nothing.receive. If receive only merges, two separate receives on the same node produce identical clocks and wrongly compare equal. The receive is an event; bump your slot after the merge.{ a: 2 } with { a: 2, b: 1 } by looping only the left clock's keys skips b and reports equal. Union both key sets and read an absent counter as 0.before and after. before means this clock is the dominated one — every slot at most the other's. Anchor it to the sentence "this event happened before the other," and the direction stops flipping.0 for a process you have only mentioned makes two logically-equal clocks look different to a deep-equality check like toEqual. Keep the map sparse — absent already means zero.O(1) space, and a real total order, but blind to concurrency. When you only need some consistent order (say, totally-ordered multicast), break ties deterministically by pairing the count with the node id and comparing (time, nodeId) lexicographically — the same tiebreak that makes last-writer-wins registers deterministic.O(N) counters per clock hurts when membership churns. Production systems prune entries for retired nodes or cap the set of tracked replicas, trading a little precision for a bounded clock.Keep practising the same patterns with a nearby challenge.
No submissions yet
Share your approach and start the discussion.
A vector clock is a map from each process in a distributed system to an integer event counter, used to decide whether one event happened before another or whether the two are concurrent. Real systems reach for them when there is no shared wall clock to trust: Amazon's Dynamo, Riak, and many collaborative editors stamp every update with a vector clock so a replica can later tell "this version is strictly newer" apart from "these two versions conflict." Your job is to build one.
You implement a factory vectorClocksLamport(nodeId) that returns a live clock for one process. It exposes tick (log a local event), receive (fold in a message from another process), get (read the current counters), and compare (relate this clock to another). Two pure helpers hang off the factory for working with raw states directly.
type Clock = Record<string, number>; // a missing key means 0
type Relation = 'equal' | 'before' | 'after' | 'concurrent';
function vectorClocksLamport(nodeId: string): {
tick(): Clock; // log a local event: bump your own counter
receive(other: Clock): Clock; // merge (elementwise max), then bump your own
get(): Clock; // a copy of the current counters
compare(other: Clock): Relation;
};
// Static-style helpers on the factory (pure functions over raw states):
vectorClocksLamport.merge; // (a: Clock, b: Clock) => Clock elementwise max
vectorClocksLamport.compareClocks; // (a: Clock, b: Clock) => Relationconst a = vectorClocksLamport('a');
const b = vectorClocksLamport('b');
a.tick(); // a logs an event -> { a: 1 }
const msg = a.tick(); // and another -> { a: 2 } (attach this to the message)
b.tick(); // b logs an event -> { b: 1 }
b.receive(msg); // max({ b: 1 }, { a: 2 }), then bump b -> { a: 2, b: 2 }vectorClocksLamport.compareClocks({ a: 2, b: 1 }, { a: 2, b: 2 });
// 'before' every counter is at most the other, and b is strictly less
vectorClocksLamport.compareClocks({ a: 1 }, { b: 1 });
// 'concurrent' a leads on its slot, b leads on its slot; neither dominatesreceive is max-then-tick. First take the elementwise maximum with the incoming state, then increment your own counter — receiving a message is itself a local event, so it advances your slot just like tick does.compare is a partial order. Return before when every one of this clock's counters is at most the other's and at least one is strictly less; after for the mirror image; equal when all counters match; and concurrent when each clock leads somewhere, so neither dominates.receive and compare take a raw clock object — the same shape get() returns — so a clock can be serialized and sent over the wire. Do not assume the argument is another factory instance.Date.now; every method is a plain synchronous computation.You'll build a per-process event counter that can look at two snapshots and say whether one truly came before the other — or whether they happened side by side, with no way to order them.
Three teammates edit a shared document offline. Each makes a few changes, then they reconnect and sync. Some edits clearly build on others — Bina fixed a typo that Ada had already written. But some were made in parallel: Ada and Cai both rewrote the intro without seeing each other's version. The first case has a natural order; the second is a genuine conflict.
You cannot settle this with a wall clock. Clocks drift, and "a later timestamp" does not mean "saw the earlier edit" — two machines can stamp concurrent edits in either order. What you need is a counter that tracks events and who has seen them, not seconds. A vector clock does exactly that: it counts events per process, and the counters themselves encode who knew what.
A vector clock is one integer per process. Your own slot counts the events you have generated. Every other slot records the latest event of that process you have heard about — directly, or passed along through someone else.
To relate two clocks, compare them slot by slot. If clock X is greater than or equal to clock Y in every slot and strictly greater in at least one, then everything Y knew, X also knew, and then some — X is after Y. If X trails everywhere, it is before. And if each clock leads in some slot the other trails, neither dominates: they are concurrent. That last verdict — "no order exists" — is the one a single number can never express.
The tempting shortcut is a Lamport scalar clock: track a single number instead of a whole vector. Bump it on every local event; on receive, catch up to the sender then bump.
function lamportScalar(nodeId) {
let time = 0;
return {
tick() {
return (time += 1); // a local event advances time by one
},
receive(theirTime) {
time = Math.max(time, theirTime) + 1; // catch up to the sender, then +1
return time;
},
};
}This is a real, useful clock — it guarantees that if event X causes event Y, then time(X) < time(Y). But the converse fails, and that is the whole problem. time(X) < time(Y) does not imply X caused Y. A single number is forced to lay every event out on one line, so it invents orderings that causality never established.
Read the picture through the scalar clock. The event on B and the event on C are each the first on their process, so both get scalar time 1 — equal numbers, and the scalar cannot tell "concurrent" from "the same moment." Worse, A's second event has scalar time 2 while C's event has 1, so the scalar reports 1 < 2 and calls C's event earlier than A's — even though A and C never exchanged a message. Keep a separate slot per process and the confusion evaporates: [0,0,1] and [2,0,0] are visibly incomparable, because each is ahead of the other in a different slot.
function vectorClocksLamport(nodeId) {
// The clock is a plain map: process id -> counter. A process we've never
// heard from is simply absent, which we read as 0 — we never store zeros.
const clock = {};
// A defensive copy, so callers can read (and even mutate) the result
// without reaching into our live state.
function get() {
return { ...clock };
}
// A local event bumps only our own slot.
function tick() {
clock[nodeId] = (clock[nodeId] || 0) + 1;
return get();
}
// Receiving a message does two things at once: we learn everything the
// sender knew (elementwise max), and the receive is itself a local event
// (so we bump our own slot afterwards).
function receive(other) {
const merged = merge(clock, other);
for (const id of Object.keys(merged)) {
clock[id] = merged[id];
}
clock[nodeId] = (clock[nodeId] || 0) + 1;
return get();
}
function compare(other) {
return compareClocks(clock, other);
}
return { tick, receive, get, compare };
}
// --- Pure operations over raw states: no instance, no side effects ---
// The join: for every process, keep the larger of the two counters. It is
// commutative, associative, and idempotent — the reason replicas converge.
function merge(a, b) {
const out = {};
for (const id of new Set([...Object.keys(a), ...Object.keys(b)])) {
out[id] = Math.max(a[id] || 0, b[id] || 0);
}
return out;
}
// Compare two clocks componentwise. We only need to know whether 'a' is ever
// ahead of 'b', and whether it is ever behind; the four verdicts fall out.
function compareClocks(a, b) {
let aAhead = false; // some slot where a > b
let aBehind = false; // some slot where a < b
for (const id of new Set([...Object.keys(a), ...Object.keys(b)])) {
const av = a[id] || 0;
const bv = b[id] || 0;
if (av > bv) aAhead = true;
else if (av < bv) aBehind = true;
}
if (aAhead && aBehind) return 'concurrent'; // each leads somewhere
if (aBehind) return 'before'; // a is at most b, and strictly less somewhere
if (aAhead) return 'after'; // a is at least b, and strictly greater somewhere
return 'equal'; // identical on every slot
}
// Expose the pure helpers as static-style methods on the factory.
vectorClocksLamport.merge = merge;
vectorClocksLamport.compareClocks = compareClocks;
module.exports = { vectorClocksLamport };The design splits cleanly into two halves. merge and compareClocks are pure functions over raw states — no instance, no mutation — and they are the mathematical core. The factory is a thin stateful wrapper: receive is literally merge followed by a self-tick, and compare is just compareClocks bound to the live clock. Three details earn their lines.
receive is max-then-tick. Taking the elementwise maximum folds in everything the sender knew without ever lowering a counter you already hold. Then — because receiving a message is itself an event on your timeline — you bump your own slot. Skip the max and you lose the sender's history; skip the tick and two distinct receive events collapse to the same clock.
The four-way compare from two booleans. You never need to know how far ahead or behind — only whether this clock is ever ahead and whether it is ever behind. Ahead-and-behind is concurrent; behind-only is before; ahead-only is after; neither is equal. Iterating the union of both key sets, with a missing slot read as 0, is what makes { a: 2 } and { a: 2, b: 1 } compare correctly instead of ignoring b.
Absent means zero, and stays that way. tick and receive only ever write values that are at least 1, so the map stays sparse. Reading clock[id] || 0 everywhere means an absent slot behaves exactly like a zero one — without you having to seed every process's counter up front.
Take replica B, which has already logged two of its own events and earlier heard A's first event — so its clock is { a: 1, b: 2 }. A message now arrives from A carrying the state { a: 3, c: 1 }. Run b.receive({ a: 3, c: 1 }):
merge step (elementwise max, union of a,b,c)
a: max(1, 3) = 3
b: max(2, 0) = 2 <- incoming had no b, read as 0; we keep our larger 2
c: max(0, 1) = 1
-> { a: 3, b: 2, c: 1 }
tick own slot (b)
b: 2 + 1 = 3
-> { a: 3, b: 3, c: 1 }
Now compare B's old state against its new one:
compareClocks({ a: 1, b: 2 }, { a: 3, b: 3, c: 1 })
a: 1 < 3 -> behind
b: 2 < 3 -> behind
c: 0 < 1 -> behind
aAhead = false, aBehind = true -> 'before'
The old clock is before the new one — the receive event causally follows everything B previously knew, exactly as it should. Contrast two replicas that never talked: compareClocks({ a: 1 }, { b: 1 }) finds a ahead on its slot and behind on b, so it returns concurrent.
receive. Writing clock[id] += other[id] double-counts shared history — the same event gets tallied on every hop it travels. Fix: take the maximum, which is idempotent, so re-receiving a duplicate message changes nothing.receive. If receive only merges, two separate receives on the same node produce identical clocks and wrongly compare equal. The receive is an event; bump your slot after the merge.{ a: 2 } with { a: 2, b: 1 } by looping only the left clock's keys skips b and reports equal. Union both key sets and read an absent counter as 0.before and after. before means this clock is the dominated one — every slot at most the other's. Anchor it to the sentence "this event happened before the other," and the direction stops flipping.0 for a process you have only mentioned makes two logically-equal clocks look different to a deep-equality check like toEqual. Keep the map sparse — absent already means zero.O(1) space, and a real total order, but blind to concurrency. When you only need some consistent order (say, totally-ordered multicast), break ties deterministically by pairing the count with the node id and comparing (time, nodeId) lexicographically — the same tiebreak that makes last-writer-wins registers deterministic.O(N) counters per clock hurts when membership churns. Production systems prune entries for retired nodes or cap the set of tracked replicas, trading a little precision for a bounded clock.Keep practising the same patterns with a nearby challenge.
No submissions yet
Share your approach and start the discussion.