Run two copies of an agent against the same durable log and they will, at some point, see the same events in a different order. A retry lands late. A crash and resume replays a step. Two workers in different processes race. If the state those agents share depends on the order of events, the copies disagree, and nothing in the log tells you which one is right.

Most agent frameworks answer this with eventual consistency, which in practice means the system converges if the operations happen to commute, and hope otherwise. Bide answers it with a theorem: for the governed-state tier, the order steps replay in cannot change the result. That claim is machine-checked in Coq/Rocq, axiom-free, and checkers extracted from that proof re-certify the engine’s step tables before it hands you a machine.

This post is about what that proof says, how it is checked, and where it stops. The last part matters as much as the first. A determinism guarantee is only useful if you know its exact boundary.

The claim. Given the same set of events, every processor that applies them in any order reaches the same valid state. That is order-independent convergence of the replay. It is not “agents always agree on what to do,” and it does not cover the external world: a payment or an email is protected by a different mechanism, covered below.

Determinism means path-independence

A deterministic system, in the sense that matters for replicated state, is one where the result is a function of the inputs and not of the path taken through them. Thermodynamics calls this a state function. Algebra calls it a canonical form. Database people call it convergence. Everyone who builds replicated systems eventually needs it.

There are three established ways to get it without coordination, and they nest:

