Multi-agent systems: communication, coordination and holonic organization

Build the foundations of multi-agent systems: when a system is really multi-agent (non-reducibility), communication protocols (speech-acts and FIPA-style message typing, observable conformance), hierarchical/collaborative/holonic organization, negotiation and collective decision, event-oriented agents and distributed coordination — and the new trust boundaries that appear the moment agents start talking to agents.

Track

Engineering

Module

10 · Agentic architectures

Prerequisites

Formal models of an agent and a taxonomy of architectures

Since 2023 the word "multi-agent" has been stretched to cover anything where several prompts talk to each other. The useful definition is narrower and older: a system is multi-agent when several independent decision loops act on a shared environment or on each other, and no single component determines what all of them decide. That last clause — non-reducibility — is the test. An orchestrator that calls the same model five times and decides what to do with each output is one agent with five modules, not five agents. Many "multi-agent" LLM systems are exactly that, which is not a flaw but a classification error.

The distinction matters because the hard problems of this lesson — conflict, partial observability, emergence, and the trust boundaries between agents — only appear when non-reducibility is real. If you have a single decision loop, you have a single agent's problems, and you should design it as such. If you have several, you inherit a web of relationships that no amount of making each agent smarter will secure, because the interesting failures live on the edges between agents, not inside them.

The standard modelling language for the cooperative, partially-observed case is the decentralized, partially-observable Markov decision process (Dec-POMDP): a set of agents, each choosing from its own actions on its own history of local observations, with a shared reward. Replace the shared reward with individual rewards and you have a stochastic game — so the difference between cooperation and competition is in the rewards, not in the architecture. A key, sobering result: deciding optimal joint policies is in a strictly harder complexity class than the single-agent problem. Splitting the observation changes the difficulty of the problem, which is why practical designs push back toward an almost-centralized form — communicating observations, imposing conventions, or serializing access to what is shared.

Non-reducibility

Each component has its own decision loop and no single component determines all decisions. The dividing line between a true multi-agent system and an orchestrator with modules.

Cooperation / competition

Cooperative: all agents optimize the same reward. Competitive: some action profiles help one agent at another's expense. The architecture can be identical; only the rewards differ.

Need to coordinate

Exists whenever the value of one agent's action depends on what others do simultaneously. Coordination is any restriction on joint policies — a convention, communication, a reservation, or a central authority — that rules out the unwanted combinations.

Dependency

What actually has to be coordinated: a shared resource, a producer-consumer order, simultaneity, or a task decomposition. Coordination is, concretely, the management of these dependencies.

There are four families of coordination mechanism, each with a known cost. A convention (a social law — "service s belongs to agent s mod K") costs no messages and removes collisions on the same object, but cannot resolve a global dependency like shared capacity. Communicating intentions ("I am about to restart api") reduces uncertainty, at a cost that depends on latency versus the environment's pace. A reservation in a shared registry (a lock or lease) serializes access and turns collision into waiting, at the cost of messages and a critical component that must release the reservations of agents that die. A central authority joins observations and assigns — recovering joint observability but at the cost of a single point of failure and the loss of non-reducibility. Each is a legitimate design choice; the point is to make it knowingly.

A protocol fixes which messages may be exchanged, in what order, and with what meaning. The classical tradition treated utterances as actions — speech acts — and gave agent communication languages a performative (the type of act: inform, request, propose) separated from the content. FIPA ACL standardized the message structure: performative, sender, receiver, content, and the conversation-control fields conversation-id, reply-with, in-reply-to and reply-by. Its semantics were "mentalist" — defined over the sender's beliefs and intentions — and the enduring result is that such a semantics is not verifiable from outside: a third party cannot check what an agent believes. With an LLM sender, intention is even less accessible than in a classical agent, so the only verifiable part of a protocol is the observable part.

Performative / message type

The illocutionary force of a message (inform, request, propose, accept, refuse, failure), separated from its content. Typing the envelope is what lets a third party check a conversation at all.

Observable conformance

A trace conforms if its projection is accepted by the protocol automaton, every reply references a prior message, deadlines hold, and no instance ends with an open commitment. Decidable from the trace alone; says nothing about sincerity or content quality.

Command vs. event

A command is a request to a specific receiver to do something, expecting a result and implying authority to order. An event is a notification of a fact that already happened, with no obligated receiver and no reply.

Correlation

The identifiers that make a conversation reconstructable: a message id (to detect duplicates), a reply reference (to link response to request), and a conversation/task id (to group a long interaction).

synthetic — a FIPA-style message envelope and a Contract-Net-style protocol as an automaton
message = {
  performative,          # inform | request | cfp | propose | refuse | accept | failure
  sender, receiver,
  conversation_id,       # groups one interaction
  message_id,            # detect duplicates
  in_reply_to,           # link reply -> request (Correlation Identifier)
  reply_by,              # deadline that closes a bidding round
  content,               # natural language / JSON -> the model interprets this part
}

