PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Sajjad Khan

arXiv:2605.17076v2cs.LGcs.AIcs.DCcs.MA

TL;DR

LLM agents sharing mutable state can silently overwrite one another because existing frameworks lack write-ownership semantics. S-Bus reconstructs read sets from HTTP traffic to apply optimistic concurrency control, while its evidence shows self-reports over-claim shard usage by 32% to 49%.

  • Problem

    LLM agents sharing mutable state can produce Structural Race Conditions because existing frameworks lack write-ownership semantics for natural-language state.

  • Method

    S-Bus uses a server-side DeliveryLog to reconstruct agents’ read sets from observed HTTP GET operations and apply optimistic concurrency control without agent declarations.

  • Results

    32% to 49%: worker self-reports over-claim shard usage under LLM-judge and human-annotator evaluation, respectively.

  • Takeaways & Limitations

    ORI’s practical value depends on topology: it verifies coordinated dedicated-shard behavior but can admit semantically contradictory contributions in single-shard workloads.

  • Takeaways & Limitations

    The formal evidence retains one undischarged typing axiom, FUNTYPINGRECONSTRUCTION, in the TLAPS proof.

Abstract

from arXiv · show

We address concurrency control for LLM agents sharing mutable state over HTTP, where agents cannot be modified to declare read sets. S-Bus is an HTTP middleware whose central mechanism, a server-side DeliveryLog, reconstructs each agent's read set at commit time from observed HTTP GET traffic. The consistency property it provides -- Observable-Read Isolation (ORI), a partial causal consistency over the HTTP-observable read projection -- prevents Structural Race Conditions in dedicated-shard topologies. Three contributions. (C1) DeliveryLog mechanism with three-tier mechanised evidence: TLAPS proves ReadSetSoundness and ORICommitSafety (modulo one typing axiom); exhaustive TLC at N=3 explores 20,763,484 states with zero violations; Dafny discharges 9 inductive lemmas. (C2) Empirical safety parity against PostgreSQL 17 SERIALIZABLE and Redis 7 WATCH/MULTI: zero Type-I corruptions across 884,110 commit attempts (427,308 under active contention). (C3) ORI is semantically neutral in dedicated-shard workloads but harmful in single-shard collaborative writing because preservation propagates concurrent contradictions. v2 update: the PH-3 LLM judge is now independently validated against a human annotator (Zahid Hussain, Mindgigs Peshawar) on 400 (step, shard) pairs at strict kappa=0.93 (n=93, 96.8% raw agreement). Inter-LLM-judge agreement is kappa=0.46 (boundary variance). Agent self-reports over-claim shard usage by 32% (LLM judge) to 49% (human annotator). The SJ-v4 semantic-quality rubric remains single-judge LLM-only. Source code, formal proofs, harness, annotation data: https://github.com/sajjadanwar0/sbus

1 INTRODUCTION

S-BUS addresses structural race conditions in concurrent LLM agents sharing mutable HTTP state by reconstructing read sets from observed GET traffic and applying optimistic concurrency control. Its guarantees are structural and strongest for dedicated-shard topologies, while semantic correctness and single-shard collaborative writing remain workload-dependent.

  • Problem: Concurrent agents can silently overwrite one another after reading the same shard version, creating a Structural Race Condition (SRC).An SRC is defined structurally by coincident reads and commits at the same expected version without an intervening re-read.
  • Scope and limitations: S-BUS provides structural conflict prevention for dedicated-shard workloads, while single-shard collaborative writing is out of scope and requires adaptive merge routing.The formal proofs cover read-set monotonicity and cross-shard equality at commit, not agent semantic correctness.
  • Approach: S-BUS uses a server-side DeliveryLog to reconstruct each agent’s read set from HTTP GET operations and validate cross-shard staleness at commit time.This applies optimistic concurrency control without requiring agents to declare read sets or add coordination code.
  • Empirical safety: 200,880 commit attempts produced zero Type-I corruptions for S-BUS, PostgreSQL 17 SERIALIZABLE, and Redis 7 WATCH/MULTI.The result spans N ∈{4,8,16,32,64}, 30 task domains, and 1,350 runs, with a 95% Rule-of-Three upper bound of 1.49×10−5.
  • Topology-conditional behavior: 40/40 agent-step contributions per trial were preserved with ORI-ON, compared with 10/40 = 1/N under ORI-OFF in 959 paired trials.The contribution-preservation invariant is structurally unconditional but its semantic benefit depends on workload topology.