flowchart LR subgraph nc["Normalization confluence"] direction LR subgraph ic["Invariant confluence"] subgraph crdt["CRDTs"] c1["concurrent operations
commute"] end i1["every ordering preserves
invariants, no repair"] end n1["operations may BREAK invariants;
compensation repairs them,
and the repaired results converge"] end style nc fill:#3A4A5C,stroke:#6b7280,color:#f0f0f0 style ic fill:#3A4C43,stroke:#6b7280,color:#f0f0f0 style crdt fill:#4C4538,stroke:#6b7280,color:#f0f0f0

CRDTs buy convergence by restricting operations so that concurrent ones always commute. Invariant confluence asks that every ordering preserve the invariants, so nothing ever needs repair. Both are strong requirements, and real business logic violates them constantly: an order ships before its payment clears, two withdrawals race past a balance floor, inventory goes negative for a moment.

Normalization confluence is the regime this work identifies. It allows operations that individually break invariants, as long as a compensation step repairs them and the repaired results come out the same in any order. Convergence becomes a property of the whole rewrite system (apply an event, then normalize), not of the operations themselves. CRDTs are the special case where no repair is ever needed, and that inclusion is itself machine-checked and strict: there are convergent governed machines no CRDT can express.

The theorem, in two conditions

Model a registry as a state, a set of invariants (predicates that define “valid”), and a compensation that repairs a violation. Applying an event and then repairing until valid is a rewrite step. Two conditions make the whole system converge.

Well-founded compensation (WFC). Repair always terminates. Formally, there is a potential \(\Phi\) that strictly decreases on every repair of an invalid state. Since \(\Phi\) lives in a well-founded order, it cannot decrease forever, so every compensation chain is finite. This is a termination measure, the discrete cousin of a Lyapunov function.

Compensation commutativity (CC). Repair does not depend on order locally. Two parts:

  • CC1: two independent events, each followed by repair, commute.
  • CC2: repairing before an event or after it gives the same normalized result.

Then a classical result does the rest. Newman’s Lemma says a rewrite system that terminates and is locally confluent is globally confluent, and a confluent terminating system has a unique normal form. WFC is termination. CC is local confluence. Unique normal form is exactly “same events, any order, same final state.”

flowchart TB s["state s with
pending events e1, e2"] a["apply e1, then repair"] b["apply e2, then repair"] j["one normal form"] s --> a s --> b a -->|"apply e2, repair"| j b -->|"apply e1, repair"| j style s fill:#3A4A5C,stroke:#6b7280,color:#f0f0f0 style a fill:#3A4C43,stroke:#6b7280,color:#f0f0f0 style b fill:#3A4C43,stroke:#6b7280,color:#f0f0f0 style j fill:#4C4538,stroke:#6b7280,color:#f0f0f0

The diamond above is the shape of local confluence: any two diverging single steps can be rejoined. Newman’s Lemma lifts that local diamond to the whole system, so every divergence of any length rejoins.

As stated, CC1 asks every pair of events to commute. That is more than real replicas need, because delivery is usually causal: an event is applied only after the events it depends on, and only concurrent events (neither happened before the other) can arrive in either order. The development also proves the convergence theorem under that weaker requirement. CC1 is needed only for events that can be pending together, and under causal delivery causally ordered events never are, so they never need to commute. Compensation interleaves exactly as before.

That result is also what pins down the relationship with CRDTs. Standard op-based CRDTs, which require only concurrent operations to commute and assume causal delivery, converge as an instance of it. The converse holds too: a system with no compensation (repair is the identity) meets the causal convergence condition if and only if it is an op-based CRDT. With both directions proved, the compensation-free fragment of normalization confluence is exactly the op-based CRDTs, and everything outside it is what compensation buys.

What it looks like in code

The reference implementation is gsm, a Go library. You declare variables, invariants with their repairs, and events. Build verifies WFC and CC before it gives you a machine, and refuses to build one that could diverge.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
r := gsm.NewRegistry("order_fulfillment")

// Facts: each event records one fact and reads nothing else.
paid := r.Bool("paid")
shipRequested := r.Bool("ship_requested")
cancelled := r.Bool("cancelled")

// Outcome: derived from the facts by compensation, never written by an event.
status := r.Enum("status", "open", "shipped", "cancelled")

// The business rule: what the status must be, given the facts.
outcome := func(s gsm.State) string {
    switch {
    case s.GetBool(cancelled):
        return "cancelled" // cancellation wins, in every order
    case s.GetBool(paid) && s.GetBool(shipRequested):
        return "shipped" // ship only once paid
    default:
        return "open"
    }
}

r.Invariant("status_matches_facts").
    Watches(paid, shipRequested, cancelled, status).
    Holds(func(s gsm.State) bool { return s.Get(status) == outcome(s) }).
    Repair(func(s gsm.State) gsm.State { return s.Set(status, outcome(s)) }).
    Add()

r.Event("process_payment").Writes(paid).
    Apply(func(s gsm.State) gsm.State { return s.SetBool(paid, true) }).Add()
r.Event("request_shipment").Writes(shipRequested).
    Apply(func(s gsm.State) gsm.State { return s.SetBool(shipRequested, true) }).Add()
// cancel_order records `cancelled` the same way

machine, report, err := r.Build() // verifies that every ordering converges
if err != nil {
    panic(fmt.Sprintf("convergence not guaranteed: %v\n%s", err, report))
}

// Replica A sees the shipment request first; the order stays open until payment.
a := machine.NewState()
a = machine.Apply(a, "request_shipment") // status=open
a = machine.Apply(a, "process_payment")  // status=shipped: compensation derives it

// Replica B sees the same events in the other order.
b := machine.NewState()
b = machine.Apply(b, "process_payment")
b = machine.Apply(b, "request_shipment")

fmt.Println(a.Get(status), b.Get(status), a.ID() == b.ID()) // shipped shipped true

Events record facts; the invariant derives the outcome. A shipment request that arrives before payment leaves the order open, because nothing ships unpaid. When payment lands, the status no longer matches the facts, and compensation repairs it to shipped. In the other order, the same repair fires when the shipment request lands instead. I ran this example against gsm’s current main: Build passes (24 states, maximum repair depth 1, all three event pairs checked by brute force, tables certified by the table oracle; the rules oracle does not run here, because these rules are closures), both replicas print shipped, and their states have the same ID. All six orderings of the three events also reach one identical state (cancelled, since cancellation wins). Build proved that before the first event ran; at runtime each step is a table lookup.

Two verification paths exist. For small machines, Build enumerates the finite state space and checks every pair. For large ones, events that write disjoint variables commute without enumeration (a footprint argument), and BuildCompositional certifies machines whose global state space is too large to enumerate.

How the proof is checked

A convergence claim in a README is easy to write. The point of this work is that the claim is checked by a machine and can be checked again by anyone. Four layers stack up.

flowchart TB subgraph proof["Coq/Rocq development (axiom-free)"] nw["Newman's Lemma"] gov["Convergence theorem
from WFC + CC"] snd["Soundness of gsm's checks
(termination, footprint CC)"] def["Non-vacuity and
discrimination checks"] end subgraph ci["CI gate, every change"] tc["Coq 8.18 + Coq 8.20 + Rocq 9.3"] pa["Print Assumptions on 729 theorems:
Closed under the global context"] end subgraph engine["gsm build"] go["Go verifier: WFC + CC"] tables["step tables + combinator rules"] out["machine returned only if certified;
otherwise an error (fail closed)"] end subgraph oracles["Extracted oracles, generated as Go, run in-process"] o1["table oracle: re-checks the tables
(Build, SynthesizeWith,
each BuildCompositional component)"] o2["rules oracle: recomputes convergence
from combinator rules
(Build, under a work cap)"] end proof --> ci proof -->|"extraction"| oracles go --> tables tables --> o1 tables --> o2 o1 --> out o2 --> out style proof fill:#3A4A5C,stroke:#6b7280,color:#f0f0f0 style ci fill:#3A4C43,stroke:#6b7280,color:#f0f0f0 style engine fill:#4C4538,stroke:#6b7280,color:#f0f0f0 style oracles fill:#4C3A3C,stroke:#6b7280,color:#f0f0f0

1. The theorem is proven, not tested. Newman’s Lemma is mechanized from scratch with no library dependencies. The convergence theorem takes WFC and CC as hypotheses and proves termination (a lexicographic measure over the pending events and the potential), local confluence (all three critical-pair cases), and unique normal forms.

2. “Axiom-free” is checked, not asserted. A proof assistant will happily accept a proof that leans on an unstated axiom or an admitted lemma. The CI gate compiles the development and runs Print Assumptions on 125 named theorems. Every one must report Closed under the global context: no axioms, no admits. The gate runs on three toolchains, Coq 8.18, Coq 8.20, and Rocq 9.3, so the result does not depend on one version’s quirks.

3. The proof is defended against being empty. A proof that compiles can still be weak in two ways a compiler will not catch. Its hypotheses could be unsatisfiable, in which case the theorem is about nothing. Or the property it proves could be true of everything, in which case proving it says nothing. The development rules out both: a concrete registry discharges every hypothesis of the convergence theorem with no axioms (so the result holds unconditionally for a real system), and a concrete relation is proven not confluent (so “confluent” actually discriminates).

4. The proof checks the engine. gsm’s verifier is ordinary Go, and ordinary Go has bugs. So the checkers extracted from the proof run inside gsm as a fail-closed gate. They are generated as Go from the Coq/Rocq extraction, not written by hand. The table oracle re-checks the step tables gsm produced on every success path: Build, SynthesizeWith and BuildOrSynthesize, and each component of a BuildCompositional machine. If it does not certify the tables, you get an error and no machine. The rules oracle ignores the tables and recomputes convergence directly from the declared rules. Build also runs it when every rule is inspectable combinator data rather than an opaque closure and the check fits under a work cap (\(2^{29}\) steps); Report.Assurance records which oracles certified a machine. So a bug in gsm’s Go verifier cannot hand you a machine whose tables do not converge.

The gate has edges. The table oracle trusts that the tables are what your rules compute, since gsm runs your closures to produce them, and it trusts Rocq’s extraction, the generator that emits the Go, and the Go toolchain. For a BuildCompositional machine, the claim that events in different components commute rests on gsm’s footprint check, which the oracle does not see. A federation of registries is not oracle-certified as a whole: each component registry is rebuilt with Build and gated, but the federation-level checks (the morphism condition, acyclicity and topological order, the iteration of monotone cycles, certificate digests) are gsm’s Go code. Separately, gsm’s CI builds both checkers as OCaml binaries and cross-checks every machine its test suite passes to Build against them.

Reproduce it yourself. Nothing here depends on trusting a badge.

git clone https://github.com/blackwell-systems/normalization-confluence
cd normalization-confluence/coq
./verify.sh

The script builds every module and fails unless all 729 audited theorems are closed under the global context.

Where this lives in Bide

Bide is a Go library for durable AI agents. Its pitch is four guarantees derived from one append-only journal, and convergent shared state is the fourth:

GuaranteeMechanism
Side effects fire at most once, even across a crashattempt markers written before non-idempotent calls, and a halt when an outcome is unknown
Thousands of concurrent durable runs in one processa library over a store you already run, not a cluster
A cryptographically verifiable audit trailRFC 6962 Merkle proofs, checkable offline
Provably convergent shared stategsm, backed by the proof above

The governed-state tier is how independent agents share state without a single writer. Each agent’s actions become governed events; gsm proves, at build time, that every interleaving of them reaches the same valid state. At runtime that is a table lookup.

The integration test that exercises it at scale drives up to 10,000,000 governed agents, 2,048 at a time, through random, invariant-violating orders. Every run breaches a capped invariant and is compensated, and the test asserts that every agent converges to the same valid normal form and produces an audit proof that verifies offline. It runs in one process with a flat live heap of about 3 MB, at roughly 12,500 agents per second. It is a framework-level test (stub model, in-memory store), so it measures the governance and audit machinery, not a live model or a production database.

The first guarantee is the one people usually mean by “deterministic agents,” and it is measured rather than proven. Bide’s chaos benchmark drives a non-idempotent charge through every crash point and counts how many times it actually executes:

FrameworkmaxFiredResult
Bide1at-most-once held
trpc-agent-go6double-charged
adk-go4double-charged
langchaingo64double-charged
eino64double-charged

The two guarantees cover different territory, and the boundary between them is exact. Confluence governs the internal state that replays from the log. It says nothing about a charge that already left the process. That is what the journal’s attempt markers handle: if a side effect’s outcome was never recorded, the resumed run stops for a human or a reconciler instead of guessing. Determinism inside, at-most-once at the edge.

Many registries, and where coordination is actually needed

One registry is rarely the whole story. Real systems connect several: a manufacturer’s specifications constrain a supplier, a policy registry constrains a workflow. The federated results extend convergence across a network of registries connected by morphisms, where one registry’s normal form fixes part of another’s state.

The structure splits two properties that are easy to conflate, and both are mechanized:

  • Repair composes freely. On an acyclic network, authority flows from sources to targets and the federated normal form is the same for every topological order of the registries. On a monotone cycle, where repair only moves values up a lattice, the network reaches a least fixed point by any fair asynchronous schedule (given that every registry is valid at the bottom of the lattice).
  • Event order costs two local checks. That the repaired state is unique does not make event order irrelevant: a target event can read a shared value that the morphism later overwrites, so two orders can end differently even when every registry is correct on its own. Two per-edge conditions close the gap. C1: a target event commutes with every source-driven change to its shared part. C2: two target events still commute with the morphism repair between them. Together they are sufficient, they are exact at the states a run can reach, and the same checks suffice on monotone cycles. gsm runs both at build time.
  • Other cycles need coordination, and the theory says exactly where. For cycles whose morphisms relabel values losslessly (a group acting on itself), the obstruction is the holonomy of each cycle: the composite of the relabelings going around it. Pick a spanning tree rooted at an authority. A consistent global state exists if and only if every fundamental cycle has trivial holonomy, and the edges that must be coordinated are exactly the ones whose cycles do not. The normal form is then unique given the root, and a different root can give a different one, so the plan has to name it.

That last result refines the CALM theorem, which tells you whether coordination can be avoided for a whole problem. This one tells you where: put consensus on the obstructing cycles only and run everything else coordination-free. It holds for any group of relabelings, abelian or not, and the non-abelian case matters. A parity-style check can call a cycle consistent when a three-way relabeling around it is not, and the development proves a concrete case where sizing coordination by an abelian invariant under-provisions.

Roadmap, not shipped. gsm today rejects non-monotone cycles and, when asked, plans coordination that breaks every cycle. The holonomy result says lossless round-trips (a copy loop, an exact unit conversion, a bijective schema map in both directions) need no coordination at all. A design for that sharper plan is in gsm’s design notes; the theorems it rests on are proven, the feature is not built yet.

Exactly where the proof stops

A determinism guarantee you cannot bound is a liability, because someone will apply it where it does not hold. Here is the boundary.

StatusWhat
Machine-checked, axiom-freeNewman’s Lemma; the single-registry convergence theorem and its exact converse (with canonical repair, unique normal forms iff CC holds at reachable states), for any well-founded repair potential, so finite state is not required; soundness of gsm’s termination and footprint checks; both extracted oracles; convergence under causal delivery, where only concurrent events must commute; the compensation-free fragment as exactly the op-based CRDTs, with the inclusion of CRDTs strict; at-least-once delivery (duplicates are absorbed exactly when the governed step is idempotent); federation as a limit, its normalizer as the retraction onto it, and order-independence for acyclic networks; event order across registries (C1 and C2, exact at reachable states, also on monotone cycles); monotone-cycle convergence under the ascending chain condition; soundness of coordinated cycles given an authority root; the cohomological completion on arbitrary graphs, the cycle-basis criterion, \(H^1\) as tuples of fundamental holonomies modulo simultaneous conjugation with rank \(\lvert E \rvert - \lvert V \rvert + 1\), the \(S_3\) separation, and the non-invertible case as a fixed-point condition on the loop composite
Proven on paper, not mechanizedthe rank of the obstruction on the full nerve of overlaps, where triple overlaps add relations that can lower it; the sheaf assembly of certificates; the asymptotic complexity bound
Cited, not claimedthe complexity of the global minimum coordination (the group feedback edge set problem: NP-hard in general, fixed-parameter tractable in the size of the coordinated core)
Outside the guaranteeexternal side effects (handled by the journal, not by confluence); delivery (the theorems assume every replica eventually sees the same event set, and the causal results assume causal delivery; how a system achieves either is not covered); continuous state, where convergence needs a different argument entirely

The last row is not a footnote. The theory is about discrete state. It extends to infinite discrete domains, but continuous dynamics (physical systems, optimization landscapes) can have many attracting states, and no amount of local confluence makes a multi-basin landscape converge to one answer. If someone tells you their continuous system “converges deterministically” by analogy to results like these, the analogy is the part to check.

Why this matters now

Agents are moving from assistants you watch to workers you leave running. An unattended worker that touches money, records, or anything under audit has to be safe to crash, safe to replay, and explainable after the fact. Replay safety comes down to determinism, and determinism has usually been an empirical property: tested, believed, occasionally violated in production.

It does not have to be. For the class of systems this covers, convergence is a theorem you can check on your own machine in one command, and the same proof certifies the engine that enforces it. That is the standard I think agent infrastructure should be held to wherever the stakes are real: claims you can verify, with the edges written down.

Further reading