js-quorum-lease-clock-skew-fencing-recovery-20261010

Answer

Solution delivered

Artifacts - ~/solution.md — the required write-up (title, root-cause analysis, exact fix with full runnable code, verification). - ~/solution.js — the self-contained implementation + simulator + test suite. Verified: node solution.js → ALL CHECKS PASSED (exit 0). The code embedded in the markdown is byte-identical to the runnable file (checked programmatically).

Root cause

The failure is a worker committing after its lease was transferred away. Three independent defects produce it:

1. Wall-clock expiry is used as the safety mechanism. With changing skew the error is up to 2*maxSkew + maxDelay; if the next lease is granted inside that window, holders overlap.
2. Fencing tokens are not strictly monotone/durable. Non-strict >= promise, in-memory maxPromised, in-memory resource maxToken, or no quorum promise all let stale/duplicate tokens through.
3. The lease is activated before the resource is fenced, leaving a post-transfer window where an old write is still accepted.

Exact fix (the critical lines)

// Voter: STRICT promise, persist BEFORE ack -> unique, globally increasing tokens
const ok = token > this.maxPromised;      // NOT >=
if (!ok) return { ok:false, reason:'stale' };
this.maxPromised = token; this.persist();

// Resource: reject anything below the durable high-water mark (never consults a clock)
if (token < this.maxToken) return { ok:false, reason:'fenced', maxToken:this.maxToken };
this.maxToken = token; this.persist();

// Coordinator: transfer is complete only after the durable fence moves
const adv = this.resource.advance(token);
if (!adv.ok) return { ok:false, reason:'fence-unavailable', token }; // burn the token

// Worker: bounded clock margin for liveness only
const usable = Math.max(0, duration - (2*this.cfg.maxSkew + this.cfg.maxDelay));

Safety is clock-free (majority quorum intersection + strict token monotonicity + durable fence). Clocks only bound the usable lease window.

Verification

• 5 safety invariants checked over the full ledger: GRANT_NOT_MONOTONIC, TOKEN_REUSE, STALE_ACCEPT, STALE_AFTER_TRANSFER, COMMIT_AFTER_LEASE_END.
• Targeted falsification: each of 5 injected defects produces a violation, while the fixed config produces none.
• Deterministic adversarial simulator (mulberry32-seeded) varying quorums, concurrent same-token proposals, crashes/recoveries, whole-cluster restarts, resource crashes, and fast→slow clock flips discovers all 5 defect classes (e.g. no-fencing: 57, non-strict-promise: 254, non-durable-nodes: 190, naive-clock-margin: 214).
• Extended confidence: fixed config, 7,500 trials, 0 violations, 33,548 successful grants.
• Availability: majority grant succeeds; 2-of-5 minority fails with no-quorum; duration <= 2*maxSkew+maxDelay yields zero usable time.