2 RELATED WORK

S-BUS is positioned as an HTTP consistency layer for multi-agent systems whose existing frameworks lack write-ownership semantics and whose conflicts can cause silent overwrites. Its design combines automatic read-set reconstruction with conditional requests, causal-log ideas, and a projection-based isolation model, while distinguishing OCC from CRDT and merge alternatives.

  • Multi-agent frameworks: Existing multi-agent frameworks lack write-ownership semantics for mutable shared state, typically detecting conflicts only through self-reports or downstream validation.The cited frameworks route state through workflow graphs, message-passing channels, or agent-local memory.
  • Multi-agent frameworks: 23–31% of LangGraph failures are consistency errors, while 20/20 N=4 trials produced silent overwrites under last-write-wins.S-BUS targets this failure category with ORI as the missing structural primitive.
  • Concurrency-control foundations: S-BUS adapts RFC 7232 conditional requests by reconstructing read sets automatically from HTTP GET traffic and validating sibling-key versions across shards.This enables SDK-free integration under HTTP/1.1 rather than requiring agents to declare read sets.
  • Isolation-level theory: ORI prevents G0, G1a, G1b, and G2-item over Robs, while permitting G2 over Rhidden and G3 globally.The model is therefore a projection-based consistency guarantee over the observable history.
  • Why not X?: S-BUS targets non-commutative natural-language state with OCC, whereas CRDTs are preferable for additive shards and LLM-assisted merging resolves conflicts post-hoc.The related work identifies CRDTs and LLM-assisted merge as alternatives whose suitability depends on the workload.

3 MECHANISM AND CONSISTENCY MODEL

S-Bus reconstructs agent read sets from observed HTTP GETs via a server-side DeliveryLog and enforces Observable-Read Isolation (ORI) at commit. ORI is formally and exhaustively supported for observable reads, while hidden-read coverage and retry behavior remain workload- and topology-dependent.

  • DeliveryLog mechanism: The DeliveryLog records each agent’s HTTP GET key-version pair and rejects commits when any recorded cross-shard version has advanced.This reconstructs read sets server-side without requiring agents to declare them, generalizing HTTP ETags across shards.
  • Observable-Read Isolation: ORI requires totally ordered writes per shard and freshness of every recorded cross-shard observable read at commit.Under A1–A5, all committed histories are ORI-legal over Robs.
  • Formal evidence: 687 TLAPS obligations were proved with 0 failed, while exhaustive TLC found 20,763,484 N=3 states and 2,811,301 reduced N=4 states with zero violations.The TLAPS safety theorems depend on one retained FUNTYPINGRECONSTRUCTION axiom; a full exhaustive N=4 sweep at MAXVERSION=3 remains open work.
  • Read coverage: 26.1% of reads are in Robs, leaving 73.9% in unobservable Rhidden; session-cumulative DeliveryLog coverage is fobs_total = 0.998.The formal safety guarantee applies to HTTP-recorded reads, while session-scoped DeliveryLog retention validates earlier recorded versions at commit.
  • Topology and retries: At SCR = 0.856 with N=16, K=19 retries are required for 95% success, whereas default K=5 yields 47% success.The retry bound assumes i.i.d. conflicts; positive correlation can raise effective SCR and require at least 2× the i.i.d.-derived bound.

4 DELIVERYLOG

