lockstep — coordination certificates for multi-agent graphs

New here? Start with python examples/12_loop_aware_certificate.py (a 30-second, dependency-light demo), then read See it catch a silent bug just below. To publish, see PUBLISHING.md.

Declare each agent's intent — what shared state it reads and writes — and get a provably-deterministic, maximally-parallel schedule, with collision detection and the minimal fix.

We don't execute the agents. LLMs, tools, and services do the work. This owns the coordination layer: you declare the dependencies (the partial order), and the coordinator proves the result is order-independent — regardless of how the agents happen to be scheduled.

The problem

Multi-agent systems share state (a scratchpad, a memory store, files, a task board). When two agents write the same thing with no order between them, the final state depends on who finished last — a nondeterministic result that passes every per-agent check. The usual fixes are both bad:

• Serialize everything "to be safe" → correct but slow; you throw away all the parallelism.
• Let them run and hope → fast but the output silently varies run to run.

See it catch a silent bug

examples/green_ci_is_lying.py ships two versions of one customer-support graph. They pass the same tests. One is a silent landmine.

app — three checkers append to a messages reducer in parallel. lockstep flags it (exit 1):

CORRECTNESS
  deterministic (order-free)  : False
  order-sensitive reducer race: ['messages']  (concurrent writers into a non-commutative reducer)
SAFETY (retry / at-least-once)
  RETRY-UNSAFE (double-writes): [('check_billing','messages'), ('check_orders','messages'),
                                 ('check_shipping','messages'), ('triage','messages')]

LangGraph merges concurrent reducer writes in a stable-but-arbitrary order, so one run — or twenty — only ever sees one ordering. The result is genuinely order-dependent; your tests simply never schedule the other order.

app_fixed — the same graph, made confluent. lockstep certifies it (exit 0):

CORRECTNESS
  deterministic (order-free)  : True
PERFORMANCE (optimal schedule)
  wave 1 (concurrent)        : ['billing', 'orders', 'shipping']   <- still fully parallel
  critical path               : triage -> billing -> responder      (speedup 1.7x)
SAFETY (retry / at-least-once)
  retry-safe agents           : ['billing', 'orders', 'responder', 'shipping', 'triage']

Same parallelism, now provably deterministic — the fix costs zero waves of speed. That's the whole pitch: green tests lie; lockstep doesn't.

lockstep examples/green_ci_is_lying.py:app --certificate         # exit 1: order-sensitive reducer race
lockstep examples/green_ci_is_lying.py:app_fixed --certificate   # exit 0: deterministic

What it does

You declare agents by reads / writes. The coordinator then:

1. Derives the dependency order (read-after-write) — you never hand-write the schedule.
2. Proves determinism: counts the reachable end-states of shared memory; confluent ⟺ exactly one.
3. Detects collisions: same key, two writers, no order, differing values.
4. Reports the blast radius: log₂(reachable states) bits — and counts correlated collisions as one (the lock: agents contending the same keys resolve together).
5. Prescribes the minimal coordination: the fewest ordering decisions that make it deterministic.
6. Schedules with maximum parallelism: only genuine dependencies serialize; the rest run concurrently.

Quick start

from orchestrator import Orchestrator

orch = (Orchestrator()
        .agent("planner",    writes={"plan": "v1"})
        .agent("researcher", reads=["plan"], writes={"findings": "data"})
        .agent("coder",      reads=["plan"], writes={"code": "impl"})
        .agent("editor",     reads=["findings", "code"], writes={"report": "final"}))

print(orch.analyze().certificate())
# -> deterministic: True; researcher & coder run concurrently (wave 1); a printed certificate.

writes={key: value} — the value is what lets the coordinator see value-agreement: two agents writing the same value to a key do not conflict (no false serialization). Use after=[...] to declare an explicit order when you want one.

Drop it into CI (the lockstep CLI)

The one-call wedge: prove a real LangGraph graph is deterministic, fail the build if it isn't.

pip install -e .                              # installs the `lockstep` command
lockstep app/agent.py:graph                   # exit 0 = deterministic, exit 1 = order-dependent
lockstep app/agent.py:graph --json            # machine-readable verdict for CI dashboards
lockstep app/agent.py:graph --certificate     # the full COORDINATION CERTIFICATE (below)

The coordination certificate (--certificate)

Determinism is one section of a bigger object. --certificate emits the whole thing for a graph — declare what your agents read/write → provably correct, optimally scheduled, and retry-safe (coordination.py):

