A Survey of Agentic Coordination Formalisms

Deleuze and Guattari’s word assemblage (agencement) names a working arrangement of heterogeneous parts whose identity lies in what they do together rather than in what each part is. The relations are external to their terms: a component can be unplugged from one assemblage and plugged into another, and the whole persists not by essence but by ongoing processes of territorialisation, the stabilising of relations, and deterritorialisation, their coming loose.

A multiagent system at work on a complex task is an assemblage in exactly this sense: models, tools, humans, channels and task fragments held together by nothing more than their current relations, which are continually being made and unmade. An orchestrator spawning a worker territorialises; a handle passed onward, a subtask re-routed, a private channel escaping its scope, these deterritorialise. The previous post treated the fabric of such arrangements through the π-calculus. But “coordination” spans far more than message plumbing, and no single formalism totalises the assemblage. Each theory below is a cut: it holds one aspect still, makes it precise, and abstracts the rest. This post is a map of the cuts.

> coordination-stack — six cuts through the assemblage · select a layer to jump

asideOn ascription, before the mental vocabulary starts

Talk of an agent’s beliefs and intentions invites the charge of anthropomorphism, so it is worth being clear at the outset what the formalisms below actually claim. The answer is: nothing psychological. Mental-state ascription, in McCarthy’s classic analysis,¹ is legitimate exactly when it expresses the same information about a system’s behaviour more compactly than a mechanistic description would. In the agent logics the ascribed states are modal operators with fixed axiom systems, belief typically as KD45 and knowledge as S5, and intention, in Cohen and Levesque’s construction, is defined as a persistent goal within a temporal modal logic. The mental vocabulary is discharged into axioms.

The philosophical residue is the question of intentionality, the aboutness of states. Here the useful distinction is derived intentionality: the content of a formal agent’s belief atoms is fixed by an externally supplied interpretation, in the same way model-theoretic semantics fixes the denotation of symbols. Nothing in the coordination theories below requires anything stronger. Whether some systems could possess original intentionality is a live philosophical question, but it is one the formalisms neither ask nor need answered; they operate, deliberately, at the level of behaviour under an interpretation.

The interaction fabric

The first family of formalisms fixes the structure of interaction: who can talk to whom, in what order, and how that changes. This is the territory of the process calculi, of which the π-calculus is the member built for topologies that change as the system runs.

On top of the calculi sit session types, which turn a protocol into a checkable artefact: where an ordinary type constrains a value, a session type prescribes the sequence, direction and payload of the messages on a channel, as in ${!}\mathsf{Int}.\,{?}\mathsf{Bool}.\,\mathbf{end}$ , the type of an endpoint that sends an integer, awaits a boolean, and stops, while its peer holds the dual type. Their multiparty form is a choreography: one global description of the whole conversation, written from the viewpoint of no participant, projected mechanically to a local type per participant. A well-formed choreography yields processes that are deadlock-free by construction.

Beneath this layer sits a proof theory. Linear logic, Girard’s logic of resources, removes the structural rules that let assumptions be duplicated and discarded, which makes a proposition something consumed by use, exactly the ontology of messages, channel endpoints and capabilities. Under a Curry–Howard correspondence discovered by Caires and Pfenning and sharpened in Wadler’s Propositions as Sessions, linear logic propositions are session types, proofs are π-calculus processes, and cut elimination is communication; deadlock-freedom stops being a property one checks and becomes a corollary of the logic, since a deadlock would amount to a cyclic proof and the logic has none. The echoes run deeper: Milner’s replication $!P$ deliberately mirrors Girard’s exponential !A, both meaning an unlimited supply, which is what a server is, and Girard’s Geometry of Interaction programme reads proofs themselves as interacting processes, arriving at computation-as-communication from the proof-theory side.

The question this layer answers: can the conversation go wrong structurally, through mismatch, stuck states, or orphaned messages, regardless of what any participant is thinking.

The knowledge layer

Coordination failures are frequently knowledge failures, and epistemic logic makes them precise. The operator $K_a\,\varphi$ says agent $a$ knows $\varphi$ , interpreted over the worlds $a$ cannot distinguish; the operators nest, and what $a$ knows about what $b$ knows is exactly the currency protocols trade in.