The DeliveryLog reconstructs each agent’s read set from observed shard GETs at commit time, with explicit entries taking precedence and zero false-negatives under A1 in default mode. ARSI instead uses fully declared read sets, while default reconstruction may cause stale-entry false-positive aborts after TTL.

  • Read-set reconstruction: At commit, the reconstructed read set is R_explicit ∪ session-deliveries, with explicit entries taking precedence.The DeliveryLog records each GET /shard/:key?agent_id=X and combines explicit declarations with session-delivery observations.
  • Read-set reconstruction: 0 false-negatives under A1 are reported for default DeliveryLog reconstruction, despite occasional stale-entry false-positive aborts after TTL.In ARSI mode, agents declare their full read sets explicitly and the DeliveryLog false-positive rate is 0.

5 ARCHITECTURE AND ALGORITHM

The architecture is implemented in safe Rust with Raft coordination and sled persistence, using crash-safe logging and a verified deadlock-free lock order.

  • Implementation: 1,679 lines of safe Rust implement ACP, Raft coordination, and sled persistence, with zero unsafe blocks.The ACP core comprises ≈950 lines; the system uses Tokio 1.44 and Axum 0.8.4.
  • Implementation: The registry uses Mutex<HashMap>, the WAL uses direct File::write_all() for SIGKILL safety, and Dafny verifies the RwLock → TokenMutex ordering is deadlock-free.The lock-order graph has a single edge and no cycle.

6 EXPERIMENTAL SETUP

The experiments run on a fixed AWS/GPT-4o-mini setup with explicit validity criteria and are organized into three distinct axes: ORI correctness, architecture comparison, and pure ORI effects. The roadmap spans diverse workloads, backbones, topologies, and scales, including 1,364 valid SWE-bench runs and targeted injection and contention studies.

  • Environment and validity: All experiments use an AWS Lightsail eu-west-2 instance with 2 vCPU and 8 GB RAM, a single-process Tokio S-Bus server, and GPT-4o-mini at temperature 0.3.Runs require S-Bus health, at least 50% step completion, and no API timeout over 30 seconds; fewer than 2% are excluded.
  • Three-layer experiment structure: The study separates ORI correctness, architecture comparison, and pure ORI effect to distinguish mechanism performance from parallel-coordination benefits and baseline effects.ORI-correctness experiments use shared-shard topologies with ORI triggered on every conflict, whereas architecture comparisons use distinct shards where ORI never triggers.
  • Experiment portfolio: 1,364 valid runs evaluate SWE-bench across 30 tasks, N ∈{4,8,16}, and 50 steps under a distinct-shard topology with SCR = 0.This is Exp. B and measures architecture-level coordination rather than ORI’s consistency mechanism.
  • Experiment portfolio: 9,304 cross-shard injections, 590 shared-shard contention attempts, and 200 direct stale-read injections provide targeted tests of validation, contention, and Type-II/Robs behavior.These correspond to Exp. CSV, Exp. E, and Exp. SR, respectively.
  • Experiment portfolio: 813 Haiku-3 runs, 150 Llama-3.1-8b-instant runs, and 8,400 phidden step-logs extend evaluation across backbones and a 10-domain workload set.The backbone studies use 30 and 14 tasks, respectively; PH-2 covers 10 domains.

7 RESULTS … 7.6 Exp. WORKLOAD-B: Cross-Workload Structural Validation on Data-Pipeline Planning

