Vector Clocks

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.

Signature

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) => Relation

Examples

const 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 dominates

Notes

• Missing means zero. A process you have never heard from has counter 0. Store only the counters you have actually touched, and treat any absent slot as 0 when you read, merge, or compare.
• receive 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.
• States travel, not instances. 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.
• Pure and synchronous. The "clock" counts events, not seconds. There are no timers and no Date.now; every method is a plain synchronous computation.