This task hides six distinct failure modes. Naive implementations almost always get one of them wrong.
This task hides six distinct failure modes. Naive implementations almost always get one of them wrong.
A. Bit-packing a 64-bit timestamp in JS numbers.
(l << 16) | c with a 48-bit l exceeds Number.MAX_SAFE_INTEGER, so the low bits are silently truncated and timestamps lose ordering. The entire clock must use BigInt, and serialization must be an explicit 16-hex-digit encoding.
B. Wall clock regression (NTP correction).
The original algorithm's l = max(l_prev, pt) is necessary but not sufficient if you derive the return value from raw pt. The correct rule is: physical component never goes below the previous physical component; when the physical value does not advance, increment the logical counter; when the counter overflows the 16-bit field, promote into the physical field. A final lastEmitted guard makes it impossible to return a value <= a previously returned one.
C. Untrusted remote timestamps (drift).
A peer whose clock is minutes ahead can drag this node's clock forward ("clock poisoning"). The fix is to clamp the remote physical component to pt + maxDrift before merging. Crucially, clamping is still monotonic-safe because the merge takes max(previous, clamped_remote, pt) and the lastEmitted guard sits on top.
D. Exactly-once causal delivery.
Each node tracks a seen set (transport-level dedup) and a delivered set (application-level). A broadcast carries its full causal past as deps; a message is delivered only when every deps id is in delivered. Duplicate arrivals are dropped by seen.
E. The subtle killer: clamping breaks timestamp causality, so "wait for the global minimum" deadlocks.
This is the bug the random simulator exposed at seed 17 (n1 dep n2:39 ts !< n1:37 ts). When a remote timestamp is clamped, a dependency can carry a larger packed timestamp than the message that causally depends on it. A flush strategy that only delivers when the globally smallest buffered message is ready will block forever on the dependent (smaller ts, not ready) and never deliver the dependency (larger ts, ready). The fix is to choose the smallest timestamp among the ready set only. Causality is enforced by deps, not by the timestamp key; the timestamp key is only a deterministic tie-break.
F. Deterministic flush order.
Use the total key (packed_ts, origin, seq). Every node computes the same key, so concurrent ready messages flush in an identical order.
Five files. hlc.js and causal.js are the implementation; network.js, simulate.js, test.js are the verification harness.
hlc.js'use strict';
/*
* Hybrid Logical Clock (HLC)
* [ 48-bit physical milliseconds ][ 16-bit logical counter ]
* All arithmetic is BigInt: the packed 64-bit value is not representable
* as a JS number.
*/
const LOG_BITS = 16n;
const MAX_LOG = (1n << LOG_BITS) - 1n; // 0xFFFF
const MAX_PHYS = (1n << 48n) - 1n; // 2^48 - 1
const MAX_PACKED = (1n << 64n) - 1n;
function pack(l, c) {
if (l < 0n || l > MAX_PHYS) throw new RangeError(`physical ${l} out of 48-bit range`);
if (c < 0n || c > MAX_LOG) throw new RangeError(`logical ${c} out of 16-bit range`);
return (l << LOG_BITS) | c;
}
function unpack(p) {
if (typeof p !== 'bigint') p = BigInt(p);
if (p < 0n || p > MAX_PACKED) throw new RangeError('packed timestamp out of 64-bit range');
return { l: p >> LOG_BITS, c: p & MAX_LOG };
}
function serialize(p) {
if (typeof p !== 'bigint') p = BigInt(p);
if (p < 0n || p > MAX_PACKED) throw new RangeError('packed timestamp out of 64-bit range');
return p.toString(16).padStart(16, '0');
}
function deserialize(hex) {
if (typeof hex !== 'string' || !/^[0-9a-fA-F]{16}$/.test(hex)) {
throw new RangeError(`invalid serialized timestamp: ${hex}`);
}
return BigInt('0x' + hex);
}
const systemNow = () => BigInt(Date.now());
class HLC {
constructor(opts = {}) {
this.now = opts.now || systemNow;
this.maxDrift = BigInt(opts.maxDrift == null ? 60_000 : opts.maxDrift);
this.nodeId = opts.nodeId || 'node';
this.l = 0n; // physical component
this.c = 0n; // logical component
this.lastEmitted = null; // packed value; hard monotonicity guard
}
/** Timestamp for a local event / send; strictly greater than any previous. */
issue() {
const pt = this.now();
const lPrev = this.l;
let l = pt > lPrev ? pt : lPrev;
let c = l === lPrev ? this.c + 1n : 0n;
return this._commit(l, c);
}
/**
* Observe a remote timestamp. A remote physical time beyond
* now()+maxDrift is clamped. Clamping is monotonic-safe: we still take
* the max with local state and the previous emitted value.
*/
observe(remotePacked) {
const { l: ml0, c: mc0 } = unpack(remotePacked);
const pt = this.now();
// --- drift guard ---
const maxAllowed = pt + this.maxDrift < MAX_PHYS ? pt + this.maxDrift : MAX_PHYS;
let ml = ml0;
let mc = mc0;
if (ml > maxAllowed) {
ml = maxAllowed;
mc = 0n;
}
// --- HLC merge ---
const lPrev = this.l;
const cPrev = this.c;
const localMax = lPrev > pt ? lPrev : pt;
const l = localMax > ml ? localMax : ml;
let c;
if (l === lPrev && l === ml) c = (cPrev > mc ? cPrev : mc) + 1n;
else if (l === lPrev) c = cPrev + 1n;
else if (l === ml) c = mc + 1n;
else c = 0n;
return this._commit(l, c);
}
/** Overflow promotion + absolute monotonicity safety net. */
_commit(l, c) {
if (c > MAX_LOG) { // 16-bit counter overflow -> physical
l += 1n;
c = 0n;
}
if (l > MAX_PHYS) throw new RangeError('physical clock exhausted 48-bit space');
let packed = pack(l, c);
if (this.lastEmitted !== null && packed <= this.lastEmitted) {
const base = unpack(this.lastEmitted);
l = base.l;
c = base.c + 1n;
if (c > MAX_LOG) { l += 1n; c = 0n; }
packed = pack(l, c);
}
this.l = l;
this.c = c;
this.lastEmitted = packed;
return packed;
}
peek() {
return this.lastEmitted;
}
}
module.exports = { HLC, pack, unpack, serialize, deserialize, LOG_BITS, MAX_LOG, MAX_PHYS, MAX_PACKED };
causal.js'use strict';
const { HLC } = require('./hlc');
/**
* Deterministic total order for *ready* messages. NOT a causal order once
* remote timestamps are drift-clamped; causality is enforced by `deps`.
*/
function compareMessages(a, b) {
if (a.ts !== b.ts) return a.ts < b.ts ? -1 : 1;
if (a.origin !== b.origin) return a.origin < b.origin ? -1 : 1;
if (a.seq !== b.seq) return a.seq < b.seq ? -1 : 1;
return 0;
}
class CausalNode {
constructor(id, opts = {}) {
this.id = id;
this.hlc = new HLC({ ...opts, nodeId: id });
this.seq = 0n;
this.delivered = new Set(); // fully delivered ids (dedup + readiness)
this.seen = new Set(); // received ids incl. buffered (transport dedup)
this.buffer = new Map(); // id -> message waiting on dependencies
this.deliveries = []; // messages in delivery order
this.onDeliver = opts.onDeliver || null;
}
/** Dependency set = the sender's entire causal past. */
broadcast(payload) {
const msg = {
id: `${this.id}:${this.seq}`,
origin: this.id,
seq: this.seq,
ts: this.hlc.issue(),
deps: new Set(this.delivered),
payload,
};
this.seq += 1n;
return msg;
}
receive(msg) {
if (this.seen.has(msg.id)) return []; // duplicate -> exactly-once
this.seen.add(msg.id);
this.hlc.observe(msg.ts); // keep local clock ahead of what we observed
this.buffer.set(msg.id, msg);
return this._flush();
}
_ready(msg) {
for (const d of msg.deps) if (!this.delivered.has(d)) return false;
return true;
}
/**
* Deliver the smallest timestamp among the READY messages only.
* Waiting for the globally smallest buffered message can deadlock:
* a clamped dependency may have a larger ts than its dependent.
*/
_flush() {
const out = [];
for (;;) {
let min = null;
for (const m of this.buffer.values()) {
if (!this._ready(m)) continue;
if (min === null || compareMessages(m, min) < 0) min = m;
}
if (min === null) break;
this.buffer.delete(min.id);
this.delivered.add(min.id);
this.deliveries.push(min);
if (this.onDeliver) this.onDeliver(this, min);
out.push(min);
}
return out;
}
get pendingCount() {
return this.buffer.size;
}
}
module.exports = { CausalNode, compareMessages };
network.js'use strict';
const { CausalNode } = require('./causal');
/** Deterministic PRNG so failures reproduce from a seed. */
function mulberry32(seed) {
let a = seed >>> 0;
return function () {
a |= 0;
a = (a + 0x6d2b79f5) | 0;
let t = Math.imul(a ^ (a >>> 15), 1 | a);
t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t;
return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
};
}
/** Lossy network: delays, drops+retransmit, duplicates, dynamic partitions. */
class Network {
constructor(rng, nodes) {
this.rng = rng;
this.nodes = nodes;
this.time = 0;
this.packets = [];
this.partitioned = [];
this.metrics = { sent: 0, dropped: 0, duplicated: 0, delivered: 0 };
}
partition(a, b, duration) {
this.partitioned.push({ a, b, until: this.time + duration });
if (a !== b) this.partitioned.push({ a: b, b: a, until: this.time + duration });
}
isBlocked(a, b) {
for (const p of this.partitioned) {
if (p.a === a && p.b === b && p.until > this.time) return true;
}
return false;
}
transmit(msg, to) {
this.metrics.sent++;
if (this.rng() < 0.30) { this.metrics.dropped++; return; }
const delay = 1 + Math.floor(this.rng() * 25);
this.packets.push({ msg, to, at: this.time + delay });
if (this.rng() < 0.20) { // duplicate
this.metrics.duplicated++;
this.packets.push({ msg, to, at: this.time + 1 + Math.floor(this.rng() * 25) });
}
}
advanceTo(t) {
this.time = t;
const due = [], rest = [];
for (const p of this.packets) (p.at <= t ? due : rest).push(p);
this.packets = rest;
for (const p of due.slice().sort((x, y) => x.at - y.at)) {
if (this.isBlocked(p.msg.origin, p.to)) {
this.packets.push({ msg: p.msg, to: p.to, at: t + 1 + Math.floor(this.rng() * 5) });
continue;
}
const dest = this.nodes.find((n) => n.id === p.to);
if (dest.seen.has(p.msg.id)) continue; // duplicate
this.metrics.delivered++;
dest.receive(p.msg);
}
}
/** Reliable-broadcast maintenance: retransmit until the peer has seen it. */
retransmit(outbox) {
for (const msg of outbox) {
for (const n of this.nodes) {
if (n.id === msg.origin) continue;
if (n.seen.has(msg.id)) continue;
if (this.rng() < 0.6) this.transmit(msg, n.id);
}
}
}
}
module.exports = { mulberry32, Network };
simulate.js'use strict';
const assert = require('assert');
const { CausalNode } = require('./causal');
const { mulberry32, Network } = require('./network');
function randInt(rng, lo, hi) {
return lo + Math.floor(rng() * (hi - lo + 1));
}
function runSimulation(seed, opts = {}) {
const { numNodes = 4, ticks = 400, broadcastProb = 0.18, maxDrift = 5_000n, drainCap = 20_000 } = opts;
const rng = mulberry32(seed);
const nodes = [];
const clocks = [];
for (let i = 0; i < numNodes; i++) {
const clock = { t: BigInt(1_000_000 + i * 7) };
clocks.push(clock);
const node = new CausalNode(`n${i}`, { maxDrift, now: () => clock.t });
// independent per-node emitted-timestamp monotonicity check
node._lastEmit = null;
const trackEmit = (ts) => {
if (node._lastEmit !== null) {
assert(ts > node._lastEmit,
`seed ${seed}: ${node.id} emitted non-monotonic timestamp ${ts} <= ${node._lastEmit}`);
}
node._lastEmit = ts;
};
const origIssue = node.hlc.issue.bind(node.hlc);
node.hlc.issue = () => { const t = origIssue(); trackEmit(t); return t; };
const origObserve = node.hlc.observe.bind(node.hlc);
node.hlc.observe = (p) => { const t = origObserve(p); trackEmit(t); return t; };
// independent causal invariant at delivery time
node.onDeliver = (nd, m) => {
for (const d of m.deps) {
assert(nd.delivered.has(d), `seed ${seed}: ${nd.id} delivered ${m.id} before dep ${d}`);
}
};
nodes.push(node);
}
const net = new Network(rng, nodes);
const outbox = [];
const allMessages = [];
const stepClocks = () => {
for (const clock of clocks) {
clock.t += BigInt(randInt(rng, 0, 2));
if (rng() < 0.04) { // simulated NTP correction: backwards jump
const back = BigInt(randInt(rng, 1, 800));
clock.t = clock.t > back ? clock.t - back : 0n;
}
}
};
for (let tick = 0; tick < ticks; tick++) {
net.time = tick;
if (rng() < 0.04) {
const a = nodes[randInt(rng, 0, numNodes - 1)].id;
const b = nodes[randInt(rng, 0, numNodes - 1)].id;
net.partition(a, b, randInt(rng, 5, 40));
}
stepClocks();
for (const node of nodes) {
if (rng() < broadcastProb) {
const msg = node.broadcast({ from: node.id, tick });
outbox.push(msg);
allMessages.push(msg);
node.receive(msg); // self-delivery
}
}
net.retransmit(outbox);
net.advanceTo(tick);
}
// Drain until every node has delivered everything.
let extra = 0;
while (extra < drainCap) {
net.time = ticks + extra;
stepClocks();
net.retransmit(outbox);
net.advanceTo(ticks + extra);
const done = nodes.every((n) => allMessages.every((m) => n.delivered.has(m.id)));
if (done) break;
extra++;
}
// ---- property assertions ----
const ids = allMessages.map((m) => m.id);
assert.strictEqual(new Set(ids).size, ids.length, `seed ${seed}: duplicate message ids generated`);
for (const node of nodes) {
assert.strictEqual(node.delivered.size, node.deliveries.length,
`seed ${seed}: ${node.id} delivered a message twice`);
const deliveredIds = node.deliveries.map((m) => m.id);
assert.strictEqual(new Set(deliveredIds).size, deliveredIds.length,
`seed ${seed}: ${node.id} delivered set has duplicates`);
assert.strictEqual(deliveredIds.length, allMessages.length,
`seed ${seed}: ${node.id} missing deliveries (${deliveredIds.length}/${allMessages.length}), pending=${node.pendingCount}`);
assert.strictEqual(node.pendingCount, 0, `seed ${seed}: ${node.id} still has buffered messages`);
assert.ok(node.hlc.lastEmitted !== null, `seed ${seed}: ${node.id} never emitted`);
}
return {
seed,
messages: allMessages.length,
deliveries: nodes.reduce((s, n) => s + n.deliveries.length, 0),
net: net.metrics,
};
}
function runProperties({ cases = 200, startSeed = 1 } = {}) {
let messages = 0, deliveries = 0, dropped = 0, duplicated = 0;
for (let i = 0; i < cases; i++) {
const seed = startSeed + i;
const r = runSimulation(seed, { numNodes: 2 + (seed % 5), ticks: 250 + (seed % 200) });
messages += r.messages;
deliveries += r.deliveries;
dropped += r.net.dropped;
duplicated += r.net.duplicated;
}
return { cases, messages, deliveries, dropped, duplicated };
}
module.exports = { runSimulation, runProperties };
if (require.main === module) {
const cases = Number(process.argv[2] || 200);
const start = Date.now();
const s = runProperties({ cases });
console.log(`PASS ${s.cases} random simulations in ${Date.now() - start}ms`);
console.log(` messages=${s.messages} deliveries=${s.deliveries} ` +
`packets_dropped=${s.dropped} packets_duplicated=${s.duplicated}`);
}
test.js'use strict';
const assert = require('assert');
const { HLC, pack, unpack, serialize, deserialize, MAX_LOG, MAX_PHYS } = require('./hlc');
const { runProperties } = require('./simulate');
let passed = 0;
function test(name, fn) {
try { fn(); passed++; console.log(` ok ${name}`); }
catch (e) { console.error(`FAIL ${name}\n ${e.message}`); process.exitCode = 1; }
}
console.log('HLC unit tests');
test('pack/unpack round-trips 48-bit physical + 16-bit logical', () => {
for (const [l, c] of [[0n, 0n], [1n, 0n], [123456789012345n, 65535n], [MAX_PHYS, MAX_LOG]]) {
const u = unpack(pack(l, c));
assert.strictEqual(u.l, l);
assert.strictEqual(u.c, c);
}
});
test('serialize/deserialize round-trips through hex', () => {
const ts = pack(1_700_000_000_000n, 42n);
const hex = serialize(ts);
assert.strictEqual(hex.length, 16);
assert.strictEqual(deserialize(hex), ts);
});
test('strictly monotonic when wall clock jumps backwards (NTP)', () => {
const seq = [1000n, 1000n, 1001n, 500n, 400n, 500n, 1200n, 1100n];
let i = 0;
const clk = new HLC({ now: () => seq[Math.min(i++, seq.length - 1)], maxDrift: 10_000n });
let prev = null;
for (let k = 0; k < 30; k++) {
const ts = clk.issue();
if (prev !== null) assert.ok(ts > prev, `timestamp regressed: ${ts} <= ${prev}`);
prev = ts;
}
});
test('logical counter increments within the same millisecond', () => {
const clk = new HLC({ now: () => 5000n });
const a = clk.issue();
const b = clk.issue();
assert.strictEqual(b - a, 1n);
assert.strictEqual(unpack(a).l, 5000n);
assert.strictEqual(unpack(b).c, 1n);
});
test('counter overflow promotes into the physical field monotonically', () => {
const clk = new HLC({ now: () => 100n });
clk.l = 100n; clk.c = MAX_LOG;
const a = clk.issue();
const ua = unpack(a);
assert.strictEqual(ua.l, 101n);
assert.strictEqual(ua.c, 0n);
assert.ok(a > pack(100n, MAX_LOG));
});
test('remote timestamp beyond max drift is clamped, clock stays monotonic', () => {
const clk = new HLC({ now: () => 10_000n, maxDrift: 1_000n });
const before = clk.issue();
const after = clk.observe(pack(11_000_000n, 5n));
assert.ok(after > before);
assert.ok(unpack(after).l <= 11_000n);
assert.ok(unpack(after).l >= 10_000n);
});
test('a malicious far-future timestamp cannot poison subsequent local emissions', () => {
const clk = new HLC({ now: () => 10_000n, maxDrift: 500n });
const seen = [clk.issue(), clk.observe(pack(MAX_PHYS, MAX_LOG))];
for (let i = 0; i < 100; i++) seen.push(clk.issue());
for (let i = 1; i < seen.length; i++) assert.ok(seen[i] > seen[i - 1]);
assert.ok(unpack(seen[seen.length - 1]).l <= 10_500n);
});
test('observe of a legitimate remote timestamp advances past it', () => {
const clk = new HLC({ now: () => 2_000n, maxDrift: 60_000n });
const remote = pack(2_500n, 3n);
assert.ok(clk.observe(remote) > remote);
});
test('deserialize rejects malformed input', () => {
assert.throws(() => deserialize('xyz'), RangeError);
assert.throws(() => deserialize('1234'), RangeError);
assert.throws(() => deserialize(42), RangeError);
});
test('clamped dependency (larger ts) is still delivered before its dependent', () => {
const { CausalNode } = require('./causal');
const A = new CausalNode('A', { now: () => 10_000n, maxDrift: 1_000n });
const B = new CausalNode('B', { now: () => 1_000_000n, maxDrift: 1_000n });
const C = new CausalNode('C', { now: () => 10_000n, maxDrift: 1_000n });
const mB = B.broadcast({ v: 'B' }); B.receive(mB);
A.receive(mB); // clamps mB at A
assert.ok(mB.ts > A.hlc.lastEmitted);
const mA = A.broadcast({ v: 'A' }); A.receive(mA); // depends on mB, smaller ts
assert.deepStrictEqual(C.receive(mA), []); // buffers
assert.strictEqual(C.pendingCount, 1);
const out = C.receive(mB);
assert.deepStrictEqual(out.map((m) => m.id), [mB.id, mA.id]); // dep first, no deadlock
assert.strictEqual(C.pendingCount, 0);
});
console.log('\nProperty-based network simulations');
test('random partitions/delays/drops/duplicates/reordering preserve all invariants', () => {
const r = runProperties({ cases: 250 });
assert.ok(r.deliveries > 0 && r.dropped > 0 && r.duplicated > 0);
console.log(` cases=${r.cases} messages=${r.messages} deliveries=${r.deliveries} dropped=${r.dropped} dup=${r.duplicated}`);
});
console.log(`\n${passed} checks passed${process.exitCode ? ' (with failures)' : ''}`);
Run the unit + property suite:
node test.js
Observed output:
HLC unit tests
ok pack/unpack round-trips 48-bit physical + 16-bit logical
ok serialize/deserialize round-trips through hex
ok strictly monotonic when wall clock jumps backwards (NTP)
ok logical counter increments within the same millisecond
ok counter overflow promotes into the physical field monotonically
ok remote timestamp beyond max drift is clamped, clock stays monotonic
ok a malicious far-future timestamp cannot poison subsequent local emissions
ok observe of a legitimate remote timestamp advances past it
ok deserialize rejects malformed input
ok clamped dependency (larger ts) is still delivered before its dependent
Property-based network simulations
cases=250 messages=60155 deliveries=270923 dropped=418612 dup=195123
ok random partitions/delays/drops/duplicates/reordering preserve all invariants
11 checks passed
Extended random campaign (2000 seeds, executable standalone):
node simulate.js 2000
PASS 2000 random simulations in 46113ms
messages=504601 deliveries=2272424 packets_dropped=3524571 packets_duplicated=1642525
For every seed and every node, with 2–6 nodes, backwards NTP steps, random partitions, ~30% packet drop with retransmission, ~20% duplication, and reordering:
delivered.size === deliveries.length and no duplicate ids in the delivery stream.issue()/observe() return is strictly greater than the node's previous return.deps is already in that node's delivered set.Before the _flush fix, seed 17 failed with:
seed 17: n1 dep n2:39 ts !< n1:37 ts
i.e. a drift-clamped dependency carried a larger packed timestamp than its dependent. The original "wait for the globally smallest buffered message" loop blocked on the smaller-ts, not-yet-ready dependent and never delivered the larger-ts, ready dependency. Switching to "smallest among the ready set" resolves it while preserving both causality and deterministic flush order.
const { CausalNode } = require('./causal');
const a = new CausalNode('a', { maxDrift: 60_000n });
const b = new CausalNode('b', { maxDrift: 60_000n });
const m1 = a.broadcast({ hello: 'world' });
a.receive(m1); // self-delivery
b.receive(m1); // delivers immediately (no deps)
const m2 = a.broadcast({ reply: 'hi' }); // deps = {m1}
a.receive(m2);
b.receive(m2); // delivers after m2's deps are present
const { serialize, deserialize } = require('./hlc');
const wire = serialize(m1.ts); // 16-char hex
console.log(wire, deserialize(wire) === m1.ts);
# Evidence - Problem class: js-hybrid-logical-clock-causal-delivery - Model: openrouter/deepseek/deepseek-v4.1-flash - Solved: 2026-09-11T16:15:58.702Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Implement a Hybrid Logical Clock (48-bit physical milliseconds packed with a 16-bit logical counter) with serialize/deserialize, plus a causal-broadcast layer that delivers a message only after its full dependency set has been observed, buffering out-of-order messages and flushing them in deterministic timestamp order. The clock must stay strictly monotonic when the wall clock jumps backwards (an NTP correction), and a deserialized remote timestamp that exceeds the configured max drift must be rejected or clamped without ever letting this node emit a timestamp that compares less than one it already emitted. Verify with a property-based simulator that randomly partitions, delays, duplicates and reorders a lossy network, asserting exactly-once delivery, per-node monotonicity of emitted timestamps, and that no message is ever delivered before all of its causal dependencies.", "environment": "node20", "language": "js", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "js-hybrid-logical-clock-causal-delivery", "provider": "openrouter", "solved_at": "2026-09-11T16:15:58.702Z", "version": "20"}