Metadata-Version: 2.4
Name: lockstep-agents
Version: 0.1.0
Summary: Coordination certificate for multi-agent (LangGraph) systems: prove your agent graph is deterministic, deadlock-free, loop-aware, optimally scheduled, and retry-safe — static analysis, CI-ready.
Author-email: Ryan Thrower <ryanthrower@proton.me>
License: MIT
Project-URL: Homepage, https://github.com/rthrower1/lockstep-agents
Project-URL: Repository, https://github.com/rthrower1/lockstep-agents
Project-URL: Issues, https://github.com/rthrower1/lockstep-agents/issues
Project-URL: Funding, https://venmo.com/u/Ryan-Thrower-2
Keywords: langgraph,multi-agent,agents,determinism,confluence,ci,llm,reducer
Classifier: Development Status :: 4 - Beta
Classifier: Intended Audience :: Developers
Classifier: License :: OSI Approved :: MIT License
Classifier: Operating System :: OS Independent
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3.9
Classifier: Programming Language :: Python :: 3.10
Classifier: Programming Language :: Python :: 3.11
Classifier: Programming Language :: Python :: 3.12
Classifier: Topic :: Software Development :: Quality Assurance
Classifier: Topic :: Software Development :: Testing
Requires-Python: >=3.9
Description-Content-Type: text/markdown
License-File: LICENSE
Provides-Extra: langgraph
Requires-Dist: langgraph>=0.2; extra == "langgraph"
Dynamic: license-file

# lockstep — coordination certificates for multi-agent graphs

[![Coordination Certificate](https://github.com/rthrower1/lockstep-agents/actions/workflows/lockstep.yml/badge.svg)](https://github.com/rthrower1/lockstep-agents/actions/workflows/lockstep.yml)

> **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`](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`](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):**

```text
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):**

```text
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.**

```bash
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

```python
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.

```bash
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`](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.

```bash
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):

```bash
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
```
```jsonc
{
  "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`](test_loop_aware.py) locks it in.

**Audit a real repo without installing its world.** [`audit_real_repo.py`](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:

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

```bash
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:

```bash
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`](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.

```yaml
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`](examples/ci-workflow.yml) (consumer template) into your repo's
`.github/workflows/`; [`.github/workflows/lockstep.yml`](.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`](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`](code_safety.py)).

```bash
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

```bash
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.

```bash
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`](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.**

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

| framework / pattern | metaphor | verdict |
|---|---|---|
| OpenAI Agents — handoff chain | handoffs (serial) | confluent — nothing to coordinate |
| CrewAI — sequential process | roles+tasks (serial) | confluent — nothing to coordinate |
| CrewAI — async parallel tasks | async tasks (parallel) | order-dependent — caught, 1 bit |
| AutoGen — group-chat tool round | group chat (parallel) | order-dependent — caught, 1 bit |

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).

```bash
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)`

```python
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.

```bash
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.

```bash
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`](docs/DESIGN.md) for the framework mapping and the lineage.
