Coordination Computation Class: Necessary Conditions for Bounded Multi-Agent Semantics‌​‌‌‍​‌​​‍‌‌‍‌​‌​​‌​​‌​​‌​​​‍​​​​​‍​‌‍​‍‌​​​​​​‍‌​​​​‍​‌​​​‍‌‍‌​‌‍‌‍​‍​​‌​​‌‍‌‍‌‌​​‌​​​​‍‌‍‌‌‌‍‌‌​‌‌‍‌‌​‌‍‌‍‌‍

In a previous position paper, I described why multi-agent systems drift. The argument was structural: connectivity is not coordination, optimization does not prevent divergence, and long-horizon integrity requires architectural bounds rather than heuristic tuning.‌​⁠‌‌⁠‍​‌​​‍‌⁠‌‍‌⁠⁠​‌‍​⁠‌‍⁠⁠‌‍⁠⁠‌⁠​‍‌‍‌​‌‍‍‌‌‍⁠‍‌‍​‌‌⁠‌​‌‍‍‌‌‍⁠⁠‌‍⁠‍​‍⁠‌‌‍​⁠‌‍⁠⁠‌‍⁠‌‌⁠​​‌⁠‌‌‌⁠‌​‌‍​‌‌⁠‌​‌‍‍‌‌‍⁠⁠‌‍⁠‍​‍⁠‌‌‍​⁠‌‍⁠​‌‍​‌‌⁠​⁠‌⁠​⁠‌⁠⁠​​⁠​‌​⁠‌⁠​⁠‌⁠​⁠​‍​⁠‌​​⁠‍​​⁠​‌​⁠​⁠​⁠‍‌​⁠‍​​⁠​‍​⁠‌⁠​⁠‌⁠

This paper takes the next step. It defines the coordination computation class — the minimal set of jointly necessary conditions that a system must satisfy to qualify as coordination-safe under irreversible cognitive evolution.

1. Why a Computation Class, Not a Protocol

Protocols describe what a system does. Computation classes describe what a system must be.

A transport protocol specifies message formats, delivery guarantees, retry logic. A coordination protocol specifies handshake sequences, consensus rounds, commitment phases. These are operational descriptions. They say nothing about the structural properties that must hold across the entire lifetime of a multi-agent system.

A computation class, by contrast, defines membership through invariants. A system either satisfies the invariants — or it does not belong to the class. There is no partial membership. There is no "almost coordination-safe". The class concerns bounded semantic evolution under irreversible state accumulation, not merely distributed agreement. Systems that permit semantic rollback, unbounded divergence under rejoin, or trust relaxation under propagation are formally outside this class, regardless of their empirical performance.

This distinction matters because coordination failures in long-horizon systems are not protocol violations. They are invariant violations. The protocol executed correctly — but the system drifted anyway, because the protocol never guaranteed the structural property that would have prevented drift.

2. The Four Necessary Conditions

A system belongs to the coordination computation class if and only if it satisfies the following jointly necessary conditions.

Condition 1: Irreversible State Evolution. Committed cognitive transitions may be superseded but are never rolled back. Once an agent commits a state change to the shared topology, that change becomes part of the permanent structural record. Supersession is permitted — a later state may override an earlier one — but silent erasure is not. This prevents the class of failures where an agent acts on state that was later retracted without its knowledge.

Condition 2: Trust-Monotonic Propagation. State updates propagate through a typed memory topology under trust constraints that are monotonically non-decreasing. An agent cannot lower the trust requirements of a propagation path that has already been established. Trust levels may increase — access may become more restricted — but they cannot be relaxed. This prevents privilege escalation through state manipulation and ensures that propagation constraints accumulate rather than erode.

Condition 3: Typed Agent-Store Access Enforcement. Every interaction between an agent and a state store is mediated by a typed access relation that is enforced at the propagation engine level, not at the application level. The access types define what an agent may read, write, propagate, or commit — and these types are structural properties of the coordination layer, not runtime parameters. This prevents the class of failures where an agent bypasses coordination constraints by accessing shared state through an unmediated channel.

Condition 4: Bounded Structural Cold-Start Divergence. The maximum difference between a recovering agent's operational context and the last committed system state must be deterministically bounded. Specifically, this bound must not grow with operational history length. A system where cold-start divergence is proportional to the number of prior transitions is not coordination-safe — it merely appears stable during short observation windows.

These four conditions are jointly necessary. Removing any one of them opens a specific class of structural failure that cannot be prevented by the remaining three. No combination of the remaining three can compensate for the absence of the fourth.

3. Joint Necessity: What Breaks Without Each Condition

Without Condition 1 (irreversible evolution): an agent may act on retracted state. The system appears consistent at query time but diverges under action, because the operational history contains gaps that no current state inspection can reveal.

Without Condition 2 (trust monotonicity): propagation constraints degrade over time. Early coordination guarantees erode as the system evolves. Trust becomes path-dependent and eventually unverifiable — the system cannot determine whether a propagation path still satisfies the constraints under which it was established.