Across the results, S-BUS prevents structural races, validates stale-read rejection, and shows coordination and runtime trade-offs across code and non-code workloads. The evidence also distinguishes mechanism conformance from semantic-quality or topology-generalisation claims.

  • 7 RESULTS: The results are organized into five narrative arcs and supporting subsections aligned with the paper’s three contribution areas.The reading guide directs safety assessment to structural conflicts and CC parity, coverage to Arc A2, generalisation to Arc A4, and deployment scope to Arc A5.
  • 7.1 Exp. B: Coordination Architecture Comparison (distinct-shard): Exp. B compares S-BUS, LangGraph, CrewAI, and AutoGen under distinct-shard topology, where SCR = 0 and ORI rejection is never triggered.The experiment measures coordination-architecture efficiency rather than ORI consistency-mechanism quality.
  • 7.2 Task Success and Wall-Time Trade-off: AutoGen achieves 88–90% S@50 versus S-BUS’s 70–74%, while S-BUS significantly outperforms CrewAI, underperforms AutoGen, and trails LangGraph only at N = 16.Fisher’s exact tests report p < 10^-6 against CrewAI, p < 0.01 against AutoGen, and p = 0.012 against LangGraph at N = 16.
  • 7.3 Exp. SR and Exp. CSV: Structural Validation: 200/200 Exp. SR trials rejected every stale commit and accepted every fresh commit, with zero errors and a 95% CI upper bound of ≤3.0%.Exp. CSV recorded 9,304 OCC-on injections and zero corruptions, versus a 56–62% OCC-off corruption rate.
  • 7.4 Exp. SEQUENTIAL: Measured Wall-Time Speedup: All Exp. SEQUENTIAL comparisons favor parallel S-BUS execution over sequential execution with p < 0.0001 across N ∈{4,8,16}.The measurements use identical servers, tasks, backbones, and steps, varying only concurrent versus serial execution; the reported model is Θ(S·tstep).
  • 7.5 Exp. ORI-ISOLATION: Mechanism Conformance Under Contention: 479 ORI-ON trials at N = 4 matched the specified retry-loop behavior, establishing implementation conformance rather than semantic-quality improvement or ORI value.The experiment’s zero-variance outcomes are specification-determined; live execution showed wall-time ranges of 122–154 s with ORI-ON and 37–45 s with ORI-OFF.
  • 7.6 Exp. WORKLOAD-B: Cross-Workload Structural Validation on Data-Pipeline Planning: 0/638 = 0.00% divergent commits occurred under ORI-ON versus 590/639 = 92.33% under ORI-OFF across eight data-pipeline domains.Aggregate χ2 = 1094.98, p < 10^-240; all 80 trials reached 100% completion, with ORI-ON retries absorbing stale-read rejections.
  • 7.6 Exp. WORKLOAD-B: Cross-Workload Structural Validation on Data-Pipeline Planning: Exp. WORKLOAD-B supports structural-conflict prevention beyond code workloads, while its uniform 91%–94% domain rates reflect harness shape and do not establish generalisation to all topologies.The experiment measures structural prevention, not semantic output quality; it is presented as mitigating Threat ET1 at χ2 = 1094.98 significance.

7.7 Exp. PH-2: phidden Measurement … 7.12 Exp. E and SCALE: Shared-Shard Contention at N ≤64

Across PH-2 through SCALE, S-Bus measures substantial hidden shard usage, validates semantic extraction and human agreement, shows API-layer mitigation requirements, and preserves zero Type-I corruption under shared-shard contention up to N=64.

  • 7.7 Exp. PH-2: phidden Measurement: phidden = 0.739, with 95% CI [0.736,0.741], across 128,622 reads and 95,022 hidden references in 10 task domains.Domain values range from 0.511 for Django queryset to 0.836 for Astropy FITS.
  • 7.9 PH-3 validation summary: Strict human validation reaches κ=0.93 with n=93 and 96.8% raw agreement, while LLM-judge agreement is κ=0.46.The human annotator identifies a 49% self-report over-claim rate, compared with 32% from the LLM judge.
  • 7.10 Exp. ADVERSARIAL-RHIDDEN (summary): An in-process phiddenWrapper produces final-state corruption identical to ORI-OFF, showing hidden-reference mitigation must operate at the LLM-API layer.This result motivates the transparent proxy approach evaluated in Exp. PROXY-PH2.
  • 7.11 Exp. PROXY-PH2: Structural-Coverage Decomposition: DL-accumulation = 0.555 dominates structural coverage, while proxy-marginal = 0.0018 and total ftotal = 0.998 on 16,800 paired GPT-4o-mini step-logs.Cross-backbone replication confirms 0/26,400 Type-I corruptions and ftotal ∈[0.997,0.999].
  • 7.12 Exp. E and SCALE: Shared-Shard Contention at N ≤64: Exp. E records zero Type-I corruptions across 590 commit attempts, while SCR rises from 0.650 at N=4 to 0.856 at N=16.The version-check-disabled baseline has 97.5% corruption at N=4.
  • 7.12 Exp. E and SCALE: Shared-Shard Contention at N ≤64: Zero Type-I corruptions persist across 74,400 commit attempts through N=64, with a 95% CI upper bound of 0.004%.At N=32, K95=28 is required for 95% liveness under worst-case shared-shard contention; default K=5 is insufficient above N=8.