The layer’s central concept is common knowledge, written $C_G\,\varphi$ : everyone knows $\varphi$ , everyone knows that everyone knows it, and so on through every level. Its central theorem is an impossibility. In the coordinated attack problem, two generals who can only exchange messages over an unreliable channel can never attain common knowledge of the plan, however many acknowledgements they send, and therefore can never guarantee simultaneous action. This places a hard ceiling on what any coordination protocol can promise, and it is as binding on a fleet of LLM agents as it was on the generals.

The question answered: what must each party know, and how must knowledge propagate, before joint action is possible at all.

The commitment layer

A team is more than co-located workers, and the BDI tradition formalises the difference. Its account of individual agency, from Bratman via Rao and Georgeff, treats intention as the commitment that makes deliberation tractable: an agent that reconsiders everything at every step never acts.

The multiagent extension is the theory of joint intention: a shared commitment to a goal together with an obligation of mutual belief about its status. The load-bearing axiom is small and sharp. An agent that privately discovers the goal is achieved, impossible or irrelevant may not silently drop it; it must first make that discovery mutually believed. Concrete communication obligations fall out of this one requirement, and it is precisely what most current agent orchestrations lack: a worker that fails silently is an agent without joint intentions. The agent communication languages of the FIPA era grounded their message types in speech act theory, so that sending an inform or a request is itself an act with defined commitments.

The question answered: when is an agent obliged to speak, and what does it mean to be bound to a shared goal.

The strategic layer

Where agents are self-interested, or merely autonomous, coordination becomes equilibrium. The baseline notion is the Nash equilibrium, a strategy profile no agent can improve on by deviating alone; an arrangement that is not one relies on agents acting against their own interests to sustain it. Mechanism design runs the analysis in reverse, shaping the rules so that self-interested behaviour yields the outcome the designer wants, and cooperative game theory contributes the Shapley value, the canonical fair division of a joint payoff among members of a coalition that only produces value together. Credit assignment among cooperating agents is this problem exactly.

The logical face of this layer starts from temporal logic, in which properties of executions are stated with $\square\varphi$ (“always”, the shape of safety properties) and $\lozenge\varphi$ (“eventually”, the shape of liveness). Alternating-time temporal logic replaces the path quantifiers with coalitions: $\langle\!\langle A\rangle\!\rangle\,\varphi$ says the agents in $A$ have a joint strategy forcing $\varphi$ whatever the others do. Because these are logics with finite models, model checking applies: strategic ability becomes a property a tool can verify, counterexample traces included.

The question answered: what can this coalition bring about, and under what rules is honesty rational.

The decision layer

If one asks not whether coordination is possible but what the optimal joint behaviour is under uncertainty, the models are decision-theoretic. The single-agent base is the Markov decision process; the cooperative multiagent generalisation is the Dec-POMDP, in which several agents share one reward function but each acts only on its own local observations.

The headline result is negative and important: solving a finite-horizon Dec-POMDP is NEXP-complete, which by the time hierarchy theorem is unconditional intractability, not conjecture. Read as systems advice, this is a proof that fully general decentralised coordination does not scale, and that the structure practitioners impose, hierarchy, explicit communication, task decomposition, is not an optimisation but a necessity. In the vocabulary of the opening: an assemblage that never reterritorialises is computationally unliveable.

The question answered: what is the best a decentralised team can do, and what does it cost to find it.

The task layer

Finally, the task itself has structure, independent of who performs it. Petri nets model precedence, synchronisation and resource contention directly, and their workflow specialisation makes soundness, every run can complete and no task is dead, a decidable property of the task graph. On the allocation side, the contract net protocol is the venerable pattern: announce, bid, award, report, with subcontracting by recursion. Stripped of its deliberative content it is a small conversation structure, and its descendants are visible in every orchestrator that farms work out to bidders.

The question answered: does the task’s own dependency structure admit completion, and how does work find its worker.

Reading the map

Laid side by side, the layers are not a hierarchy. No level grounds the others; each formalism cuts the assemblage differently and answers a question the others cannot ask, which is why the map is best read as a rhizome, with multiple entrances and no root. Session types will not tell you whether a worker is obliged to report failure; joint intention theory will not tell you whether the reporting protocol can deadlock; neither will tell you what the coalition can force, or what optimal decentralised behaviour costs.

For a working orchestration of LLM agents, the near-term useful cuts are the ones closest to the machinery: session types and choreographies for protocol conformance, epistemic preconditions for what each agent must be told, joint-intention-style obligations for failure reporting, and the Dec-POMDP result as standing justification for imposing structure. The strategic layer becomes load-bearing the moment agents represent different principals.