Skip to content

Formal verification ​

bide checks the designs of its coordination protocols with TLA+ models, written in PlusCal and explored exhaustively, within stated bounds, by the TLC model checker in CI. The Apalache model checker adds, nightly, an inductive invariant of the claim protocol that proves, for two drivers over two processes, AtMostOnce and NotStartedExclusive on one call (attempts 0..3, 8 claim ids) and all four of AtMostOnce, NotStartedExclusive, NoLiveOverride and AtMostOncePerIntent with halt resolution and the caller's second call (attempts 0..3, 6 claim ids), without the approval gate, and, under the lease check, assuming no plain run holds the live attempt at the check (PlainRunIdleAtCheck), at any depth and for any number and mix of faults within the run's 8 (6) claim ids and attempts 0..3 (claim ids are never reused, so this bounds the number of claims). This page is the overview: why bide does it, what each model guarantees and which code it covers, every bug the models found or confirmed and where it was fixed, what runs on a pull request and what runs nightly, how the models and the Go code stay in step, and what the models do not cover.

The detailed reference for every model (its rules, model-to-code map, properties, configurations and bounds) is spec/tla/README.md. The plan behind the work, with its milestones, is the design note formal models of the coordination protocols.

At a glance:

  • 14 models (1, 1b, 2, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 and 17), each checked on every pull request and merge queue batch that changes it, and all of them on main and nightly. Models is a required check.
  • 495 configurations in the merge queue (192 that must pass, each also run for vacuity, and 303 that must fail with their named property: the regression, finding and limit configurations and twenty-eight ci reachability checks), and 122 larger ones nightly.
  • Apalache, nightly: an inductive invariant proves, for two drivers over two processes, AtMostOnce and NotStartedExclusive on one call (attempts 0..3, 8 claim ids) and all four of AtMostOnce, NotStartedExclusive, NoLiveOverride and AtMostOncePerIntent with halt resolution and the caller's second call (attempts 0..3, 6 claim ids), without the approval gate, and, under the lease check, assuming no plain run holds the live attempt at the check (PlainRunIdleAtCheck), at any depth and for any number and mix of faults within the run's 8 (6) claim ids and attempts 0..3 (claim ids are never reused, so this bounds the number of claims); a bounded symbolic regression must find #90's F2.
  • 28 bugs found in bide's own design or code (F1 to F5, P1, P2, T1 to T6, a rollback that never ended, L1 to L7, D1 to D3, and S1 to S4), and one more confirmed (a spend-accounting bug found in review, which model 8 confirmed). Most were caught before release; four (L1, S1, S2, S4) shipped in releases up to v0.9.0 and were fixed in v0.10.0. Each fixed one is kept as a regression configuration (L2 to L7 and S3 since P14 implemented their rules, S1, S2 and S4 since #137, D1 to D3 since #133). Model 14 found N1 in the notifier design before the core was built (adopted, kept as a regression), and, by the budgets of the core, N2 and N3 at long claim TTLs (fixed in the core, and checked as assumptions).

What TLA+ and model checking are ​

TLA+ is a language for describing a system as its states and the steps that change them. PlusCal is a code-like form of TLA+ that reads like an algorithm, with labels marking the steps; bide writes its models in PlusCal, and the tools translate them to TLA+. TLC is the model checker: it starts from the initial states and explores every state reachable within the bounds a configuration sets (how many drivers, crashes, ambiguous replies, attempts).

A test runs the schedules someone wrote or a randomizer happened to reach. TLC tries every interleaving of the modelled steps and every placement of every fault, up to the bound, and checks the stated properties in each state it reaches.

The properties come in two kinds. An invariant must hold in every reachable state: "a side effect never fires twice". A liveness property says something good eventually happens: "a dead holder's run is eventually picked up". The bounds are small, so a result says nothing beyond them. Small bounds still find real bugs because most protocol bugs show up in small cases: two drivers, one crash, two or three ambiguous replies (the small-scope hypothesis). Every bug on this page was found at such bounds. A vacuity check guards against a model that passes because nothing happens in it: each passing configuration is run again with the invariant "the effect never fires", which TLC must report violated.

Apalache is a second model checker for the same models. Instead of enumerating states, it turns a model's states and steps into formulas and lets an SMT solver search them. The three kinds of result differ in what they cover:

  • Bounded exhaustive (TLC): every reachable state within a configuration's bounds (drivers, faults, attempts), however many steps it takes to reach. Nothing beyond the bounds.
  • Bounded symbolic (Apalache, check --length=N): every behavior of up to N steps, with the constants a configuration leaves open (which process each driver runs in, the kind of call, the lease holders) chosen by the solver. It reaches larger parameters than TLC, but only short behaviors.
  • Inductive (Apalache): a stronger statement IndInv that holds initially, that every step preserves from any state satisfying it, and that implies the property. Three one-step checks then prove the property in every reachable state, at any depth, with no bound on the fault counters. What stays bounded is what the check fixes: the number of drivers, the attempts and the claim ids, and since claim ids are never reused, the id pool also bounds how many claims, and so how many faults that force a new claim a run can have.

