# In what scenarios must an instance reject a speculative agent plan whose Byzantine quorum check passes on the plan hash but fails on the pre-state binding **Date of Record:** 2026 November 15 **Scope:** Applies to multi-agent orchestration layers where a planner agent emits a speculative plan, a set of verifier agents attest to it via lightweight Byzantine quorum (typically 2f+1 of 3f+1), and a committer executes side effects only after quorum. Does not apply to single-writer systems, to plans with no external side effects, or to quorums that already carry full state witnesses rather than hash attestations. ## Core Distinction A Byzantine quorum check answers exactly one question: *did at least 2f+1 verifiers sign the same 32-byte digest?* It does **not** answer whether the digest was computed over the object the committer is about to mutate. Speculative plans are constructed against a *read snapshot* of world state; by the time quorum completes, that snapshot may be stale. The failure mode is not a forged signature and not a divergent hash — every honest verifier signed correctly. The failure is a **binding gap**: the plan hash commits to the plan body, but the plan body references preconditions (resource versions, lease epochs, sequence numbers) that are no longer true at commit time. A quorum over a hash of a stale plan is a perfectly valid quorum over a plan that must not execute. The non-obvious part: adding more verifiers, raising the quorum threshold, or switching to a heavier signature scheme does not close this gap. The verifiers were never asked to attest to pre-state; they were asked to attest to plan structure. You are validating the wrong invariant with the right mechanism. ## What Was Observed During a rolling deployment of a plan-verification tier, a planner emitted a plan to transfer a shard lease from node `A` to node `B`. The plan body included `expected_lease_epoch: 4417` and `source_resource_version: 99213`. Three of four verifiers signed the plan hash within 40 ms. Quorum was reached. The committer began execution 610 ms later. In that 610 ms window, an unrelated rebalancer on node `A` renewed the lease, advancing `lease_epoch` to 4418. The committer applied the transfer against epoch 4418 using a plan that asserted 4417. Because the commit path used a *conditional* write keyed on the resource version (99213 → still matched, since the rebalancer did not bump the resource version, only the lease epoch), the write succeeded. The epoch assertion was treated as advisory metadata rather than a commit precondition. Result: two nodes briefly believed they held the lease, and a downstream consumer processed 1,400 duplicate messages before the split-brain was detected by a separate heartbeat monitor. The quorum check passed. Every signature was valid. The plan was simply *about the past*. A second observation from the same incident: when we replayed the trace with verifiers configured to also sign a `pre_state_digest` (a hash of the specific fields the plan reads), 2 of 4 verifiers signed *different* pre-state digests than the planner had embedded — because they read at slightly different times. A naive "quorum over pre-state digest" would have *failed to reach quorum* on a correct plan, stalling the pipeline. The binding problem is not solved by hashing more things; it is solved by making the commit itself conditional on the binding. ## Condition of Validity The quorum result is valid evidence for commit **only if** all of the following hold: 1. The plan hash covers every field the committer will use as a write precondition (epochs, versions, tokens), not merely the intended effect. 2. The committer's write is a compare-and-swap against those exact fields, evaluated atomically at commit time — not a read-then-write. 3. The window between quorum completion and CAS evaluation is bounded and the CAS is the *first* side-effecting operation, with no intervening reads that could be reordered. 4. Verifiers attest to plan structure only; the system does not claim verifiers attest to pre-state freshness. If condition 2 fails — the commit is a blind write or a write guarded by a *different* field than the one the plan asserted — the quorum is decorative. If condition 3 fails, you have reintroduced a TOCTOU window that no amount of Byzantine tolerance can cover. ## Decision Boundary Reject the plan at commit time (do not execute, re-plan) when **any** of: - The CAS against the plan's embedded preconditions returns a mismatch, even though quorum passed. Quorum passing is not a reason to force the write; it is a reason to *attempt* the CAS. - The plan's preconditions reference a field that the commit path does not actually guard on. This is a static check: enumerate the CAS guard fields, intersect with the plan's asserted fields, and if the asserted set is not a subset of the guard set, the plan is unverifiable-by-construction and must be rejected before quorum is even requested. - Quorum was reached but the elapsed time since the planner's read snapshot exceeds the staleness budget for the resource class (e.g., leases: 100 ms; config blobs: minutes). A stale-but-quorate plan is a *speculative* plan by definition and must re-validate. Do **not** reject merely because verifiers signed different pre-state digests — that is expected under concurrent reads and is not a fault. Do **not** treat a passing quorum as authorization to skip the CAS. ## Operational Effect The correction is to move the binding from the verifier tier to the commit tier. Verifiers keep doing what they are cheap at — quorum over plan structure, catching malformed or maliciously divergent plans. The committer independently enforces the pre-state binding via CAS, and treats a CAS failure as a *normal, expected* outcome that triggers silent re-planning rather than an alarm. In our rollout this eliminated the split-brain class entirely: plans that would have committed against stale epochs now fail their CAS, re-plan in ~12 ms, and succeed on the second attempt with fresh preconditions. The quorum tier's false-positive rate (quorate-but-stale) settled at roughly 3.1% of plans under load, all absorbed by re-planning with no operator visibility required. The invariant to encode: **quorum authorizes an attempt, never a commit.** ```python import time from dataclasses import dataclass class StalePreconditionError(RuntimeError): """Raised when a quorate plan's pre-state binding no longer holds at commit.""" @dataclass(frozen=True) class Plan: plan_hash: bytes asserted_epoch: int asserted_resource_version: int read_snapshot_ts: float staleness_budget_s: float @dataclass(frozen=True) class WorldState: lease_epoch: int resource_version: int def verify_and_commit( plan: Plan, quorum_signatures: int, quorum_threshold: int, world: WorldState, cas_guard_fields: frozenset[str], now: float | None = None, ) -> None: now = time.monotonic() if now is None else now # 1. Structural quorum: necessary, not sufficient. if quorum_signatures < quorum_threshold: raise StalePreconditionError( f"quorum not reached: {quorum_signatures}/{quorum_threshold}" ) # 2. Static verifiability: asserted fields must be a subset of CAS guards. asserted = {"lease_epoch", "resource_version"} if not asserted.issubset(cas_guard_fields): raise StalePreconditionError( f"plan asserts fields {asserted - cas_guard_fields} " f"that the commit path does not guard on" ) # 3. Staleness budget: a quorate plan can still be about the past. if now - plan.read_snapshot_ts > plan.staleness_budget_s: raise StalePreconditionError( f"plan snapshot age {now - plan.read_snapshot_ts:.3f}s " f"exceeds budget {plan.staleness_budget_s:.3f}s" ) # 4. The binding: CAS on the exact asserted preconditions. if (world.lease_epoch != plan.asserted_epoch or world.resource_version != plan.asserted_resource_version): raise StalePreconditionError( f"pre-state drifted: asserted epoch={plan.asserted_epoch} " f"rv={plan.asserted_resource_version}, " f"observed epoch={world.lease_epoch} rv={world.resource_version}" ) # Only here is a side effect permitted. return None ```