go-paxos-ballot-promise-ordering
The corrected Paxos acceptor lives in ~/paxosballot/paxos.go. The two traps are fixed with two deliberate properties in the Prepare handler:
Fix 1 — off-by-one (<= vs <). Reject only when the incoming ballot is strictly lower than the highest promised ballot (b < promised), and never persist anything on the reject path. With b <= promised the reject branch also writes promisedBallot = b, so a rejected ballot clobbers (lowers) the promise — after which a competing leader with a ballot between the old and new promise can hijack the round. <= additionally rejects equal-ballot retries, which must instead re-promise and return the highest accepted value.
Fix 2 — persist after validate, and persist a full state copy. The promise is written to the store only after the ballot has been validated against the current promise, and the write is next := a.state (a full copy carrying AcceptedBallot/AcceptedValue forward). Persisting before validation lets a request that is about to be rejected corrupt the promise anyway, and a naive "fresh record" write silently drops the accepted value — breaking the invariant that once a value is accepted for a ballot, it is never lost.
func (a *Acceptor) Prepare(b Ballot) PrepareResult {
a.mu.Lock()
defer a.mu.Unlock()
// Step 1: validate FIRST. Reject iff b < PromisedBallot (strict <).
// b < promised -> reject, and DO NOT touch any state
// b == promised -> re-promise; return the highest accepted value
// b > promised -> raise the promise to b
if b < a.state.PromisedBallot {
return PrepareResult{OK: false, PromisedBallot: a.state.PromisedBallot}
}
// Step 2: persist ONLY after validation passes, as a FULL COPY of the
// state so raising the promise can never discard an accepted value.
next := a.state
next.PromisedBallot = b
if err := a.store.Write(next); err != nil {
return PrepareResult{OK: false, PromisedBallot: a.state.PromisedBallot, Err: err}
}
a.state = next
return PrepareResult{
OK: true,
PromisedBallot: next.PromisedBallot,
AcceptedBallot: next.AcceptedBallot,
AcceptedValue: next.AcceptedValue,
HasAccepted: next.HasAccepted,
}
}
Accept (Phase 2) follows the same discipline: reject iff b < promised, then persist a full copy with the accepted ballot/value set. State is durable through a Store interface (Read/Write of whole State records), so a promise or accepted value survives restarts, and a failed persist never mutates in-memory state.
The bugdemo package ships the two buggy variants (OffByOne: reject with <= + persist on reject; PersistBeforeValidate: persist before validating with a value-dropping write) so the failure modes can be reproduced on demand.
Repo: `~/paxosballot` (module `paxosballot`, go 1.26). `go vet` clean; `go test -race -v ./...` — **10/10 pass**: ``` --- PASS: TestPrepareRejectsLowerBallotAndKeepsState (reject 3, 4 after promise 7; promise stays 7) --- PASS: TestEqualBallotRePromisesWithAcceptedValue (Prepare(1) twice after Accept(1,"x") -> OK + "x") --- PASS: TestHigherPreparePreservesAcceptedValue (Accept(5,"alpha"), Prepare(9) -> returns "alpha") --- PASS: TestRejectedPrepareDoesNotCorruptState (reject leaves all fields; retry 8 re-promises "gold") --- PASS: TestPromiseSurvivesRestart (promise 42 durable; Prepare(41) rejected after restart) --- PASS: TestAcceptedValueSurvivesRestart (Accept(10,"persist-me") durable across restart) --- PASS: TestPrepareStoreFailureLeavesStateUnchanged (failed persist: no in-memory/durable change, Err set) --- PASS: TestAcceptRules (Accept below promise rejected; equal/above OK) --- PASS: TestMultipleRounds (round 2/3 leaders learn and keep v1) --- PASS: TestConcurrentPreparesMonotonic (16 goroutines x 100 ballots; final promise == max) ok paxosballot 1.012s ``` Edge cases covered: equal-ballot retries (re-promise, not reject), rejected ballots never lowering the promise, accepted value surviving higher-ballot promises *and* restarts, store-write failure leaving both memory and disk state untouched, and concurrent monotonicity of the promise. The traps are real — `go test -tags bugdemo ./bugdemo/` fails all 4 scenarios against the buggy code, exactly as described in the problem: ``` FAILURE MODE: rejected ballot 3 overwrote the promise: got 3, want 5 (OffByOne, <= persists on reject) FAILURE MODE: equal-ballot Prepare(2) must re-promise, got a rejection (OffByOne, <= rejects equal ballot) FAILURE MODE: raising the promise discarded the accepted value (PersistBeforeValidate, value dropped) FAILURE MODE: rejected request overwrote the promise: got 3, want 5 (PersistBeforeValidate, persist before validate) ``` The identical scenarios pass against the fixed implementation in `paxos_test.go`.
{"model": "deepseek-v4-flash", "problem_class": "go-paxos-ballot-promise-ordering", "result": "passed", "tests": 10}The corrected Paxos acceptor lives in ~/paxosballot/paxos.go. The two traps are fixed with two deliberate properties in the Prepare handler:
Fix 1 — off-by-one (<= vs <). Reject only when the incoming ballot is strictly lower than the highest promised ballot (b < promised), and never persist anything on the reject path. With b <= promised the reject branch also writes promisedBallot = b, so a rejected ballot clobbers (lowers) the promise — after which a competing leader with a ballot between the old and new promise can hijack the round. <= additionally rejects equal-ballot retries, which must instead re-promise and return the highest accepted value.
Fix 2 — persist after validate, and persist a full state copy. The promise is written to the store only after the ballot has been validated against the current promise, and the write is next := a.state (a full copy carrying AcceptedBallot/AcceptedValue forward). Persisting before validation lets a request that is about to be rejected corrupt the promise anyway, and a naive "fresh record" write silently drops the accepted value — breaking the invariant that once a value is accepted for a ballot, it is never lost.
func (a *Acceptor) Prepare(b Ballot) PrepareResult {
a.mu.Lock()
defer a.mu.Unlock()
// Step 1: validate FIRST. Reject iff b < PromisedBallot (strict <).
// b < promised -> reject, and DO NOT touch any state
// b == promised -> re-promise; return the highest accepted value
// b > promised -> raise the promise to b
if b < a.state.PromisedBallot {
return PrepareResult{OK: false, PromisedBallot: a.state.PromisedBallot}
}
// Step 2: persist ONLY after validation passes, as a FULL COPY of the
// state so raising the promise can never discard an accepted value.
next := a.state
next.PromisedBallot = b
if err := a.store.Write(next); err != nil {
return PrepareResult{OK: false, PromisedBallot: a.state.PromisedBallot, Err: err}
}
a.state = next
return PrepareResult{
OK: true,
PromisedBallot: next.PromisedBallot,
AcceptedBallot: next.AcceptedBallot,
AcceptedValue: next.AcceptedValue,
HasAccepted: next.HasAccepted,
}
}
Accept (Phase 2) follows the same discipline: reject iff b < promised, then persist a full copy with the accepted ballot/value set. State is durable through a Store interface (Read/Write of whole State records), so a promise or accepted value survives restarts, and a failed persist never mutates in-memory state.
The bugdemo package ships the two buggy variants (OffByOne: reject with <= + persist on reject; PersistBeforeValidate: persist before validating with a value-dropping write) so the failure modes can be reproduced on demand.
Repo: `~/paxosballot` (module `paxosballot`, go 1.26). `go vet` clean; `go test -race -v ./...` — **10/10 pass**: ``` --- PASS: TestPrepareRejectsLowerBallotAndKeepsState (reject 3, 4 after promise 7; promise stays 7) --- PASS: TestEqualBallotRePromisesWithAcceptedValue (Prepare(1) twice after Accept(1,"x") -> OK + "x") --- PASS: TestHigherPreparePreservesAcceptedValue (Accept(5,"alpha"), Prepare(9) -> returns "alpha") --- PASS: TestRejectedPrepareDoesNotCorruptState (reject leaves all fields; retry 8 re-promises "gold") --- PASS: TestPromiseSurvivesRestart (promise 42 durable; Prepare(41) rejected after restart) --- PASS: TestAcceptedValueSurvivesRestart (Accept(10,"persist-me") durable across restart) --- PASS: TestPrepareStoreFailureLeavesStateUnchanged (failed persist: no in-memory/durable change, Err set) --- PASS: TestAcceptRules (Accept below promise rejected; equal/above OK) --- PASS: TestMultipleRounds (round 2/3 leaders learn and keep v1) --- PASS: TestConcurrentPreparesMonotonic (16 goroutines x 100 ballots; final promise == max) ok paxosballot 1.012s ``` Edge cases covered: equal-ballot retries (re-promise, not reject), rejected ballots never lowering the promise, accepted value surviving higher-ballot promises *and* restarts, store-write failure leaving both memory and disk state untouched, and concurrent monotonicity of the promise. The traps are real — `go test -tags bugdemo ./bugdemo/` fails all 4 scenarios against the buggy code, exactly as described in the problem: ``` FAILURE MODE: rejected ballot 3 overwrote the promise: got 3, want 5 (OffByOne, <= persists on reject) FAILURE MODE: equal-ballot Prepare(2) must re-promise, got a rejection (OffByOne, <= rejects equal ballot) FAILURE MODE: raising the promise discarded the accepted value (PersistBeforeValidate, value dropped) FAILURE MODE: rejected request overwrote the promise: got 3, want 5 (PersistBeforeValidate, persist before validate) ``` The identical scenarios pass against the fixed implementation in `paxos_test.go`.
{"model": "deepseek-v4-flash", "problem_class": "go-paxos-ballot-promise-ordering", "result": "passed", "tests": 10}