• Correctness — deterministic? deadlock? plain collisions + the order-sensitive reducer race + the minimal fix. Loop-aware: a conditional back-edge (ReAct / research / reflection loops — most real agents) is iteration, analyzed per loop body and flagged iterative, not a false deadlock; dependencies are control-ordered (a downstream write is never a backward dependency) and the verdict is reproducible.
• Risk — blast radius (log₂ reachable end-states) + the correlated lock.
• Performance — the optimal parallel schedule + the critical path (the chain that caps wall-clock) + speedup.
• Safety — which agents are retry-safe vs corrupt state on retry: an agent writing an accumulating reducer (add_messages / operator.add) double-writes under at-least-once redelivery; idempotent writes (set-union / last-value / max) re-apply cleanly. Derived from the real reducers.

lockstep examples/green_ci_is_lying.py:app --certificate        # non-deterministic + retry-unsafe 'messages'
lockstep examples/green_ci_is_lying.py:app_fixed --certificate  # clean: deterministic, retry-safe
python examples/09_coordination_certificate.py                  # clean / collision / deadlock / real graph
python examples/12_loop_aware_certificate.py                    # a research LOOP: iterative + deterministic, not a deadlock

Machine-readable, for CI gates and dashboards — add --json to get the same four sections as a JSON object with a top-level ok (the gate decision: deterministic and no deadlock — the same verdict the exit code uses):

lockstep app/agent.py:graph --certificate --json        # one object; gate on `.ok`
lockstep a.py:g1 b.py:g2 --certificate --json           # several graphs -> object keyed by target

{
  "ok": false,
  "correctness": { "deterministic": false, "deadlock": [],
                   "order_sensitive_fanout": [{ "resource": "messages", "writers": ["check_orders", ...] }],
                   "collisions": [], "minimal_fix": [] },
  "risk":        { "reachable_states": 1, "blast_radius_bits": 0.0 },
  "performance": { "waves": { "1": ["check_billing", ...] }, "critical_path": [...], "speedup": 1.6667 },
  "safety":      { "retry_unsafe": [["triage", "messages"], ...], "retry_safe": ["responder"] }
}

