quorum-lease-epoch-fencing
Done. The solution is written and verified.
~)| File | Purpose |
|---|---|
SOLUTION.md |
Self-contained write-up: root-cause analysis, normative rules, safety + liveness proofs, smallest counterexample, embedded code, verification output |
fencing-sim.js |
Runnable discrete-event simulator (nodes, virtual clock, partitions, quorum elections, leases, fencing-token store) |
verify.js |
5-scenario verification suite — node verify.js exits 0 |
A lease is a local timing fact, not cluster state. Under async partitions/clock drift/pauses a deposed leader can keep believing it holds authority and apply writes after a successor takes over. A write with no ordering token carries no authority information, so the resource cannot reject it.
q = ⌊N/2⌋+1 for both elections and commits; quorums intersect.epoch/grantedEpoch before replying; grant only strictly increasing epochs. ⇒ at most one leader per epoch, totally ordered.L; leader acts only until L − 2ε. Leases are for progress, not safety.highToken and rejects token < highToken. This is the actual stale-leader defence.Scenario A fencing ON, over-long stale lease -> stale token=1 REJECTED after token=2
Scenario B fencing OFF (weakened) -> stale applied after successor (authority regresses)
Scenario C N=2, quorum=1 -> two leaders share epoch 1; fence can't order equal tokens
Scenario D crash + lease expiry -> new leader commits (liveness)
Scenario E 200 random partition/timing runs -> 0 two-leader epochs, 0 fence regressions
=== 11/11 checks passed ===
The smallest counterexample is N=2, q=1: two isolated nodes both self-elect at epoch 1, so both writes carry the same token and the fence cannot disambiguate them — proving token uniqueness must come from quorum intersection, not from fencing. The embedded code was diff-checked byte-for-byte against the runnable sources.
# Evidence - Problem class: quorum-lease-epoch-fencing - Model: openrouter/deepseek/deepseek-v4.1-flash - Solved: 2026-10-04T04:16:29.132Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Given an asynchronous replicated log with crashes, partitions, delayed messages, and expiring leases, design a leader handoff protocol that prevents stale leaders from committing writes after a successor obtains authority. State the quorum, epoch, and fencing-token rules, then construct executions proving safety and eventual progress under the stated synchrony assumptions, including the smallest counterexample when a rule is weakened.", "environment": "node20", "language": "js", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "quorum-lease-epoch-fencing", "provider": "openrouter", "solved_at": "2026-10-04T04:16:29.132Z", "version": "20"}