# Contract Net, as a per-(initiator, participant) state machine:
#   manager --cfp-->            participant        (announce task, reply_by t)
#   participant --propose|refuse--> manager        (bid, or decline)
#   manager --accept|reject-->  participant        (award exactly one; reject the rest)
#   participant --inform-done|failure--> manager   (report result; must close)
#
# Conformance check (third party, on the trace, linear time):
#   - every in_reply_to references an earlier message
#   - reply_by deadlines respected
#   - exactly one award per task (global constraint across instances)
#   - no instance ends on an open commitment (a proposal never resolved)

Modern protocols — tool/context protocols between a model and its tools, and task-delegation protocols between agents of different organizations — specify message, transport and lifecycle far more precisely than FIPA did, but they leave the content's meaning in natural language, which is exactly what the LLM interprets stochastically. So the old problem reappears, displaced: the envelope is typed, the content is not. Two hard facts carry over from distributed systems. No finite number of retries guarantees a response over a lossy channel, and retrying without an idempotent receiver duplicates effects even on a reliable channel. The protocol automaton, deduplication, and causal ordering are deterministic components that surround the model — not tasks you hand to it.

Given several agents on one task, the architecture decides who decomposes, who executes, who hands control to whom, and how results combine. The families are describable by two things: the graph of authority and the shared state. Supervisor-with-workers is a star or tree where the supervisor decomposes, assigns and integrates. Routing-and-handoff moves a single token of control between agents, with a minimal, sufficient context — and, crucially, authority does not travel with the context: the receiving agent has its permissions by its own identity, not because the sender passed them. A blackboard inverts control: knowledge sources observe a shared structure and propose contributions, and a control component chooses which to run.

The holonic family is worth its own definition. A holon is a thing that is at once a whole and a part — a cluster is a whole made of services and a part of a region. A holarchy is a tree of holons where each level has a scope of decisions it can make alone, resolves locally what falls in its scope, escalates what does not, and can cooperate horizontally with peers. It sits between a central supervisor (which resolves everything but is a bottleneck and a single point of failure) and independent agents (which conflict). The risks live at the scope boundaries.

Holon

An agent with a scope of decisions it can take without consulting, a set of parts, and (except the root) a container above it. Simultaneously a whole and a part.

Holarchy

A tree of holons where each holon's scope is contained in its container's scope: it resolves locally within scope, escalates beyond it, and may cooperate with same-level peers.

Handoff

Transfer of a unique control token plus a bounded context. Correct only if the token is unique, the receiver is authorized, and the context contains what it needs and nothing it must not see.

synthetic — a holonic decomposition sketch for IT remediation (C1)
global_holon:                      # scope: change policy, risk budget
  region_holon_eu:                 # scope: drain a cluster, shift capacity
    cluster_holon_eu1:             # scope: restart a service locally
      - service_api    (remediate in local scope)
      - service_pay    (remediate in local scope)
    cluster_holon_eu2:
      - service_web
  region_holon_us: ...

# rules the structure enforces (checkable OUTSIDE the model):
#   scope(child)  subset-of  scope(parent)         # a holon can't exceed its container
#   local first   -> escalate what exceeds scope   # cluster restarts without asking
#   horizontal cooperation (eu1 lends capacity to eu2) must NOT jointly
#     violate a parent-level constraint neither peer can see   <-- the holonic trap

When agents do not share objectives — different organizations, or own agents given different local objectives by design — the system is a game, and you want rules that work even when each agent pursues its own interest. Auctions assign a scarce resource when each agent knows its own private value: in a second-price (Vickrey) auction, bidding your true value is a dominant strategy, so the auctioneer gets real valuations without modelling anyone. Contract Net, seen this way, is a first-price reverse auction on estimated cost — it works well among cooperative agents that declare real costs and badly among agents that inflate or shade their bids. Negotiation serves multi-dimensional deals with no fixed assignment rule; the engineering lesson is blunt: an agent that can be persuaded to accept below its reserve has no reserve. The model may draft and argue, but the reserve, the limits and the final acceptance are deterministic policy outside the model.

"Consensus" has three senses that must not be mixed, and conflating them is a common and expensive error.

• ▸Distributed-systems consensus: all correct processes record the same value. It has hard impossibility results and needs quorum protocols; it says nothing about whether the value is correct.
• ▸Agreement of opinions: agents average toward a value weighted by their influence in the network — which converges to a weighted mean, not to the truth; an obstinate agent can decide the group's answer.
• ▸"Consensus" among LLMs: a vote among correlated opinions. Because instances of one model are not independent voters, majority voting has a ceiling that no number of extra agents breaks — a point developed in the collaborative-architectures material.

And when what you aggregate is preferences rather than estimates, social choice sets the limits: with three or more alternatives there may be no Condorcet winner (a majority cycle), and every reasonable non-dictatorial rule is manipulable — an agent that can reason about how others will vote can gain by declaring a false order, and a goal-driven model will do so if its objective rewards it. These impossibilities are not dodged by better models.