7.13 Exp. PG-COMPARISON (FULL): Three-Backend CC-Parity at Scale · 7.14 Backbone Generalisation (T3-A, T3-B) · 7.15 Exp. SJ-V4: Semantic Judge Context Diversity Effect

Across three backends, S-BUS matched PostgreSQL SERIALIZABLE and Redis WATCH/MULTI in safety while incurring lower latency, and backbone results were model-dependent. In single-shard SJ-v4, fresh context unexpectedly produced more corruption than stale context, revealing a topology-driven semantic effect.

  • 7.13 Exp. PG-COMPARISON (FULL): Three-Backend CC-Parity at Scale: 200,880 commit attempts produced 0 Type-I corruptions across S-BUS, PG-SER, and REDIS-WATCH.The 95% Rule-of-Three upper bound was 1.49×10^-5 per-attempt corruption rate.
  • 7.13 Exp. PG-COMPARISON (FULL): Three-Backend CC-Parity at Scale: S-BUS was 1.80×–1.95× faster than REDIS-WATCH and PG-SER was 13×–15.5× slower than S-BUS.All three backends exhibited near-linear scaling, increasing ∼11.5–13.4× from N=4 to N=64.
  • 7.13 Exp. PG-COMPARISON (FULL): Three-Backend CC-Parity at Scale: The dedicated-shard workload produced 0 HTTP-409 conflicts because agents owned distinct shards, so the experiment measured safety parity rather than contention effectiveness.The following contention experiment addresses the unexercised retry paths.
  • 7.13 Exp. PG-COMPARISON (FULL): Three-Backend CC-Parity at Scale: Matched Rust adapters yielded 0 Type-I corruptions across 136,080 commit attempts, with commit throughput converging within statistical noise at N ≥16.Across the combined sub-experiments, the architectural value of S-BUS is operational simplicity and an LLM-native contract rather than differentiated CC mechanics.
  • 7.14 Backbone Generalisation (T3-A, T3-B): Backbone results were model-dependent: Haiku-3 placed S-BUS below CrewAI, while Llama-3.1-8b-instant placed S-BUS above LangGraph at N=4.Under Haiku-3, S-BUS was not significantly different from LangGraph; under Llama-3.1-8b-instant, the result was 84.6% vs. 33.3% with Mann-Whitney p = 0.0002.
  • 7.14 Backbone Generalisation (T3-A, T3-B): Under Llama-3.1-8b-instant, S-BUS CWR = 0.19 versus LangGraph CWR = 8.44, a 44× difference.CWR measures coordination-token overhead relative to work tokens and was measured only for Llama-3.1-8b-instant.
  • 7.15 Exp. SJ-V4: Semantic Judge Context Diversity Effect: Fresh agents produced 40.6% corruption versus 29.1% for stale agents, a lift of −11.5 pp with p = 0.0002.Only 6/20 tasks showed the expected positive lift; 10/20 reversed it and 4/20 showed no difference.
  • 7.15 Exp. SJ-V4: Semantic Judge Context Diversity Effect: In the single-shard topology, fresh agents read identical intermediate state and generated redundant patches, whereas stale reasoning diversified coverage.This topology effect is outside ORI’s intended dedicated-shard operating regime, where contributions are complementary and semantic neutrality is reported.