When a property fails, TLC prints a counterexample: the step-by-step trace of states that leads to the violation, each state one atomic step such as a store write, a crash or a cancellation. In bide's models these are typically 10 to 30 states long.

A small excerpt from the claims model (spec/tla/claims/Claims.tla): the step a claim takes when its marker write returned an error, and the at-most-once invariant.

tla
ClaimNS:
  \* The marker may have committed: record that this claim never called the effect.
  Reply(reply);
  WriteNS(CallOf[self], g, cid[self], reply);
  if reply # "ok" then
    Remember(g, cid[self]);
  end if;
  outcome := "error"; goto Finish;

AtMostOnce == \A c \in Calls : fired[c] <= 1

Reply(reply) lets TLC pick any store reply (success, an error that did not commit, an error that did, while the configuration's error budget lasts), the claim writes its not-started record and remembers its claim id if that write fails too, and AtMostOnce says that no call's effect has fired more than once, in any state TLC reaches.

To learn more, see Leslie Lamport's TLA+ home page.

Why bide model-checks ​

bide's core promise is that a side effect fires at most once, and that what the journal says about it is true, across process crashes, overlapping drivers, cancellations and a store that can report an error for a write it actually committed (an ambiguous write). That promise rests on small protocols: an exclusive attempt claim, a not-started record bound to the claim, numbered re-attempts, an in-process memory of claims whose write was ambiguous, a resume gate, halt resolution, leases and recovery.

bide already tests this layer hard: deterministic crash sweeps, a reference model with randomized schedules, exhaustive fault-schedule explorations of the claim protocol, a multi-process harness against real Postgres, and mutation checks (see How bide is verified). Those tests check the implementation on the schedules they reach. The bugs that matter here need a specific combination of faults and interleavings, which is where tests run out (plan, section 2):

  • Fault placement is combinatorial. F1 below needs three ambiguous store replies and a cancellation, in a specific order, in one process. F3 needs three error replies and no crash.
  • Interleaving is combinatorial. T6 needs a drive cancelled while a leaked call is still inside a tool, a re-drive that answers from a cache, and a later saga step that fails.
  • Reply ambiguity is invisible to the code. A write that errors may have committed. The code cannot branch on which happened, so a test must inject both outcomes at every write. A model gives every write both outcomes by construction.
  • Some bugs need no fault at all. L2 below is a plain race between Cancel and a drive.

TLC explores every interleaving of a model's rules and every placement of its faults within the configuration's bounds, and checks each property in every reachable state. Two results show what that adds:

  • The claims model (model 1) found F1 to F4 in the claim protocol of P6a (#92) after that pull request had been through three adversarial review rounds and its exhaustive fault-schedule harness (agent/claim_explore_test.go, agent/claim_explore_conc_test.go) was passing. Three of the four were double fires. All four were fixed in #92 before it merged.
  • The tool-call model (model 9) found T1 to T6 in redesign P12 (#117) after five review rounds. Each got a failing Go test, and all were fixed in #117 before it merged.

The models ​

PR and nightly counts are configurations. On a pull request, each model runs its ci configurations (each also run a second time for vacuity: it must show the effect can fire at all) and its regression, finding and limit configurations, each of which must fail with exactly its named property. Nightly runs larger bounds.

ModelWhat it guaranteesKey propertiesCode it coversPRNightlyStatus
1: claims and attemptsA side effect or a Step fires at most once across crashes, ambiguous writes, cancellations and drivers in one or several processes; a won claim never halts; halt resolution never overrides a live driver; a call that provably never started does not halt for ever.AtMostOnce, AtMostOncePerIntent, NotStartedExclusive, NoLiveOverride, WinnerNeverHalts, ResultStable, Progressagent: journal.go, attempt.go, step.go, loop.go (resume gate, tool claim), halt.go, keys.go, saga.go3623Checked; F1 to F4 fixed in #92
1b: the approval gateAn effect under an approval gate fires only with a recorded sufficient approval; a recorded denial is final; a passing tally rests on enough valid approvals by distinct people, signed over this exact call; the gate never waits for approvals already in. With a deadline (ApprovalPolicy.Timeout), an expired gate never runs its call, an expiry and a passing tally cannot both be the outcome, and a decision recorded after the deadline never counts. The taint guard: a call of a tainted turn also needs the escalation gate (a second instance on the derived subject <call>#taint) and never runs under the Refuse policy, and the escalation approval never replaces the tool's own gate. (On agent tool calls; deadlines on plan flow node gates are checked by Go tests, plan/deadline_test.go, not by any model, and the model takes a decision's time stamp and write as one step.)NoUnapprovedFire, TaintedNeedsEscalation, DenialFinal, TallySound, DenialSound, NoStuckPause, ExpiredNeverRuns, LateNeverCounts, ExpiryAfterDeadline, OutcomeOnceagent: approval.go, toolexec.go (quorumTally), the pre-pass in loop.go, deadline.go311Checked; F5 fixed in #109
2: the bide protocol's claim rulesA remote tool call fires at most once under lost, late and duplicated deliveries, engine and worker crashes; at most one worker runs under a marker; DELIVERY_EXHAUSTED is recorded only when no effect ran.AtMostOnce, BeginExclusive, BeginIdempotent, NoRunAfterAbandon, ExhaustedTruthful, DownstreamOnceNone yet: a design model of the bide protocol, which is not implemented168Checked; P1 and P2 fixed in the design (#95)
7: flow semanticsA lowered plan flow runs each node that is not retry-safe at most once per loop iteration, and the journal always holds a path the flow declares, resolutions included. A gated node never runs before its approval gate has the approvals it needs for that node and, in a loop, that iteration (gates are per iteration), across crashes, error replies, two drivers and halt resolution. Taint in plan flows (flow-taint) is modelled too, with inherited marks from a tainted parent and taint coming up to it: no side-effecting node attempt is claimed after a source read (a read set folded from the journal in its order, taint-mark records included) unless the second gate instance node:[iter:n:]name:taint passed or the node is exempt; Refuse is durable and re-refuses on every drive; a drive resuming under changed declarations is refused.AtMostOncePerIteration, NestedOncePerIteration, Conform, ResultsTyped, GateHeld, GatedResults, TallySound, Completes, TaintGateHeld, ResumeExact, TaintTallySound, SeparateHeld, RefusedClean, PreExecHeld, GateReasonFirst, ReplayNeverBlocked, InheritedPolicylessRefused, InheritedPolicylessNoTracked, ParentMarksUp, ParentGated, OwnGateStable, NoEchoplan: flow.go, gate.go, resolve.go; agent/flowgate.go, agent/journalhook.go, agent/keys.go, agent/approval.go (SubmitDecision), agent/halt.go (Approve)548Checked; no new finding
8: spend accountingThe journal holds every billed model request exactly once, across hedged and retried requests, failed calls, ambiguous writes, crashes and two drivers; Result.Spend never exceeds it.NoDoubleCount, SpendExact, ResultSpendagent: modelcall.go, generate.go, loop.go (Load, settle)62Checked; confirmed the #104 shared-key bug on the old rule
9: the tool-call state machineUnder any tool middleware, retries, leaked next calls and sibling calls, a side effect fires at most once, the journal's record of a call is true, a saga's rollback accounts for every effect left in place, and the rollback ends; a refusal before beginCall (an amount cap, a taint policy's Refuse) never begins the tool and leaves at-most-once intact.NoDoubleFire, RefusedNeverBegan, TruthfulRecord, NoLostSibling, SagaAccounted, NeverBegunProgress, RollbackEndsagent: toolexec.go, loop.go, saga.go, tool_middleware.go; internal/toolhook2813Checked; T1 to T6 fixed in #117
10: the run lifecycle and recoveryRecovery never resumes a finished run; one live lease holder per epoch; each end marker is written once; nothing fires after a run completed or aborted, or under a claim won after it was cancelled; Status and every writer report the first end marker; per-run options and the tool filter survive recovery; a cancelled saga is rolled back; a dead holder's run is taken over within a bounded time of its lease lapsing.NoResumeOfFinished, OneDriverPerEpoch, NoDoubleCompletion, FinishedFinal, CancelFinal, VerdictAgreement, StatusTruthful, FilterHonoured, RunOptionsDurable, CancelRollsBack, BoundedPickup, PickedUpagent: recovery.go, lease.go, loop.go, saga.go, halt.go, journal.go; the stores' Leaser and Lister419Checked, and gates P14 (#129); L1 fixed in #126; L2 to L7 implemented by P14, kept as regressions
11: delegation, sub-run authority and saga treesA child never acts with authority its delegation did not grant, nor reaches a tool after its grant expired; a saga's rollback compensates or lists every write anywhere in the tree, under the authority each sub-run journaled; a halt or lost outcome anywhere in the tree stops later saga steps; a sub-run runs only under its own call's ID while the call is open; a storage error or a wrong-authority resume is never recorded as a delegation failure, and a run it stopped continues once the right grant is bound.AuthorityNarrows, RollbackSound, RollbackUnderGrant, HaltPropagates, NoForgedSubRun, NoFalseFailure, UnrecordedContinues, RollbackEndsaudit: delegate.go; agent: subagent.go, saga.go, runctx.go, loop.go; internal/toolhook378Checked; D1 to D3 fixed in #133
12: sessionsEach turn of a session is recorded once and answers its own message; a SendOnce key is one turn, whose work runs in one run; the history is append-only and every reader sees one order; a resumed turn sees the transcript it started from; no run is shared between sessions or with a root run; a session whose driver died resumes when its message is sent again.TurnOnce, KeyOnce, NoCrossTalk, NoLostTurn, SeedFaithful, AppendOnly, BudgetHeld, NoFalseRefusal, Answered, TurnsSettleagent: session.go, keys.go (session run IDs)267Checked; S1, S2 and S4 fixed (#137); S3 fixed by P14 (v0.10.0)
13: probes for unknown outcomesActing on a probe's verdict (Happened, or NotHappened and a re-run) never makes a side effect land twice when the provider fences the original attempt (an atomic, monotonic check-and-void, or deduplication by the call's key) and every attempt's marker records the fence; attempt-scoped results keep a rejected older attempt's failure from becoming the call's outcome.AtMostOnce, OutcomeTrue, VerdictTrueNone yet: a design model of probes, which are not implemented112Checked; the documented counterexamples (lease as a fence, one result key per call, NotHappened without the Fenced stamp) fail as expected; found that the provider's void must be monotonic
14: notificationsA notification is never dropped silently: an event that stays current is acknowledged (or, with a sink that never accepts, failing and overdue are raised); duplicates are bounded by 1 + crashes + lost replies + claims that lapsed mid-send; no two processes deliver under live claims; overdue comes within one round of the deadline and its notice is sent, by a peer when the holder may be dead; recovery_failing fires under a crash loop; an event that stopped being current after a delivery was attempted gets its all-clear (resolved), never before it stopped, never overdue, and not necessarily after the event; each receiver of a routed gate has its own acknowledgement; an escalation step is observed only when due, in order, and not once the event is cleared or (but an approval) acknowledged, and stops with the event; acked and cleared are final; and the notifier never changes the run lifecycle (composed with model 10).NoSilentDrop, DupBound, NoticeSent, PeerCovers, NoticeDupBound, NoConcurrentDouble, OverdueRaised, CrashLoopAlerts, ClearsDelivered, ClearNeverEarly, ClearNeverOverdue, EscOnlyIfDue, EscChain, EscNotWhenSatisfied, EscRaised, EscStops, Terminal, LifeStepsOnlyagent: notify_engine.go (the round), notify_route.go (routing and escalation), notify_fold.go (the fold) of the notifier; no markers yet5821Checked; one regression per property breaks its rule and fails; found N1 (a failure count in memory never raises failing under a crash loop; adopted), N2 and N3 (round and notice budgets at long claim TTLs; fixed)
15: approver identityThe counting rule for a certificate-bound approver: a counted decision's leaf carries exactly the approver's identifier and was valid at A(d); no CRL the verifier received, or published longer ago than the status may be old, lists the leaf with E <= A(d); unknown, stale or out-of-window status never counts (fail closed); a decision written after a head already stamped at or after the revocation never counts, whatever its decided_at or a later head says; a passing tally rests on distinct identifiers and, with the name constraint, distinct people; a terminal tally is not recounted and stale status never removes a counted decision; the live count and the pre-execution check read a CRL beyond notAfter only if it is the first one after it (a pruning CA may have emptied any later one), also with a withheld CRL; a tally forms only from decisions the archive does not list, and a decision a revocation removed is not counted again; a gate crash loses the counted set and nothing else; the call does not run on stale status or after a counted decision's leaf, or the CA above it (a second tier with its own, longer status age), shows a revocation; a final verdict needs the complete CRL series, absence only from the first CRL after notAfter, and (with a CA tier) a root CRL a window past the decision that does not list the CA; the gate's own Anchor step gives a direct write a covering head (coverage only: that the gate then counts it is not claimed). Model 1b adds the pre-execution check on every path to the tool (crash recovery, a redeploy, a retry, and a path that skips it), the identity re-ask that lets a replacement decision execute after a revocation held the call, and the decision relation (approver, verdict, decision time, leaf).IdentityBound, RevocationSound, FailClosed, NoBackdate, SeatPerPerson, SeatPerIdentifier, TerminalStable, StaleNeverUncounts, NoExecAfterKnownRevocation, FinalNeedsCompleteSeries, AbsenceOnlyInWindow, TallyClean, DeadStaysOut, EventuallyCovered; in 1b NoExecAfterKnownRevocation, NoSquat, OneRecordPerDecision, ReplacementSupersedesaudit: VerifyChain, EvaluateStatus, AuditedStore.Reanchor; agent: TallyApprovals; and the other marked identity code in audit (audited_store.go, cert_approver.go, identity_cert.go, identity_idp.go, identity_status.go)22 (14 passing, each also run for vacuity, and 8 reachability checks) and 7 in model 1b; 25 counterexample and 7 in model 1b; 1 limit4Checked; one counterexample configuration per rule breaks it and fails with the property it guards (no freshness rule, no non-decreasing head times, no name constraints, no series coverage, no gate Anchor step, no pre-execution check, no L(C) rule on the live count or the check, no CA-tier check at the count or before the call, the leaf's age used for the CA tier's status or the reverse, no tally recheck, no dead set; in 1b no re-ask, a path that skips the check, the decision time or verdict out of the name); DistrustAfter, intermediates, OCSP and delta CRLs are not modelled
16: the kill switchA stop is read by a call after its claim, and the call starts only if no covering stop is active in what it read; a read that fails holds the call; a stop, a lift, a policy transition and a mode record never start an effect, and a halted call never starts again. The mode is each process's configuration, so no store content can switch it; an audited process counts only records signed by approvers of the policy in force at their position, a lift needs a quorum with one lifter other than the setter, and a stop set under an earlier policy stays in force after a policy transition, a process pinned to any policy on the chain walks it from the root (and reports the stops unknowable until it reaches its pin), a record for another deployment changes nothing, and a basic process does not lift a signed stop on a plain lift.AtMostOnce, StartedSawNoStop, ForgedNoEffect, ModeRecordsEvidence, LiftNeedsQuorum, AgreesWithChain, ForeignNoEffect, BasicSignedStopNeedsSignedLift, NoSpuriousUnknowable, EffectiveImpliesTrailed, StopsNeverDroppedagent: stop_control.go (the fold), stop_trail.go, the check points in loop.go, toolexec.go and endmarker.go81Checked; the documented counterexamples (no check, stale read, fail-open, plain record in audited mode, setter-only lift, mode from the store, no policy chain, no deployment check, a stored root the process does not trust, a plain lift of a signed stop, unknowable on a forgery, a lift written to the control log before its trail record, a lift that re-fires) fail as expected
17: the cap ledgerA cap ledger of dense, insert-once slots, each carrying the window's total after it, never lets the live reservations of a window exceed the limit but by a waived slot, however drivers race for the next slot and whatever crashes or re-runs happen; an attempt has one live slot, found by a lookup; a release is applied once, written only by the loop after it sealed the call's began word, and never for a retry-safe attempt, for a second invocation or for a ResolveHalt; a call that began is never released, so a window only over-counts; an attempt's window is fixed by its intent (written after the window enters the index) and a resume never derives it again; the clock bound applies only at the first intent. Written before the ledger code, as its specification.NoOvershoot, Dense, CumExact, ExactlyOnce, ReleaseOnce, NeverUndercount, IntentStable, IndexCoversIntents, IntentChecked, ResumedNeverClockRefused, ReleaseBeforeVoidinternal/capledger (reserve, release, reconcile), agent/caps_ledger.go and recovery.go (see the caps build)3413Checked; the counterexamples (insert at n+2, a stale cum_after, a release without the dedupe scan, a reserve without the lookup, the window derived again after the intent, the index insert after the intent, a rollback that releases, a release by a second invocation, a seal of a word that says the tool began, a void before the release, a clock check on resume, no clock check, a store without A1 or A2) fail as expected; two findings kept to show why (F1: a retry-safe attempt's release, and F2: a ResolveHalt release, are unsafe; the note never releases either)

Model numbers are those of spec/tla/README.md. The plan's deferred models 3 (leases) and 5 (saga rollback) are partly covered by models 10, 9 and 11; its model 4 (the store contract) is not built.

Bugs the models caught ​

Most rows were caught before they reached a release; four (L1, S1, S2, S4) shipped in releases up to v0.9.0 and were fixed in v0.10.0 (#126, #137). Each fixed one is now a regression configuration: the old rule, restored behind a Bug flag, that must keep failing with its property. L2 to L7 are regressions of the rules P14 replaced: each fails under its old rule, and P14's code implements the adopted one. Trace lengths and details are in the linked README sections.

IDModelWhat the model foundSeverityFixed in
F11pendingClaims held one claim id per marker key, so a second failed claim of the key replaced the first, and a live marker whose effect never ran was never voided. Needs three error replies and a cancellation.Stuck run: a never-started effect halts for ever, with no crash#92 (found in #100)
F21A WithMinHaltAge resolution did not cover a remembered claim: the claim's process could void the live attempt, claim the next one and call the effect while the resolution recorded "not charged".Double fire#92: the resolver claims the next attempt first (found in #100; the rule was on main from #90)
F31F2's first fix recorded the resolution's own attempt as not started after a verdict write that errored but may have committed.Double fire#92 (found in #106)
F41On the lease path, a plain Run revived a leased driver's remembered claim and fired while the resolution recorded its verdict.Double fire#92: claim the next attempt on the lease path too (found in #106)
F51bTwo approvers whose verifiers resolve to the same key were two seats for one person, so one key holder could meet an m-of-n quorum alone.Approval bypass#109 (found in #108)
P12BeginTask checked the dispatch table before reading the stored begin record, so a worker whose begin landed and whose answer was lost was refused on retry and never ran.Stuck call: halted worker_lost for an effect that never started#95 design text, 10.4 step 0 (found in #112)
P22DELIVERY_EXHAUSTED was recorded for a retry-safe call whose deliveries were only lost, though a lost delivery may have run its handler; the next call ran under a new once-key scope.Double effect downstream#95 design text, 10.9 and 6.3: only read_only tools record it, an idempotent call halts (found in #112)
T19A known failure was recorded for a side effect whose tool began and did not itself fail (a middleware turned success into an error, a later invocation's refusal, or next still running).Double fire; in a saga, an effect left in place and listed nowhere#117 (found by model 9, #123)
T29"Already ran" was recorded for a tool that never began, when the saga's accepted-arguments write failed.False record#117
T39An earlier attempt of a retry-safe saga step that changes state fired, was cut off with nothing recorded, and its re-run failed: the rollback skipped it.Effect left in place after rollback, listed nowhere#117
T49A success was recorded (and, in a saga, compensated) while a next left running was still in the tool.Effect lands after its compensation#117
T59A retry-safe tool began after its chain returned and its compensation was recorded.Effect lands after its compensation#117
T69A re-drive's cache answer was recorded while an earlier drive's invocation was still in the tool.Effect lands after its compensation#117
(unnamed)9The rollback's re-run stopped on any error, so a result check that rejects every success left the rollback with no end.Stuck rollback#117
L110RecoverLoop visited every unfinished run in id order, halted ones included, so a dead holder's run waited behind the halted runs listed before it (10 ticks with two halted runs and 15 with three, against 3 or 4 after the fix).Slow recovery#126: a second loop drives only runs whose lease lapsed (found in #124)
L210Cancel's turn-boundary check races the claim: a drive past its check claims and fires after run:cancelled landed, with no fault.Fire after cancelRule adopted into P14's design (D1 in api-v1) by #124; implemented by P14 (TestP14Rule03_CheckAfterWonClaim)
L310Cancel and completion race on two keys: Cancel can report a run cancelled that completed, or the run report an answer after Cancel landed first.Wrong verdict reportedAs L2: the first end marker in journal order is the verdict; implemented by P14 (TestP14Rule04_*)
L410Cancel on a saga wrote run:cancelled, an end marker that recovery excludes, so a saga cancelled when no drive would reach a check (or completed after the marker) was never rolled back.Effects never compensatedRule adopted into P14's design by #129: a rollback request run:cancel-requested, then the rollback and run:cancelled; implemented by P14 (TestP14Rule05_*)
L510The per-run tool filter was journaled but not said to apply at dispatch; a turn naming a filtered-out tool (unoffered, or replayed) would fire, with no fault.Filtered tool firesRule adopted by #129: the filter is enforced at dispatch; implemented by P14 (TestP14Rule13_*)
L610Status by one Get per end marker can read run:complete before the run completes and run:cancelled after Cancel lands, and report a completed run cancelled.Wrong status reportedRule adopted by #129: one Load, or the Gets again once a marker is found; implemented by P14 (Status reads one Load; TestP14Rule07_*)
L710Recovery that remembers a not-started run's skip, not its report, never recovers the run once it starts and its holder dies.Run never recoveredRule adopted by #129: run:start read again every pass; implemented by P14 (TestP14Rule15_StartedAfterSkipIsRecovered)
D111BindRollback checked each journaled grant against the one grant bound now, so a saga that delegated under two bound grants (the refusal for an expired grant asks for a live one) could not verify both, and its rollback never ended.Stuck rollback#133: the caller binds every grant the saga delegated under (WithRollbackGrants), and each child grant is checked against its own parent (found in #130)
D211BindRollback dropped the delegated mark, so the rollback's re-run of a retry-safe write in a delegated sub-run passed CallGuard and called the tool after the grant expired.Act past grant expiry#133: keep the mark, and list a refused re-run as an unknown outcome (found in #130)
D311In a plain sub-run of a saga, a failed sub-agent call is an error result, and the rollback skipped error results before recursing, so the sub-agent's writes were neither compensated nor listed.Write left in place, listed nowhere#133: recurse into a sub-agent call whatever its result (found in #130)
S112A handle whose Send started a turn and then failed or paused keeps it open in its own view; once another worker finished that turn, the handle refused every other message with ErrConfig ("a turn for x is still open") and never read the journal again.Session refuses every new message on that handle#137: reload before refusing
S212Two callers on one handle sending one message both drive its run; the second's append started past the slot the first had recorded and its reload had loaded, so the run's turn was recorded twice (and a SendOnce key had two records).Duplicate turn in the history#137: appendTurn returns at once for a run among the loaded turns
S312Against P14's design: Cancel of an open Send turn's run leaves the turn open for ever, so every other message on the session is refused.Session blocked for everRule adopted into P14's contract (rule 16 in api-v1); implemented by P14 (TestP14Rule16_CancelledTurnIsClosed)
S412A turn's run is driven with no lease, so two workers given one message both drive it, each counting only the spend it has seen, and the turn spends up to its budget once per worker.Budget overspent#137: each turn's run is driven under its lease; a worker without it gets ErrTurnContended
Shared late key8Late spend was keyed by a sequence number each driver counted itself, so two drivers wrote one @spend-late key and the second's spend was lost. Found as a suspicion in the #104 re-review; model 8 confirmed it on the old rule.Lost spend#104: a fresh id per spend record (confirmed in #111)
N114Against the notifier design: the count of failed deliveries that raises failing was kept in process memory, so a restart started it at zero, and under a crash loop failing was never raised (overdue still was, from the trail).Lost "notification failing" signalAdopted: the core counts failed rounds from the trail's claimed records; kept as a regression configuration

Models 7 and 8 found no new bug in the rules they check. Their regressions encode bugs earlier reviews found (#103's F3, F4 and F7 for flows; #104's F3, F4 and the lost-turn case for spend), so those rules cannot come back. Model 7's two gate regressions guard rules flow gates were designed with: gate-missing (a gated node run with no gate check) and gate-unscoped (a gate in a loop keyed per node rather than per iteration, so the first iteration's approval lets the next run unapproved) both fail GateHeld. A third, gate-request-order, encodes the one bug #195's adversarial review found: a decision recorded before the gate's request (node keys are predictable) was counted. The model checks that only decisions after the request count; that a counted signature binds the request's input is checked by Go tests (plan/gate_test.go), not by model 7. The other regression configurations of models 1, 1b, 9 and 10 do the same for bugs found by review and testing before the models existed, back to #31 and #58.

Model 7's twenty-five taint-* regressions are not found bugs: they are mutants of the taint design for flows (flow-taint, written before the code), each a rule reverted (no second gate, an unscoped one, node-gate approvals counting for it, a read set lost on resume, in the wrong order, reset per iteration or blind to a child's taint mark, a refusal turned into a skip, read as a decision made or journaled after the node ran, a PreExec skipped, ignored or run on a replay, an idempotent node left untracked, inherited marks ignored or lost on resume, a mark sink not run on a replay, a ResolveHalt that drops the child's marks, marks echoed up a chain, a reverse exclusion that flips the own gate, a policyless inherited flow that starts, a resume that does not compare declarations, SeparateApprovers ignored), so that the rules the implementation must keep cannot be dropped unnoticed.

What runs where ​

WhereWhatTime
Every pull request, the merge queue and main (Models, required)The checker self-test, the PlusCal translation check, and every ci, regress, finding and limit configuration (495: 220 ci, 248 regress, 3 finding, 24 limit), each passing one also run for vacuity, four at a time; on a pull request or a merge queue batch, of the models it changes (on main, every model)3.1 to 12.7 minutes (median 4.9) for every model on the CI runner, start to finish over 40 pushes to main on 2026-10-12 and 13, when the models ran in six parallel shard jobs (now twelve: MODEL_SHARDS in .github/workflows/models.yml). With twelve shards the last 20 successful runs on main (2026-10-25 to 26) took 11.3 to 18.6 minutes, median 15.4, plus one at 85.1; that is the whole workflow's wall time from creation to last update, queue included. The Models job stands for the twelve shard jobs (each shard's timeout 30 minutes)
Nightly and on demand (Models (nightly))The 122 nightly configurations: more faults, more drivers, liveness at two error replies, weak A3 (late commits)About 1 hour 50 minutes on the CI runner (1 hour 40 minutes measured before this split, plus about 7 minutes moved from pull requests, and model 10's four P14 configurations, about 6 minutes on the development machine; model 15's four add about 30 million states in total, about 4 minutes on ten workers on the development machine and not yet timed on the CI runner; job timeout 4 hours)
Nightly and on demand (Explore (full bound))The Go fault-schedule explorations of the claim protocol and of flow lowering at their full bound (BIDE_EXPLORE=1); every pull request runs them at a smaller bound under -race in the Test jobAbout 15 to 22 minutes
Nightly and on demand (Apalache (nightly))spec/tla/check.sh apalache: model 1's inductive invariant (the one-step checks of each scope, the resolver scope's step split in four, and a vacuity check), a bounded symbolic regression that must fail, TLC checks that the invariant holds in every reachable state of three configurations, and a type check of model 9's wrapper (Apalache)One job per configuration (twelve), in parallel with each other and with the TLC nightly job; the time on the runner is given in Apalache results (job timeout 350 minutes)
Every pull request (Lint, required)modelsync and TestProtocolVocabulary (next section)Part of Lint

On a pull request and in the merge queue (against the queue's base), the Models steps check only the models whose directory under spec/tla/ it changes, and the models whose configurations name a changed one in a LIBRARY line (every model when it changes check.sh, tools.lock, .github/scripts/shards.sh or the workflow); otherwise the job reports success without re-checking. TLC reads nothing outside the model's directory and the directories its LIBRARY lines name, and a change to the Go code a model describes must change the model or carry a Protocol-Impact override (the Lint job), so this skips no check whose result could differ. Pushes to main and the nightly always run every model. Workflows: .github/workflows/models.yml and .github/workflows/explore.yml.

What a counterexample looks like. When a property fails, TLC prints the violated invariant (or temporal property) and the shortest sequence of states that reaches it: each state is one atomic step, such as one store round trip, a crash or a cancellation, with every variable's value. spec/tla/check.sh compares the result with the configuration's declared expectation and prints a summary line per configuration; TLC_KEEP_OUTPUT=<dir> keeps the full trace. Traces are short: F1's is 37 states, F2's 22 to 29, T6's 55, L2's 10. A counterexample in the current rules is a bug. It gets a deterministic Go test that fails before the fix, then the fix, then a regression configuration that keeps the old rule failing.

How the models and the code stay in step ​

A model checks the design, not the code. These mechanisms keep the two from drifting apart today (milestone M4, #125):

  • Region markers. Each Go region a model's map names is wrapped in comments that name the model and the model actions it implements, for example // protocol:claims begin Claim ClaimRetry ClaimInsert ClaimNS ... // protocol:claims end. Models 1, 1b, 7, 8, 9, 10, 11, 12, 15, 16 and 17 are marked; models 2 and 13 have no Go code; model 14 has code (agent/notify_*.go) but no markers.
  • The path rule. go run ./internal/tools/modelsync, in the required Lint job, fails a pull request that touches a marked region of a model without changing anything under spec/tla/<model>/.
  • The Protocol-Impact override. A change that leaves the modelled behavior as it is (a rename, a comment, an error message) says so in the description or a commit message: Protocol-Impact: none (<reason>), or Protocol-Impact: <model>[,<model>] none (<reason>). The reason is required, and every override used is shown to the reviewer as a warning annotation.
  • Rename checks. modelsync also fails when a marker, the model-to-code map in spec/tla/README.md and the spec disagree on an action's name, so a rename on any side fails.
  • TestProtocolVocabulary (package agent, run in Lint) checks that the claim code's key constructors and record kinds match the record kinds Claims.tla declares, in both directions, and that each constructor's keys parse back to their kind.
  • Bug-flag regressions. Every historical bug a model can state is a Bug value and a configuration in regress/ that must keep failing with its property (151 today). One that starts passing means the model lost the behavior or a property weakened.
  • The CONTRIBUTING rule. A change to a modelled rule changes the model in the same pull request, and a counterexample in the current rules is reproduced as a deterministic Go test before it is fixed (CONTRIBUTING, Formal models). The pull request template asks the reviewer to confirm the model-to-code map still holds.

What the markers and the map do not yet check is meaning: that each Go function does what its model step says is checked by review. The planned work closes that gap.

Planned ​

The next model work (also on the roadmap): M3 trace validation: the Go test suites emit protocol events under a build tag, and TLC checks that every emitted trace is a behavior of the model, so the models cannot drift from real Go runs (plan, section 6.1). Delegation (model 11) and sessions (model 12), planned here before, are done.

Also planned in the milestones: the rest of M2, a helper (agent/internal/interleave) that turns a TLC counterexample into a deterministic Go test skeleton; and M5, merging and validating the traces of the multi-process HA harness nightly.

What the models do not cover ​

  • Only the bounds checked, except where an inductive invariant holds. TLC checks every behavior within each configuration's bounds and nothing beyond them. Model 1's inductive invariant proves, for two drivers over two processes, AtMostOnce and NotStartedExclusive on one call (attempts 0..3, 8 claim ids) and all four of AtMostOnce, NotStartedExclusive, NoLiveOverride and AtMostOncePerIntent with halt resolution and the caller's second call (attempts 0..3, 6 claim ids), without the approval gate, and, under the lease check, assuming no plain run holds the live attempt at the check (PlainRunIdleAtCheck), at any depth and for any number and mix of faults within the run's 8 (6) claim ids and attempts 0..3 (claim ids are never reused, so this bounds the number of claims) (Apalache results). Typical bounds: two drivers (three in one nightly configuration), one crash, one cancellation, up to two error replies on pull requests and four nightly; model 9, one turn of one or two calls with at most two invocations of a call at once; model 10, one or two recovery workers, up to three runs; model 1b, three approvers and up to three decisions. A bug that needs more is outside the check.
  • The design, not the code, until trace validation lands. The map from model steps to Go functions is reviewed by hand; modelsync checks only names and that marked code changes with its model.
  • Postgres and SQLite store internals. The models assume the store contract (first writer wins per key, prefix-closed reads, ambiguous errors). Whether a store meets it is checked by the storetest conformance suite and the multi-process harness against real Postgres (store/postgres, the required Integration check), not by a model. The store contract and journal header model (plan model 4) is not built.
  • Multi-process traces (M5) and trace validation of any kind (M3).
  • Wall-clock time outside model 10: WithMinHaltAge is encoded as the assumption it rests on.
  • Per-model gaps listed in the README: the bide protocol's call deadline as a clock, push delivery and approvals over the protocol (model 2); a flow input's canonical comparison, the run ID check, and joins (model 7); OnAnswer, Cost and the token budget's stop (model 8); pauses inside a tool and an unregistered tool in a rollback (model 9); a recovery pass's concurrency above 1, sub-runs and sessions (model 10); and the whole-tree token budget bound.

For the full list per model, see What the bounds do not cover and each model's section.

The convergence proof (Rocq) ​

The TLA+ models check bide's protocols within bounds. Governed shared state (the govern package, experimental) rests on a different kind of evidence: a machine-checked proof. gsm's convergence theorem is an axiom-free Coq/Rocq proof in normalization-confluence, checked in that repository's CI on Coq 8.18, 8.20 and Rocq 9.3. Two things tie it to bide:

  • At run time, gsm's Build returns a machine only after a table oracle, Go generated from the proof, re-checks it in-process.
  • In CI, bide's required gsm machine gate (.github/workflows/gsm-gate.yml) builds the two checkers extracted from the proof, from the proof commit and digest-pinned Rocq image gsm pins, and runs them on every machine the governance examples build.

A federation's own conditions, including the event-order checks C1 and C2, are checked by gsm's Go code, not by the proof's checkers. What the proof covers and the exact scope are in the governance guide and known limitations.

Further reading ​

Apache-2.0 licensed.