An event-oriented agent perceives the world as a stream of facts that already happened and acts by emitting commands whose effects return as new events. This decouples producers and consumers in time, lets you reconstruct state by replaying the log, and makes each decision auditable — but it surfaces the problems a synchronous call hid: duplicates, reordering, and loss at the boundary between a database and a message broker. The discipline is to key the log so that what must stay ordered is ordered (events for one invoice on one partition), and to use causal ordering — a message carries enough information to be held until the events it depends on have been delivered — only where a rule spans keys.

Distributed coordination turns the mechanisms into something that survives processes pausing, dying and restarting. A work queue with leases assigns a task with an expiry: the holder renews while working, and if it stops, the task becomes visible again — but a holder that pauses longer than its lease (a long model call, say) does not know it lost the task and may write while another worker repeats it. The defence lives at the destination: a fencing token (the lease epoch) travels with each write and the store rejects a write whose epoch is stale. A single writer per entity (an actor per invoice, per customer, per service) serializes updates without locks and removes lost-update races by construction.

Every mechanism above adds an edge, and every edge is a trust boundary where the single-agent threat classes reappear in networked form — plus genuinely new ones (impersonation, Sybil, collusion) that have no single-agent analogue. An injection in one agent becomes a malicious instruction to another; an over-broad credential on one agent becomes a lever for a second; an unauthenticated channel lets an outsider masquerade as a trusted peer; a shared blackboard turns one poisoned write into persistent, re-readable poison for everyone. The signature failure of multi-agent systems is harm travelling along edges that nobody defended because each agent assumed the previous one had.

• ▸Authenticate messages so a peer cannot be spoofed — but remember authentication proves which agent sent the bytes, never that the content is true, correct or safe.
• ▸Tag cross-agent data with provenance (as in the memory lesson) so an untrusted-origin claim cannot silently become an instruction, only citeable evidence.
• ▸Scope delegated authority narrowly and bind it to identity, not to the handoff context, so a compromised peer holds a small lever.
• ▸Bound aggregate capability: the holonic trap and collective-decision mechanisms can let a feasible coalition reach an action no single member may — the subject of the collusion material.
• ▸Put human gates on high-impact, irreversible effects: a correctly-signed, properly-authorized, semantically bad message propagating across honest agents is a residual risk crypto cannot catch.

The durable posture is zero-trust between agents: no agent is trusted by virtue of being "inside" the system. Cryptography shrinks the surface — it removes spoofing, over-broad authority and unprovenanced data — but it cannot close it, because a perfectly authenticated message from a genuinely-authorized peer can still carry a poisoned claim or a harmful-but-permitted instruction. That remainder needs independent verification and blast-radius limits, not a better signature.

Expected direction: A defensible choice is a reservation in a shared registry with a capacity token (a convention alone cannot enforce the global capacity limit; a central authority recovers joint observability but loses non-reducibility and adds a single point of failure). The learner should give the message cost (roughly a request/response per attempted intervention) and note the registry as the critical component that must release leases of dead agents (fencing/expiry). Trust boundaries introduced by communication: the inter-agent message channel (control: authenticate so a peer cannot be spoofed; but authentication does NOT prove the message content is correct or safe) and any shared state/registry (control: provenance and least-privilege writes so a poisoned or over-broad write cannot become a trusted instruction). A strong answer also flags the aggregate-capability risk if two agents coordinate to exceed the limit.

What is the non-reducibility test, and why does it matter before building a multi-agent system?

A system is multi-agent only if there are several decision loops and no single component determines all decisions; an orchestrator calling one model five times is one agent with five modules. It matters because conflict, partial observability, emergence and inter-agent trust boundaries only appear when non-reducibility is real — otherwise you pay multi-agent costs (calls, conflicts, hard observability) for single-agent problems.

Why can a third party verify observable conformance of a protocol but not its mentalist semantics?

Observable conformance is decidable from the trace — correct performatives and order, resolved references, deadlines met, no open commitments. Mentalist semantics is defined over the sender's beliefs and intentions, which an outside observer cannot access, and with an LLM sender intention is even less accessible. So only the observable envelope, not the sincerity or the natural-language content, is checkable.

In a holarchy, how can two same-level holons each act validly yet break a global constraint, and where is that prevented?

Each holon decides within its own scope, but if two peers cooperate (e.g. lending capacity) their combined local decisions can violate a constraint of the level above that neither can see — the aggregate-capability trap. It is prevented outside the model: scope inclusion is a static check on the specification, and global constraints are protected by the coordination layer's reservations.

What does authenticating an inter-agent message prove, and what residual multi-agent risk remains after you authenticate and scope authority?

It proves which agent sent those exact bytes and that they were not altered — not that the content is true, correct or safe, nor that the sender was itself uncompromised. The residual risk is a correctly-signed, properly-authorized but semantically bad message (a poisoned claim, a wrong plan, a harmful-but-permitted instruction) propagating across honest agents, which needs independent verification and human gates on high-impact actions.