7.16 Exp. MERGE: OCC vs. LLM-Assisted Merge … 7.21 Exp. DR-9: ORI Survives Leader Failover

Across MERGE, structural dose-response, topology, single-shard, case-study, and failover evaluations, S-Bus shows strong conflict detection and ORI preservation, but semantic effects depend on workload topology. Dedicated shards preserve coherence, whereas single-shard retries amplify contradictions; replicated DeliveryLogs preserved ORI through sequential leader failover.

  • 7.16 Exp. MERGE: OCC vs. LLM-Assisted Merge: 100% of structural conflicts (45/45) were detected and rejected, with 100% retry success; MERGE was 1.9× slower than OCC.OCC median latency was 2,361 ms including retry, versus 4,395 ms for MERGE.
  • 7.16 Exp. MERGE: OCC vs. LLM-Assisted Merge: 66.7% of repeated GPT-4o-mini merges had Jaccard word-overlap below 0.6, indicating substantial merge non-determinism.The mean Jaccard overlap was 0.544, with a Wilson 95% CI of [0.521,0.786] for the non-determinism rate.
  • 7.17 Exp. SJ-V5: Structural SCR Dose-Response: The SJ-V5 commit-rate dose-response exactly matched 1− (k/4)·(15/20), with prediction error below 0.5 percentage points.ORI’s cross-shard validation operated at the analytically predicted rate across stale fractions k ∈ {0,1,2,3}.
  • 7.18 Exp. DEDICATED-SHARD: Semantic Quality in the Correct Topology: 100% coherence occurred under both ORI-ON and ORI-OFF in dedicated-shard workloads, with zero redundant outputs.Commit rates were 0.799 with ORI-ON and 0.807 with ORI-OFF, confirming ORI was structurally active in both conditions.
  • 7.19 Exp. SHARED-STATE: Multi-Domain Single-Shard Evaluation: ORI-ON produced 0% consistent and 100% contradicted outputs in single-shard tasks, versus 4.4% and 85.6% under ORI-OFF.ORI-ON raised the commit rate from 0.250 to 0.534 by retrying agents’ patches, preserving contradictory sequential edits to one shard.
  • 7.19 Exp. SHARED-STATE: Multi-Domain Single-Shard Evaluation: 500 hidden reads were promoted across 480 completions, or 104.2% per completion, demonstrating feasibility but not causal precision.PhiddenWrapper intercepted responses and registered keyword-associated shard references without agent code changes; false-positive promotions remain possible.
  • 7.20 Case Study: Django Issue #11019: SCR was 0.0% across 15 steps and 60 commit attempts in the Django #11019 case study, reflecting dedicated-shard work without structural contention.Four role-specialised agents declared all four shards in every commit; the case therefore did not trigger ORI’s stale-read rejection.
  • 7.21 Exp. DR-9: ORI Survives Leader Failover: 100% of DR-9 trials preserved ORI across leader failover: 30/30 trials succeeded in a three-node Raft cluster.The validation covered sequential GET-then-kill trials; a concurrent failure within the approximately 5 ms replication window remains a limitation.

8 LIMITATIONS