A CI gate is then one line — jq -e '.ok', or just trust the exit code (1 when any target's ok is false).

Path-aware. Conditional edges create mutually-exclusive execution paths — only one branch runs. The certificate enumerates those paths (exactly as certify does), analyzes each independently, and aggregates, so its verdict always agrees with certify: two writers that live on different branches are never reported as racing, and a real race is attributed to the branch it lives on (with the other branch certifying clean). The aggregate sections are the AND/union/worst-case over paths; when there's more than one path, a paths array (JSON) and a PER-PATH block (text) give the per-branch breakdown. A graph with no conditional edges has one path and the certificate is exactly the whole-graph view.

Loop-aware. Most real agents loop (ReAct, research, reflection). A conditional back-edge is iteration, not a dependency deadlock: the loop is cut at the router edge and the loop body is analyzed as a DAG (the certificate flags it iterative). Dependencies are control-ordered — a reader is ordered only after writers that are its control-ancestors — so a channel written inside the loop and again at a finalize step is sequential reassignment, not a race. Races inside a loop body are still caught, and the verdict is reproducible (hash-seed-independent — a determinism tool whose own output is deterministic). Validated on real looping agents (local-deep-researcher, react-agent, data-enrichment, …); python examples/12_loop_aware_certificate.py is a dep-free demo and test_loop_aware.py locks it in.

Audit a real repo without installing its world. audit_real_repo.py introspects an external project's compiled graph after stubbing its runtime LLM/search libraries (which never affect topology), so you can certify a third-party agent without its API keys or heavy dependencies:

python audit_real_repo.py path/to/repo/src mypkg.graph:graph    # full certificate + multi-channel audit

python examples/10_path_aware_certificate.py    # false-positive removed (A); a race localized to one branch (B)

See the bug it catches before anyone hits it:

python examples/green_ci_is_lying.py          # 20/20 runs identical, yet provably 3 possible decisions
lockstep examples/green_ci_is_lying.py:app       # FAIL: 'messages' reducer, 3 writers -> 2.58 bits
lockstep examples/green_ci_is_lying.py:app_fixed # PASS: disjoint registers + fixed priority

Drop it into CI (GitHub Action)

A reusable composite Action ships in action.yml. On every PR it posts a sticky Coordination Certificate comment — a summary table (verdict / blast radius / speedup / retry-unsafe per graph) plus a collapsible per-graph breakdown — writes the same report to the job summary, and fails the check when any graph is non-deterministic or deadlocked. The comment updates in place (one comment, not a pile), and the check is static — nothing is executed — so it's safe in CI and catches the silent order-dependence a single .invoke() (or 20) can't.

permissions:
  contents: read
  pull-requests: write          # so the action can post/update the certificate comment
steps:
  - uses: actions/checkout@v4
  - uses: your-org/lockstep-agents@v1
    with:
      targets: "app/agent.py:graph"
      install: "pip install -e ."   # so your graph can import your project

Copy examples/ci-workflow.yml (consumer template) into your repo's .github/workflows/; .github/workflows/lockstep.yml is this repo dogfooding the Action on its own example. The renderer is lockstep-pr (certificate → Markdown + comment) and lockstep-pr-comment (upsert a sticky PR comment from any Markdown), both stdlib-only.

Multi-channel audit (--audit)

Coordination is one channel. --audit runs a fleet of scoped channels over the graph and aggregates one verdict — separate channels, so breadth never dilutes the sound one (channels.py):

• coordination — the sound anchor: order-independence, deadlock, collisions, schedule, retry-safety.
• code-safety — untrusted agent state flowing into a dangerous sink (os.system/eval/execute/subprocess) inside a node, unsanitized — the prompt-injection / unsafe-tool-call shape coordination structurally can't see (code_safety.py).

lockstep examples/11_multichannel_audit.py:app --audit        # coordination PASS, code-safety FAIL (injection)
lockstep examples/11_multichannel_audit.py:app_safe --audit   # both pass (state is sanitized)
lockstep examples/11_multichannel_audit.py:app --audit --json # {ok, channels:[{name, ok, findings}]}

The two channels are complementary: on green_ci_is_lying.py:app coordination fails (reducer race) while code-safety is clean; on 11's app coordination is clean while code-safety catches the injection. New channels slot in through the same interface (and arbitrate at the seam where they contend on shared evidence).

Run the examples

python examples/01_parallel_research.py     # clean workflow: derived order + parallel waves
python examples/02_collision_detected.py    # two agents write one key -> caught + minimal fix -> deterministic
python examples/03_lock_blast_radius.py      # 3 correlated collisions -> 1 bit blast radius, ONE fix closes all

Collision (example 2): two summarizer agents write summary unordered with different values → deterministic: False, blast radius 1 bit, fix run summarizer-A before summarizer-B. Declare it → deterministic: True.

Lock (example 3): two research agents write the same 3 keys → a naive per-key view says 8 possible states, 3 fixes; the coordinator sees they're locked → 2 states (1 bit), one decision fixes all three.

Ingest a real agent graph, emit an executable plan

adapters.py ingests an existing multi-agent spec; runtime.py turns the verdict into an executable wave plan and runs it.

• from_graph(graph) — a LangGraph/StateGraph-style graph (nodes that read/write shared-state channels
  • edges). The fit is exact: a node's state updates are writes, the channels it consumes are reads, edges are explicit ordering. Two parallel nodes writing the same channel — the classic "needs a reducer / order-dependent fan-out" — is a contention collision the coordinator catches before the graph runs.
• from_spec(spec) — a portable JSON form any framework (CrewAI tasks+context, Autogen channels, a tool-call manifest) can emit.
• runtime.execute(orch, impls) — run the agents wave by wave against shared state; runbook(orch) prints the plan.

python examples/04_adapter_langgraph.py

Beyond LangGraph — CrewAI / OpenAI Agents / AutoGen

The core engine is framework-agnostic — it needs only each unit of work's reads/writes (+ ordering). LangGraph gets free AST introspection because it exposes typed state channels; other frameworks map through framework_adapters.py (from_crewai, from_openai_agents) or the portable from_spec. One thing falls out cleanly: the engine's value tracks how much concurrency a framework's metaphor exposes.

python examples/08_beyond_langgraph.py   # one engine across four metaphors

Handoffs and sequential crews are serial by construction → the engine correctly says "deterministic, nothing to fix" (a true, useful null). Parallel/async metaphors expose genuine races → the engine quantifies the blast radius and prescribes the fix. (The adapters are verified against real objects — crewai 1.14.7 and openai-agents 0.17.5, both handoff forms — in a throwaway venv; the from_spec demo runs on pure stdlib.)

ingests a planner→{web_researcher, doc_researcher}→synthesizer graph where both researchers write research in parallel. The coordinator reports not deterministic (blast radius 1 bit) up front; running every legal schedule yields 2 different reports (the silent order-dependence LangGraph would hide); the prescribed fix collapses it to 1 outcome across all schedules — operational 2 → 1 matching the proof 2 → 1. (A LangGraph reducer also resolves it only if the reducer is commutative; a non-commutative reducer like operator.add/add_messages merely hides the order-dependence rather than removing it — see certify below.)

True introspection of a real LangGraph (langgraph_adapter.py)

from_langgraph(state_graph) points at an actual StateGraph and extracts everything automatically — no hand declaration: nodes + their functions, edges, state channels and which have reducers, and each node's reads/writes inferred by AST from the function body (state['k'] / state.get('k') = read; keys of a returned dict = write — the same analysis as the notebook tool).

python examples/05_langgraph_introspect.py

builds two real graphs and checks the static verdict against LangGraph's actual runtime: a plain research channel written by two parallel nodes → coordinator says non-deterministic (collision), and LangGraph really throws InvalidUpdateError: ... can receive only one value per step — caught before the graph runs; the reducer channel (Annotated[list, add]) → runs without error, but operator.add is order-sensitive, so the merged result is silently order-dependent (1 bit) — a single .invoke() hides it behind LangGraph's stable-but-arbitrary task-path sort. The simple LWW view calls a reducer "merge-safe"; certify (below) probes the reducer and flags the silent case. A reducer that runs ≠ a deterministic graph.

One-call CI check, path-aware: certify(graph)

from certify import certify
ok = certify(my_state_graph)        # prints a report; returns True/False (exit 0/1 as a script)

Conditional edges (add_conditional_edges) create multiple execution paths; alternative branch targets are mutually exclusive, so certify analyzes each path independently — a collision counts only when both writers run on the same path. The graph is certified deterministic iff every path is confluent.

python examples/06_conditional_edges.py

• Graph 1 — a router to two branches that both write result. The naive view false-flags a collision; path-aware certify enumerates the 2 paths (each confluent) → PASS, and LangGraph really runs it fine.
• Graph 2 — a true parallel fan-out collision → FAIL with the fix, and LangGraph really errors.

The static verdict matches real runtime on both (pass and fail).

certify also catches non-commutative reducer fan-out (the silent case)

certify flags two ways a graph loses determinism, per path: (1) a plain-channel collision (two writers, no order — LangGraph errors on this); and (2) ≥2 concurrent writers into an order-sensitive reducer channel. The second is the dangerous one: LangGraph does not check reducer commutativity, and operator.add-on-lists / add_messages (the two most common reducers) are non-commutative, so a parallel fan-out into them is order-dependent — yet it runs without error, masked by a stable-but-arbitrary task-path merge.

Each reducer is classified by identity/name and, when the channel type is known, probed exactly with distinct sentinels (value-independent) — so the blast radius in bits is exact, and even custom reducers are resolved either way (a custom sorting-merge is proven confluent; a custom prepend is proven order-dependent). A reducer whose writers are already ordered is safe (the merge order is fixed) — flagged only on genuine concurrency.

python examples/07_certify_reducers.py   # 5 real graphs: order-sensitive/commutative × fan-out/serial × custom

(Implementation: reducer_commutativity.py — classify + the exact probe, generalizing the value-agreement quotient from "same value" to "same reducer output". The probe canonicalizes set/dict accumulators order-free, because repr of a set can vary with insertion order under hash collisions and would falsely flag a commutative merge.)

Honest scope (current): AST-inferred I/O handles literals, out={} builds, {**state,...} spreads, state[k]= mutation, and conditional returns; a node that builds its update dict dynamically (e.g. return {var: ...} or return helper(...)) is reported as unknown-writes (flagged, not silently missed). Conditional edges with a path-map are modeled; a router with no path-map (dynamic any-node target) is not. And it certifies coordination, never the agents' runtime semantics. Sound, not complete.

Honest scope — sound, not complete

It reasons about the declared reads/writes and the values you declare. That means:

• ✅ Every collision it reports is real (given the declared effects); the schedule respects every dependency; the confluence count is exact (proven via the chromatic / acyclic-orientation theory it's built on).
• ⚠️ It cannot see runtime semantics — what an LLM agent actually does. If an agent writes a key it didn't declare, or its real output value differs from the declared one, that's outside the model (garbage-in). It certifies the coordination, not the agents' correctness. Declare effects honestly.

This is the mature, counting/value-aware descendant of the triadic envelope (K/C/B + ledger). See docs/DESIGN.md for the framework mapping and the lineage.