Skip to content

S-Bus: Automatic Read-Set Reconstruction for Multi-Agent LLM State Coordination

🕒 Published (v1): 2026-05-16 00:00 UTC · Source: HuggingFace · link

Why this paper was selected

S-Bus: automatic read-set reconstruction preventing multi-agent structural race conditions

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

S-Bus is an HTTP middleware that prevents Structural Race Conditions (SRCs) in concurrent multi-agent LLM systems by automatically reconstructing each agent's read set from ordinary HTTP GET traffic via a server-side DeliveryLog, requiring zero changes to agent SDKs. It applies optimistic concurrency control (OCC) over shared natural-language state and formalizes the resulting consistency property as Observable-Read Isolation (ORI), a partial causal consistency restricted to the HTTP-observable fraction of reads.

Problem

Concurrent LLM agents sharing mutable natural-language state produce SRCs: two agents read the same shard at version \(v\), generate independent deltas, and both commit without re-reading after the first commit — silently overwriting each other. Production multi-agent frameworks (LangGraph, CrewAI, AutoGen, MetaGPT, etc.) provide no write-ownership semantics over shared state; conflicts are detected post-hoc or not at all. Cemri et al. document consistency errors as 23–31% of LangGraph production failures.

Method

S-Bus interposes as an HTTP middleware between agents and a shared shard registry. Its core mechanism is the DeliveryLog: a per-agent, server-side log that records every (shard_key, version) pair delivered via HTTP GET. At commit time, the Atomic Commit Protocol (ACP) validates the DeliveryLog against current shard versions; if any previously-read shard has advanced, the commit is rejected with HTTP 409 (CROSS_SHARD_STALE), forcing the agent to re-read and regenerate.

This yields Observable-Read Isolation (ORI): a projection-based consistency model over the observable read fraction \(R_{obs}\). Formally, ORI prevents anomalies G0, G1a, G1b, and G2-item over \(R_{obs}\), but permits write-skew (G2) over the hidden fraction \(R_{hidden}\) and G3 globally, placing ORI strictly between Read-Committed and Snapshot Isolation in Adya's lattice. The DeliveryLog is architecturally a scope-restricted COPS-style causal log adapted to the HTTP/1.1 (FIFO-per-connection) assumption (Assumption A1). The system targets the dedicated-shard topology: each agent owns a distinct write key and reads from shared reference shards; single-shard collaborative writing is explicitly out of scope.

Three-tier mechanized evidence: TLAPS proves READ_SET_SOUNDNESS and ORI_COMMIT_SAFETY for arbitrary \(N_{agents}\) (687/687 obligations, modulo one retained typing axiom); TLC exhaustively explores 20,763,484 states at \(N=3\) and 2,811,301 at \(N=4\) with zero violations; Dafny discharges 9 inductive soundness lemmas (19 obligations). Rust implementation refinement is empirical only.

Key Contributions

  • (C1) DeliveryLog mechanism for automatic HTTP-traffic-based read-set reconstruction; formalization of ORI with three-tier mechanized verification (TLAPS + TLC + Dafny).
  • (C2) Empirical safety parity with production OCC backends (PostgreSQL 17 SERIALIZABLE, Redis 7 WATCH/MULTI) across 884,110 total commit attempts with zero Type-I (structural) corruptions; cross-backbone replication on gpt-4o-mini, Anthropic Haiku 4.5, and Google Gemini 2.5 Flash.
  • (C3) Topology-conditional operating-envelope characterization: ORI is semantically neutral in dedicated-shard workloads (100% coherent) but semantically harmful in single-shard collaborative writing (100% contradicted under ORI-ON vs. 85.6% under ORI-OFF), prescribing explicit deployment-scope constraints.

Results

  • Zero Type-I corruptions: 0/427,308 commits under active shared-shard contention; 0/884,110 total across all conditions; Rule-of-Three 95% upper bound \(7.0 \times 10^{-6}\).
  • Observable coverage: \(R_{obs} = 26.1\%\) of reads per single step (PH-2 workload); \(p_{hidden} = 0.739\) per step. Session-scoped DeliveryLog accumulation raises observable coverage to 99.8% of self-reported references, but the denominator over-claims by 32–49%, deflating the genuine-causal upper bound to \(\leq 70\%\).
  • Workload-B conflict prevention: 590/639 divergent commits under ORI-OFF vs. 0/638 under ORI-ON (\(\chi^2 = 1094.98\), \(p < 10^{-240}\)).
  • Formal verification: 687/687 TLAPS obligations proved; TLC \(N=3\): 20,763,484 states (depth 28); \(N=4\): 2,811,301 states (depth 24); both zero violations; Dafny: 9 lemmas, 19 obligations.
  • Distributed safety: 30/30 ORI invariants survived leader failover (Exp. DR-9, Wilson 95% CI [0.886, 1.000]).
  • LLM-judge validation: human–LLM-judge agreement \(\kappa=0.93\) (strict) on 400 annotated (step, shard) pairs; inter-LLM-judge (GPT-4o vs. Claude Sonnet 4.6) \(\kappa=0.46\).
  • Sequential vs. OCC latency: application-level locking is 5–10× slower at \(N=5\) (Exp. SEQUENTIAL).

Limitations

  • Coverage gap: \(R_{obs}\) is only 26.1% per step; ORI's formal guarantees cover only this observable projection, not the full agent read set.
  • Self-report inflation: the 99.8% session coverage figure's denominator over-claims references by 32–49%; genuine causal coverage is \(\leq 70\%\) on the principal workload.
  • Single-shard regime: ORI is actively harmful for collaborative single-shard writing; no mechanism yet deployed for this topology (adaptive merge-routing is future work).
  • HTTP/1.1 assumption (A1): HTTP/2 multiplexing breaks per-connection FIFO ordering; requires reverse-proxy pinning or explicit read-set declaration.
  • ~5 ms failover window: distributed mode has a documented concurrent-failover gap not covered by formal proofs.
  • No Rust refinement: implementation-to-model correspondence is empirical, not mechanized (Verus/Creusot future work).
  • Workload scope: empirical claims cover only two distributions (SWE-bench-derived code coordination; data-pipeline architecture planning); transfer to document authoring, RAG orchestration, etc. is open.
  • Semantic quality: final-state coherence rubric validated by LLM judge only; human-annotation gap acknowledged as principal remaining evidential follow-up.

Relevance to Harnesses / Meta-Harnesses

S-Bus targets exactly the infrastructure layer that multi-agent harnesses and meta-harnesses need but typically lack: a consistency primitive for concurrent agents sharing mutable state. Because it operates as HTTP middleware with zero in-agent code changes, it can wrap existing orchestration harnesses (LangGraph, CrewAI, AutoGen) as a bolt-on layer, making it directly composable with harness architectures that spawn parallel sub-agents against a shared shard registry. The dedicated-shard topology — each sub-agent owns a distinct write key, all read shared reference shards — maps precisely to common meta-harness patterns where a coordinator dispatches workers that independently extend a shared plan or codebase. The paper's topology-conditional analysis (ORI neutral vs. harmful) is essential design guidance for harness engineers: dedicated-shard fan-out is safe under ORI; single-shard collaborative write patterns require a different coordination primitive.