The main limitations concern incomplete observability of hidden reads, semantic-quality and proxy-extraction gaps, and remaining validation threats in the benchmarks and formal-to-implementation assurance. Additional limitations include a concurrent-failover window, a foundational typing axiom, and the absence of a Rust refinement proof.

  • Hidden-read coverage: 26.1% of reads are structurally covered in Robs, while phidden = 0.739 is not directly observable at the HTTP layer within a single step.The domain range for phidden is 51–84% on SWE-bench / GPT-4o-mini.
  • Proxy and semantic extraction: 0.555 additional coverage comes from session-scoped DeliveryLog accumulation, whereas pure-semantic references contribute 0.0018 at V=4 and negatively at V∈{8,12}.The proxy captures pure-semantic references under skip-ifexists register semantics, but throughput falls by −2.1 pp at V=4 and −47.2 pp at V=12.
  • Judge and ground-truth validity: κ=0.93 agreement with a human annotator was obtained on 400 step–shard pairs, while inter-LLM-judge agreement remained κ=0.46.The human comparison had n=93 unambiguous yes/no cases and 96.8% raw agreement; the SJ-v4 semantic-quality rubric remains single-judge LLM-only.
  • Formal and implementation assurance: 687 TLAPS obligations were proved with 0 failed, but one foundational typing axiom remains, full Raft-TLAPS is deferred, and no refinement proof covers the Rust implementation.The abstract 3-node model-checking result was 247,249 distinct states with 0 violations; async tokio support blocks Verus or Creusot refinement.
  • External validity: 0/638 divergent commits occurred under ORI-ON versus 590/639 under ORI-OFF on the non-code WORKLOAD-B workload.The difference was χ2 = 1094.98, p < 10−240, but generalisation to more workload classes and semantic outcome quality remains future work.
  • Construct validity: 8.5% of benchmark records contain cross-labelling, and shards contain narrative English rather than typed artefacts, limiting interpretation in typed-state regimes.A regenerated typed-shard benchmark is identified as future work to address this construct threat.

9 DISTRIBUTION PATH AND PRACTITIONER GUIDANCE

S-BUS is primarily suited to HTTP-based, non-commutative workloads with dedicated shards, bounded deployment size, and agents unable to use database transactions directly. Practitioner guidance favors transactional databases, Redis WATCH, CRDTs, or sequential coordination when their workload or performance assumptions fit better, while the implementation provides Raft-based clustered deployment and an HTTP-compatible proxy path.

  • When to use S-BUS: Use S-BUS for HTTP-only agents, non-commutative shared state, deployments with N ≤32 agents and ≤4 nodes, and dedicated shards.Dedicated-shard deployments are identified as the primary deployment pattern.
  • Alternatives: 13×–15.5× wall-time cost is the reported overhead for PostgreSQL SERIALIZABLE, which matches S-BUS structural safety at N ≤64.Transactional databases are recommended when agents can issue SQL transactions directly and state is structured or typed.
  • Alternatives: 1.8×–1.95× wall-time cost is the reported overhead for Redis WATCH, which matches S-BUS structural safety at N ≤64.Redis WATCH is positioned for high-throughput key-value concurrency control when its network round-trip cost is acceptable.
  • Alternatives and limitations: Use CRDTs for purely additive append-only contributions, and sequential coordination when success rate outweighs throughput, N ≤8, or the backbone is Haiku-3-class.With GPT-4o-mini-class backbones, S-BUS parallel execution achieves competitive task success at significantly lower latency; sequential coordination is also recommended for single-shard collaborative tasks because ORI is semantically harmful there.
  • Deployment path: 3-node Raft replication provides a cluster-wide total commit order, while the LLM API proxy promotes Rhidden → Robs without agent code changes.The shipped implementation uses safe Rust and supports any LLM provider supporting HTTP; the proxy intercepts completion responses and logs shard-key references.

10 CONCLUSION