Without Condition 3 (typed access enforcement): agents can bypass coordination through direct state access. The coordination layer becomes advisory rather than structural. Any agent with store-level access can introduce state changes that violate propagation invariants without detection.

Without Condition 4 (bounded structural cold-start divergence): newly initialized agents begin from arbitrarily stale context. As operational history grows, cold-start agents diverge further from the current system state. The coordination layer guarantees convergence only for agents that have been continuously present — which, in long-horizon systems, is an assumption that always eventually fails.

4. Independence from Transport and Storage

The four conditions are defined at the coordination level. They are independent of transport protocols, storage technologies, model providers, and application logic.

A system may use gRPC or HTTP, PostgreSQL or Redis, Claude or GPT, a planning agent or a retrieval agent — and still belong or not belong to this class. The conditions constrain the structural relationships between agents and shared state, not the implementation substrate.

This is what makes it a computation class rather than an architecture specification. The class is defined by what must be true, not by how it is achieved.

5. Relationship to Existing Coordination Models

Distributed consensus protocols — Paxos, Raft, 2PC — satisfy Condition 1 (irreversible log entries) and partially satisfy Condition 4 (bounded structural state via log replay). They do not satisfy Condition 2 (no trust monotonicity — all nodes are peers) or Condition 3 (no typed access — all nodes have symmetric access to the log).

Saga patterns satisfy none of the four conditions structurally. Compensating transactions violate Condition 1 (state is rolled back, not superseded). Orchestration is application-level, violating Condition 3. Trust and divergence bounds are not defined.

Event sourcing satisfies Condition 1 (append-only log) but not Conditions 2, 3, or 4. Events propagate without trust constraints, access is typically untyped, and cold-start requires full replay with unbounded divergence during reconstruction.

Multi-agent frameworks (LangGraph, CrewAI, AutoGen) satisfy none of the four conditions. They provide workflow orchestration — task routing, tool calling, memory persistence — but define no structural invariants over shared state evolution.

No existing general-purpose system satisfies all four conditions simultaneously. This is not a criticism of those systems. They were not designed to solve this problem. Any system that relaxes one of the four conditions necessarily leaves the coordination computation class and reverts to protocol-level coordination. Protocol-level coordination can simulate class-level behavior in short horizons, but cannot guarantee it under irreversible accumulation. The coordination computation class describes a set of requirements that emerges only when heterogeneous cognitive agents must maintain coherent shared state over long time horizons.

6. Instantiation

The Cognitive State Synchronization Protocol (CSSP) is an instantiation of this class. It satisfies all four conditions through specific architectural primitives: a typed memory topology with mandatory forward-only propagation, a role-based access enforcement layer, and a formal cold-start divergence bound.

CSSP demonstrates that the class is non-empty — that systems satisfying all four conditions simultaneously can be constructed. The formal details of the CSSP architecture are described in a separate specification and are outside the scope of this paper.

The purpose of defining the class is not to promote a specific instantiation. It is to establish a falsifiable criterion: given any coordination system, one can determine whether it belongs to this class by checking whether all four conditions hold. If any condition fails, the system is not coordination-safe under the definition proposed here — regardless of what other properties it may have.

7. Falsifiability

Each condition is empirically testable at the implementation level.

Condition 1 can be tested by introducing a state retraction and observing whether any agent subsequently acts on the retracted state. If so, irreversible evolution does not hold.

Condition 2 can be tested by attempting to relax a trust constraint on an established propagation path. If the relaxation succeeds, trust monotonicity does not hold.

Condition 3 can be tested by attempting to modify shared state through a channel that bypasses the typed access layer. If the modification succeeds, access enforcement does not hold.

Condition 4 can be tested by measuring structural cold-start divergence as a function of operational history length. If divergence grows without bound, the structural cold-start bound does not hold.

These are not philosophical criteria. They are engineering tests. A system either passes all four — or it does not belong to the class.

8. Implications

The coordination computation class is not a universal requirement for all multi-agent systems. Short-lived orchestrations, single-session workflows, and homogeneous agent clusters may not need bounded coordination semantics.

The class becomes necessary when three conditions converge: heterogeneous agents, shared mutable state, and operational horizons that exceed the continuous presence of any single agent. In these regimes — IP portfolio management, regulatory compliance suites, multi-year engineering specifications, research corpus governance — coordination-safety is not a feature. It is a precondition for structural integrity.

Defining the class formally allows a precise conversation about what is and is not coordination-safe. It replaces the current vocabulary of "better orchestration" and "smarter memory" with a structural criterion that can be checked, falsified, and enforced.

This is the difference between building systems that work — and building systems that hold.

© 2025–2026 Maksim Barziankou. All rights reserved. CC BY-NC-ND 4.0

MxBv, Poznan 2026.

Content Integrity Verification