S-Bus uses a server-side DeliveryLog to reconstruct HTTP-observable read sets without agent-SDK changes, providing Observable-Read Isolation for a scoped class of multi-agent race conditions. Evidence spans formal verification, safety parity, coverage analysis, and validated semantic-extraction results, while hidden reads and proxy refinement remain limitations.

  • Mechanism and scope: DeliveryLog reconstructs each agent’s HTTP-observable read set at commit time, enabling optimistic concurrency control under HTTP/1.1 without agent-SDK changes.ORI applies to write–write and cross-shard stale-read failures over the observable read fraction, Robs.
  • Formal evidence: 687 obligations were discharged for ReadSetSoundness and ORICommitSafety, with one retained primitive TLA+ function-theory axiom.TLC found 0 violations across 20.8M distinct N=3 states and 2.8M reduced N=4 states; Dafny also machine-checked inductive lemmas.
  • Proxy analysis: 0/16,800 Type-I errors were observed for the transparent proxy, whose marginal coverage was 0.0018 paired with 95% CI [0.0013,0.0024].The proxy was safety-preserving but monotonically throughput-negative at realistic vocabulary sizes.
  • Semantic extraction and limitations: Strict κ=0.93 agreement between the LLM judge and human annotator validated PH-3, while self-reports over-claimed shard usage by 32% to 49%.Transfer of semantic extraction to the multi-agent PH-2 regime remains open; full Raft-TLAPS mechanisation and Rust refinement are future work.

11 FUTURE WORK

Future work targets adaptive routing for topology-dependent workloads, mechanising the Raft layer, and testing semantic extraction in higher-phidden multi-agent settings. It also proposes typed benchmark artefacts to improve auditability and reduce judge disagreement.

  • Adaptive topology-aware coordination: ORI should be paired with adaptive routing because it is valuable for dedicated shards but harmful for contradictory single-shard collaborative writing.A-BUS is under active development; its formal model, evaluation methodology, and quantitative results are deferred to a companion paper.
  • Adaptive topology-aware coordination: Three architectural additions are proposed: an additive_hint commit flag, per-shard topology classification, and a merge engine with three strategies.The classifier distinguishes DEDICATED, CONTENDEDCOMMUTATIVE, and CONTENDEDNON-COMMUTATIVE shards using contention rate and declaration consistency.
  • Replication and mechanisation: 30/30 ORI invariants survived leader failover, but a residual ∼5 ms concurrent-failover window remains and the Raft layer lacks TLAPS mechanisation.Composing the ORI proofs with a Raft TLAPS specification is identified as the single largest remaining mechanisation gap.
  • Semantic-extraction validation: p_hidden = 0.739 versus p_hidden = 0.074 leaves semantic-extraction effectiveness in high-phidden multi-agent workloads unresolved.A rerun with a dedicated-analyst extractor attached to each agent is defined, at an estimated ∼$50 API cost per cell.
  • Benchmark and annotation quality: 8.5% of records exhibited Step-2/Step-3 judge disagreement, motivating regenerated benchmarks with typed artefacts to improve trace auditing.Current default CrewAI and LangGraph benchmarks contain plan-narrative English rather than code, SQL, or schemas.

APPENDIX

The appendix reproduces the frozen rubric used by both LLM judges in the PH-3 validation study. It defines ordered semantic-necessity tests, hard evidence rules, and fixed evaluation settings with zero output-format failures across 400 tasks.

  • Rubric purpose: The rubric asks whether the Candidate Shard demonstrably contained content the agent needed to produce the Code Change.The prompt was frozen before observing inter-judge agreement and was not revised.
  • Decision procedure: Step 1 labels Yes when the shard defines the specific entity modified or read by the Change.The test covers functions, classes, variables, fields, and constants.
  • Decision procedure: Step 2 labels Yes when the Change depends on state or schema whose concrete shape is recoverable only from the shard.Examples include schemas, prior versions, signatures, and types.
  • Decision procedure: Step 3 labels No for topical overlap, shared vocabulary, or mere context availability, while hard rules reject empty, truncated, unquotable, or name-collision evidence.The evidence must be semantic and tied to specific shard words or tokens.
  • Evaluation settings: 0/0 output-format failures occurred across the 400 tasks, with both judges run at temperature=0 and max_tokens=512.These settings applied to both judges in the PH-3 validation study.
Loading 2605.17076v2…