8  Coordination and Distributed Problem Solving

The previous chapter built a team and trusted it to act. What it quietly assumed was that agents which agree on what to do can simply go and do it. They cannot: a plan settles what and who, not the thousand smaller questions of when, in what order, and over whose copy of the shared state. Two coders handed non-overlapping tickets still contrive to edit the same file, and one of the two writes is silently lost. Two robots meet in a corridor wide enough for one and freeze, each waiting with perfect courtesy for the other to go first. Neither is a failure of teamwork in the sense of Section 7.2; every agent wanted the right thing. They are failures of coordination — the management of concurrent, interdependent action — this chapter’s subject.

The purest picture of the problem has nothing to do with software. Put several robots in a shared warehouse, give each a destination, and require them to get there without colliding: multi-agent path finding is trivial to state, genuinely hard to solve, and coordination stripped to its essentials — a shared resource, incompatible simultaneous demands, no collision allowed. But the warehouse is merely the vivid case: the same structure turns up wherever agents act at once upon anything held in common, the team’s repository and task board first of all.

The modern agent stack meets all this under a litter of newer names — shared-state management, locking, orchestration topology, parallel subagents — and rediscovers the classical failure modes at precisely the classical places: the lost write, the stale read, the two agents each blocked on the other, the work done twice because neither knew the other was at it. The agents, throughout, want to coordinate — the difficulty here is mechanical, not strategic; Part IV will withdraw even that.

8.1 The Coordination Problem: Managing Interdependence

Coordination is the management of dependencies between activities, and that one sentence, owed to Malone and Crowston, carries most of the concept (1994). The test is subtraction: if two activities could each be carried out in perfect ignorance of the other, owing nothing to each other’s order, there is nothing to coordinate — coordination is exactly the work their dependence creates. It is not an optional refinement but the bill the parcelling-out runs up. The moment the orchestrator of Section 7.4 split implement the export format into a serialiser, tests, and docs, it manufactured dependencies that had not existed while the task was whole: tests on the serialiser’s interface, docs on the finished API, all three on the single repository they must share. Decomposition buys parallelism and sells dependence in the same breath; the price, paid later, is coordination.

Dependencies are not all of one kind, and naming the kind is half of choosing the remedy — the pay-off of treating coordination as a subject rather than a knack. A shared-resource dependency arises when several activities need the same limited thing at once: the one repository, a particular file, the team’s token budget, a square of warehouse floor. A producer–consumer dependency holds when one activity yields what another needs before it can begin: the serialiser’s interface must exist before the tests can be written against it. A simultaneity dependency constrains activities to happen together, or forbids them from happening together — the two robots that must not enter the one-wide corridor at the same instant. And the task–subtask dependency is the decomposition of Section 7.4 itself. Each kind summons its own family of mechanisms; the taxonomy converts a vague unease into a specific question with a specific answer. The positive and negative relationships Section 7.5 drew between agents’ plans were a slice of this same structure; coordination manages them before they bite.

Two of these dependencies pose questions with names of their own. The shared-resource dependency, asked of agents and tasks, becomes the problem of allocation: which agent does which task, who holds the write-lock on the module. The producer–consumer and simultaneity dependencies, asked of time, become the problem of scheduling: in what order the activities run, so that producers finish before consumers start and no two conflicting actions land at once.

This differs from the delegation of Section 7.4: delegation manufactured a commitment — it got some agent to undertake a task — while allocation asks whether the assignment was a good one, balancing load, respecting dependencies, leaving the fewest conflicts to settle. A team can delegate every task flawlessly and still have allocated them abominably, piling four jobs on one agent while three sit idle. Getting the assignment and the order right is coordination’s first labour; doing it well when the choices interlock is the harder matter Section 8.5 returns to. The robotics wing made the naming formal: Gerkey and Matarić’s taxonomy of multi-robot task allocation sorts the problem along three binary axes — one task at a time or several, one robot per task or a team, assignment instantaneous or planned over a horizon — and shows several cells to be old, well-studied optimisation problems of known hardness (2004). It transfers to software teams unaltered: an orchestrator dispatching subtasks sits somewhere in that grid whether or not it knows its coordinates, and the cell fixes which allocation machinery, from greedy assignment to the auctions of Chapter 12, is even a candidate.

It is tempting to suppose that a team which has settled its joint intention (Section 7.2) and its shared plan (Section 7.3) has, in settling them, already coordinated; it has not. A shared plan fixes what the team will do and who will do each part; it characteristically leaves when, and over which shared thing, to be worked out in the doing — the plan never said not at the same time, having no vocabulary for the clash. The musicians of Section 7.3 make the point precisely: an agreed score settles the notes and the parts, yet four players reading it in one room can still produce a shambles, because a score does not keep time. Coordination is the keeping of time — the layer a plan leaves implicit. Teamwork decides the music; coordination is what makes it land together.

How much coordination a team needs rises and falls with how tightly the work is coupled. A decomposition into nearly independent parts — the prize Section 7.4 held out — leaves few dependencies to manage; a decomposition whose parts are forever touching condemns the team to coordinate at every step. The warehouse shows the gradient at a glance: a handful of robots in open space barely coordinate at all, whereas the same robots in a tight maze must negotiate almost every square. This yields the first and most general lesson of the subject, one the distributed-AI tradition understood well (Jennings, 1996): the cheapest dependency to coordinate is the one that was designed out. What cannot be designed out must be paid for, and the remainder of this chapter is, in effect, a catalogue of ways to pay.

The dependencies named so far are a static anatomy; what lends coordination its urgency is that the needing so often happens at the same time. The shared resource touched concurrently is the dependency whose mismanagement does not merely waste effort but corrupts: two activities writing the same state at once produce not a slow team but a wrong answer. Before the remedies, it is worth looking squarely at the hazard they all exist to prevent.

8.2 Acting at Once: Races, Mutual Exclusion, and Consistency

Set two agents to work on the same file at once and watch what happens. Each reads the file as it stands; each makes its change to the version it read; each writes the result back. Whichever writes second wins, and the first agent’s work vanishes without a trace — not merged, not flagged, simply gone, overwritten by a sibling that never saw it. This is a race condition: an outcome turning on the order in which concurrent activities happen to interleave — an order nobody specified and nobody controls. Its special cruelty is that it usually works: most interleavings are benign, and the lost update surfaces only when the timing lines up exactly wrong — rarely, unrepeatably, and almost never during testing. A race is a bug that hides behind its own improbability, and a system that spawns workers to write shared state with no thought for their interleaving is a race condition that has merely not yet been unlucky.

The cure is as old as the disease: mutual exclusion. Identify the stretch of activity that touches the shared state — the critical section — and arrange that at most one agent is inside it at once. Dijkstra set the problem out formally in 1965 (1965); the lock, the mutex, and the semaphore are all ways of enforcing the condition he named. Our team takes a write-lock on the module, or funnels every change through an orchestrator that applies them one at a time; either way the free-for-all becomes an orderly queue, and the lost update cannot happen because the losing write never happens. Mutual exclusion buys safety with concurrency: while one agent holds the lock the others idle, and that idling — contention — is the first showing of a cost this chapter keeps meeting.

On a single machine a lock is a modest thing, a flag in shared memory the hardware will let only one processor flip. Among distributed agents — separate processes, each with its own copy of everything, conversing only by message — there is no shared flag to flip, and the modest thing swells into a protocol: distributed mutual exclusion, agents negotiating by message who may enter — a genuine piece of engineering rather than a library call.

Worse, the very notion of order frays. Ask which of two writes came first and, absent a clock the agents share, there may be no fact of the matter. Lamport’s answer became one of the founding results of distributed computing (1978): give up the fantasy of a single global time and settle for a happens-before relation, a partial order recording only which events could have influenced which, kept by logical clocks the agents pass back and forth. The lesson beneath the algorithm is what makes distributed coordination hard in principle — separate agents do not share a now, and any agreement about the order of their actions must be manufactured, at a cost, rather than read off the world.

8.2.1 Happens-Before, Formally*

Lamport’s relation is brief enough to give in full. The events of the system are the individual actions of the agents, among them the sending and receiving of each message. For events a and b, write a \to b — read “a happens before b” — for the smallest relation satisfying three clauses: if a and b belong to the same agent and a comes earlier in that agent’s own sequence, then a \to b; if a is the sending of a message and b its receipt, then a \to b; and if a \to b and b \to c, then a \to c. Nothing else counts. Two distinct events may therefore stand in neither order, in which case they are concurrent,

a \parallel b \;\;\text{iff}\;\; \neg(a \to b) \wedge \neg(b \to a),

and their concurrency is not ignorance but fact: neither could have influenced the other. What a logical clock provides is a numbering that respects the relation — an integer C(a) for each event a, satisfying the clock condition,

a \to b \;\Rightarrow\; C(a) < C(b),

and Lamport’s rule keeps it with almost nothing: each agent ticks its counter at every event, stamps the counter onto each outgoing message, and on receipt advances its own counter past the stamp before ticking. Note that the implication runs one way only. C(a) < C(b) does not make a prior in any causal sense; the clocks — ties broken by any fixed rule, say by agent name — extend the partial order to a total one by choosing an order for concurrent events, which is exactly the sense in which agreement about order is manufactured rather than found: even the tiebreak is arbitrary.

One integer per agent and two functions over it are the whole apparatus,

def tick(c: int) -> int:              # every event ticks the counter
    return c + 1

def recv(c: int, stamp: int) -> int:  # a receipt lands past the stamp
    return tick(max(c, stamp))

coder, reviewer = 2, 0  # the coder has seen two events; the reviewer none
C_a = coder = tick(coder)       # the send a; C_a stamps the message
C_b = reviewer = recv(reviewer, C_a)  # the receipt b leaps past the stamp
C_a, C_b, C_a < C_b     # -> (3, 4, True): the clock condition holds

and the final line is the clock condition holding for the send–receive pair. The receiver’s leap from nought to four repays a glance: a Lamport stamp is not a count of the agent’s own events — the receipt was this agent’s first, yet it is stamped four — but a bound on the length of the causal chain behind it.

8.2.2 Deadlock and Its Cousins

Mutual exclusion applied without care breeds the opposite catastrophe. Give each of two agents one resource and have each wait for the other’s, and both wait for ever: deadlock. The two robots frozen nose to nose in the one-wide corridor are deadlocked; so are an orchestrator and its subagent each blocked on the other. Coffman and his colleagues named four conditions that must all hold for deadlock to arise — mutual exclusion, hold-and-wait, no preemption, and a circular chain of waiting — with the corollary that denying any one makes deadlock impossible (1971). Dijkstra’s dining philosophers is the picture every student meets; the agent stack supplies fresh instances weekly. Its gentler cousin, livelock — both agents notice the conflict, both back off politely, both retry in lockstep, for ever — is the corridor shuffle rendered in code: motion without progress.

Even where nothing collides outright, distributed agents drift out of agreement about the state they share: the instant one agent updates the shared truth, every other agent’s copy is stale until it hears. An agent acting on a stale copy is not malfunctioning; it is reasoning correctly from something that has quietly stopped being true, and the mistake is the harder to catch for looking entirely sensible. This is distributed consistency: several agents holding different versions of the same state. The distributed-systems tradition long ago mapped the trade-off it forces. Strong consistency — every read sees the latest write — is achievable but dear, each reader coordinating with the writer before proceeding; eventual consistency is cheap and lets readers race ahead, at the price of letting them be wrong for a while. The pragmatic remedy is the humble one: a single source of truth — the shared board of Section 6.6, authoritative by construction — that agents read from and write to rather than each trusting a private copy. Consistency is the common ground of Section 6.2 put under the strain of concurrent editing.

None of this is new — what should trouble the engineer is that the tools so rarely act as if they know it. Races, mutual exclusion, deadlock, and consistency are the settled canon of distributed systems, decades deep and taught to undergraduates (Tanenbaum & van Steen, 2023) — yet the post-mortems of multi-agent language-model systems keep turning up exactly these failures under new labels, filed as flaky and non-deterministic rather than under their textbook names (Cemri et al., 2025) (Table 8.1). The remedy is not novel machinery but the discipline to apply the old: serialise what must not overlap, order what must not be reordered, and keep one authoritative copy of whatever everyone relies on. Where no authoritative copy can be appointed in advance, the same canon supplies the appointment machinery: leader election, and the consensus protocols of the Paxos and Raft lineage; Section 20.9 meets their adversarial extreme, where members do not merely fail but lie. Yet locking and its relatives are the pessimist’s remedy, paying to guard against a clash on every access. There are lighter ways, and the lightest costs nothing at runtime because it was settled in advance: the rules of the road, agreed so that coordination becomes unnecessary rather than merely safe, are where we go next.

Table 8.1: The concurrency canon under new labels — each classical hazard, the guise it wears in a multi-agent language-model system, and the decades-old cure the framework rarely applied for you.
Hazard What goes wrong Where it shows in the agent stack Classical cure
Race condition The second writer wins; the first write vanishes — unmerged, unflagged, simply gone Two agents editing one file; workers spawned to write shared state; filed as flaky or non-deterministic Mutual exclusion — a lock, mutex, or semaphore round the critical section
Deadlock Every party blocked on another blocked party — all four Coffman conditions holding at once An orchestrator and its subagent each blocked on the other; a run that simply hung Deny any one of the four Coffman conditions
Livelock Both agents notice the conflict, both back off, both retry in lockstep — motion without progress The corridor shuffle rendered in code Break the symmetry — randomised backoff with jitter, or a priority order fixing who yields
Stale read (inconsistency) An agent reasons correctly from a copy of the shared state that was true and has quietly stopped being so Each agent holding its own context after another updates the shared truth A single source of truth; strong or eventual consistency, chosen knowingly

8.3 Coordinating Without Talking: Conventions and Social Laws

Every day, millions of drivers solve a coordination problem of some delicacy — who passes on which side — without a single message, a central controller, or a moment’s negotiation. They solve it because the question was settled long before any of them set out: drive on the right, or, in stubborn jurisdictions, the left. A convention of that kind is the cheapest coordination there is: the work was done once, in advance, and every later encounter draws on it for free. Our software team has the same instrument to hand. A standing rule that the architect owns the API module and the coders never edit it directly makes the file-race of Section 8.2 not unlikely but impossible — not locked against, but never attempted. Where the last section policed conflict as it happened, a convention arranges that the conflict never arises.

Two features of David Lewis’s classic analysis bear directly on agents (1969). The first is what sustains one: a regularity that solves a recurring coordination problem and holds because everyone conforms and expects the others to, so that no one gains by breaking it alone — the driver who takes the left on principle does not reform the system, merely crashes. A convention in force needs no enforcement; it is self-policing in a way that a locking protocol, forever checking, is not. The second feature is that conventions are typically arbitrary: there is nothing to choose between right and left; what matters is that everyone adopt the same rule. The content is incidental and the agreement everything — a convention is, at bottom, a piece of Section 6.2’s common ground, coordinating precisely because it is mutually known to be shared.

For human conventions, which mostly have to grow, the arbitrariness is a nuisance; for artificial agents it is an opportunity, and Shoham and Tennenholtz drew out its consequences under the name of social laws (1995). If you are building the agents, you need not wait for a convention to emerge; you can impose one at design time, such that any agent obeying it is guaranteed to coexist with the others without conflict. The traffic law is again the model — and was theirs: the motivating example of that literature is mobile robots on a grid, kept collision-free by rules of the road laid down in advance — this chapter’s warehouse, legislated for before a single run. They also posed the synthesis problem of finding a set of social laws that leaves every agent able to reach its goals while never colliding with another (1992), and showed it computationally hard: good conventions are worth designing with care rather than stumbling into. The pay-off is plain: coordination performed once, at design time, amortised across every run the system will ever make.

What a convention saves at runtime it pays for in rigidity. A social law is coarse: it forbids a whole class of actions to prevent the few that would have conflicted. A file-ownership rule occasionally makes a coder wait on the architect for a change it could, this once, have made safely itself. A convention must be known to all in advance, and it adapts to nothing: noticing the exceptional situation is exactly the runtime work it exists to spare. The trade is therefore clean and general. When the coordinating situations are frequent and similar, a convention is the right instrument and its rigidity a bargain; when they are rare, varied, or genuinely novel, the flexibility of a runtime mechanism — a lock, a negotiation — earns its cost. Coordinate in advance where you can; pay at runtime only where you must.

In a system of language-model agents the convention is often the single highest-leverage coordination mechanism available, because it can be installed with a sentence. A shared coding standard lets separate agents’ code compose without negotiation; module-ownership rules head off the write-race; an agreed output schema makes one agent’s result a valid input to the next, turning a fragile hand-off into a contract; naming conventions and the message protocols of Chapter 5 are the same move. Because a language model will mostly follow an instruction, a convention can live in the system prompt — a line of English standing in for an entire locking subsystem, about as good a bargain as the field offers. The catch is the one the substrate always springs: a model that mostly follows a convention will now and then forget it, reinterpret it, or be talked out of it, and a convention breached is silent in just the way a lock is not. Conventions among agents that cannot be trusted to keep them therefore want a backstop — mutual exclusion, or a cheap check that the rule was in fact obeyed.

Two lines mark where conventions end. Push one far enough — give it teeth, sanctions, someone to judge and enforce it — and a convention hardens into an institution; that is the material of Chapter 13, in the world Part IV opens. And where this section has treated conventions as designed, they can equally emerge, growing from repeated interaction with no designer, as the rules of language and the paths worn across a field do; that is the story of Chapter 15, and the mathematics of which convention such growth crowns waits in Section 15.3.1. Every convention, imposed or emergent, coordinates without anyone having to talk. But some coordination cannot be settled ahead of time, because it turns on the state of a shared world that reveals itself only in the doing. For that, agents fall back on a different trick — coordinating through the shared environment itself, reading and writing the very medium they act upon.

8.4 Coordinating Through the World: Blackboards and Stigmergy

There is a third way, which neither settles the matter in advance nor requires the agents to speak. A coder that finishes the serialiser sends no announcement; it commits, and the commit is itself the signal. The next agent, finding the repository altered, reads what was done and acts on it, and the two have coordinated without either addressing, or indeed knowing of, the other. The coordination lives in the shared medium the agents both act upon: coordination through the environment, the most self-effacing of the three: no agent need hold a model of any other — the world holds it for them.

We have met the classical form already: the blackboard that Section 6.6 traced back to Hearsay-II (Erman et al., 1980). There it appeared as the ancestor of shared state; regarded as coordination, its defining virtue is the decoupling Nii drew out of the pattern (1986): the specialists know nothing of one another, invoke one another never, and interact solely through the marks they leave on the board. Coordination becomes opportunistic, each agent acting whenever the shared state offers it something to do, rather than dictated by a plan of who goes when. A blackboard is not merely a place to keep what the team knows but a mechanism for coordinating without conversing.

Nature arrived at the same device long before, and the biologist Grassé named it stigmergy after watching termites build (1959). A termite’s action alters the environment — a dab of soil placed just here — and the altered environment is exactly what prompts the next action, so that a cathedral of a nest rises with no blueprint, no foreman, and no termite anywhere holding the plan. The tidiest example is the ant trail: an ant returning from food lays a chemical mark, other ants are drawn to the stronger marks and reinforce them, and the colony converges on short routes though no ant compares two paths (Theraulaz & Bonabeau, 1999). Stigmergy is coordination pared to the barest mechanism there is — no plan, no leader, no message, no goal held in any single head — and the ancestor of the swarm methods, ant-colony and particle-swarm optimisation (Bonabeau et al., 1999), that Chapter 15 takes up.

Blackboard and stigmergy are two faces of one principle — put the coordination in the environment, not in the agents — and what that buys is exactly what a system of many, changeable, unreliable agents most needs: decoupling, since an agent need not know who else is at work nor even overlap with them in time; openness, since agents may join or fall away freely; and robustness, since no coordinator’s failure stops the world — the system sags gracefully rather than snapping as agents drop out.

The contemporary agent system is thick with blackboards, most of them unlabelled. The shared workspace of Section 6.6 — the visible task board, the ticket queue, the scratchpad — is a blackboard in all but name: agents read it, take up what they are equipped to do, post their results, and leave the altered board to prompt the next. The repository is frankly stigmergic: a commit is a trace laid down for whoever comes after, a pheromone in version control, and a pipeline of agents that each reads the repo, does its part, and commits is an ant colony with better tooling. The pattern is a mainstay of modern frameworks — a shared state object every agent may read and revise — and its appeal is the old one: it asks the least of any single agent. Built deliberately rather than stumbled into, it is one of Chapter 18’s architectural patterns.

The bill, though, arrives in two parts. The first was written a section ago: a shared medium is shared state, and every hazard of Section 8.2 applies without mercy — the blackboard two agents post to at once is a race, the board one agent read a minute ago is already stale, and the repository is a merge conflict biding its time. The second is the price of the very decoupling that made the pattern attractive: coordination that lives in the environment is coordination no one is holding, hard to inspect and harder to debug, and compounding local reactions can produce collective behaviour no agent chose and no designer foresaw — the emergent dynamics Chapter 15 treats in earnest.

And there is a limit the mechanism cannot cross. Traces in a shared medium serve beautifully when contributions can be posted independently and assembled loosely, but they do not, on their own, settle a genuine clash of choices — the case in which each agent’s choice constrains the other’s. When the parts interlock that tightly, leaving marks is not enough; the agents must reconcile actively, trading partial commitments until their choices fit. That harder problem comes next.

8.5 Interlocking Choices: Distributed Search and Constraints

Some choices will not be prised apart, however the work is arranged. When the architect settles the shape of an API and a coder writes against it, neither decides alone: the architect’s choice of signature fixes what the coder may call, and the coder’s needs constrain which signatures are any use. There is no order in which one simply goes first. A trace left on a board (Section 8.4) does not help, because the mark the coder would read is the very thing that must accommodate the coder; and a convention fixed in advance does not help either, nobody having known the right interface before the work began. The two choices interlock, and the only way to satisfy both is to settle them together. This is the general problem of coordinating interdependent decisions — the one the earlier mechanisms were built to sidestep rather than solve.

The distributed-AI tradition gave the problem a clean form. In a distributed constraint satisfaction problem, each agent controls some variables, constraints link variables held by different agents, and the team must find a joint assignment that satisfies every constraint — with no agent ever seeing the whole problem, only its own variables and the constraints it shares (Yokoo et al., 1998). Its optimising cousin, the distributed constraint optimisation problem, replaces hard constraints with costs and asks for the joint assignment of least total cost — the shape most real coordination has: not a wall between legal and illegal but a landscape of better and worse, searched together (2005). Put this way, Section 8.1’s allocation and scheduling are distributed constraint problems in disguise. The difficulty is intrinsic: no agent holds the global picture, so the solution must be found by exchanging messages, and the messages, in the worst case, multiply as unkindly as the problem itself.

8.5.1 Distributed Constraint Optimisation, Formally*

The optimising form is worth setting down exactly. Take the agents N = \{1, \dots, n\} and variables x_1, \dots, x_m, each variable x_i ranging over a finite domain D_i and owned by exactly one agent, which alone may set it — the architect owns the interface signature, each robot its own route. Constraints become costs: wherever two variables bear on one another, a cost function

f_{ij} : D_i \times D_j \to \mathbb{R}_{\ge 0}

prices every combination of their values, zero for pairs that fit and rising with the badness of the fit; a hard constraint is the special case that prices its forbidden combinations beyond any willingness to pay. The pairs that carry a cost function are the edges of the constraint graph, and the problem is to find a complete assignment — a value for every variable — minimising the total cost,

\sum_{(i,j)} f_{ij}(x_i, x_j),

the sum running over the graph’s edges. What makes the problem distributed is who knows what: each agent sees its own variables, their domains, and the cost functions on its own edges, and nothing else — no agent ever holds the sum the team is jointly minimising. And when each agent owns a single variable, as the standard treatments assume, the constraint graph is node for node the coordination graph the next subsection introduces.

8.5.2 Locality and Convergence

What keeps this from being hopeless is that interaction is almost always local. The architect’s interface constrains the coder who calls it and nobody else; two robots contend only where their paths might cross. A coordination graph makes that structure explicit — a node for each agent, an edge wherever two agents’ choices directly constrain each other — and turns a forbidding global problem into a web of small local ones. An agent need reconcile its choice only with its neighbours; their adjustments ripple onward; and a solution assembles out of local agreements without any agent ever confronting the whole. The sparser the graph, the cheaper the coordination, which restates the lesson of Section 8.1 in a new key: the shape of the interaction graph, more than the number of agents, decides what a system will cost to coordinate.

How those local agreements are reached overturns an assumption the concurrency hazards seemed to force. There, inconsistency between agents’ views was a hazard to be prevented; here it is a phase to be worked through. Lesser and Corkill’s principle of functionally accurate, cooperative computation held that a distributed system need not keep every agent complete and correct at every step (1981): agents may compute on partial, tentative, even mutually inconsistent local results, exchange them, and converge, reaching the right global answer though no agent was ever locally certain. Coordination becomes iterative — each agent posts its current best guess, sees what its neighbours posted, revises, and repeats until the guesses stop moving and the choices fit. Partial global planning (Section 7.5) is exactly this in the guise of plans; the architect and coder passing drafts back and forth run the same loop by hand. What the theory adds is an account of when such a loop will settle and when it will merely oscillate.

The warehouse robots of the chapter’s opening are the exemplar the field returns to. Multi-agent path finding is a distributed constraint problem in its starkest form: each agent’s variables are the cells of its route through time, the constraints forbid any two agents from occupying the same cell at the same step, and a solution is a set of jointly collision-free routes (2019). It is the cleanest illustration of everything this section has said, and genuinely, provably hard: optimal collision-free routing for many agents is NP-hard. The field’s canonical answer, conflict-based search, is the section’s philosophy as an algorithm: plan each robot separately and cheaply, and pay for coordination only where the separate plans actually collide, branching on the conflict and re-planning under the new constraint (Sharon et al., 2015). It is also the chapter’s recurring lesson in miniature: this old, exactly-specified search problem is now, increasingly, handed to a learned policy that maps each robot’s local view straight to a move — the composed-versus-learned question Chapter 14 takes up in full. The problem is a fixture of the 1980s; the method is younger than the reader’s laptop.

Two lines bound this section. The first is the assumption quietly underwriting every method in it: that the agents cooperate — that they report their true costs and want the joint solution good rather than merely good for them. Relax it, and the distributed optimisation stops being a search and becomes a game: the same allocation problem, now among agents who will misreport to win it, the province of auctions and mechanism design in Part IV. The second line is that everything here has been the thoroughly decentralised way, information and computation staying local with no agent in charge; the alternative is to gather the whole problem to a single coordinator and solve it centrally. Which to choose — central or distributed, flat or hierarchical — is not a detail but the defining architectural decision of a multi-agent system, and each option pays a different price: the price, and the topologies that pay it, are where the chapter ends.

8.6 Topologies and the Price of Coordination

Where should the coordinating happen? Every mechanism of this chapter has to run somewhere. At one pole stands centralised coordination: a single coordinator holds the whole picture and settles everything, as the orchestrator of our running example does. At the other stands the decentralised, or peer-to-peer, arrangement: nobody in charge, agents coordinating locally through the conventions of Section 8.3, the shared media of Section 8.4, or the constraint-passing of Section 8.5. Between them sits hierarchy, coordinators of coordinators. These are different topologies — different placements of the coordinating — and each is a different bargain (Figure 8.1).

%%{init: {"theme": "base", "themeVariables": {"primaryColor": "#E8ECFF", "primaryBorderColor": "#4054B2", "primaryTextColor": "#16171B", "lineColor": "#3B4351", "edgeLabelBackground": "#FAF7F0", "clusterBkg": "#EFE9DC", "clusterBorder": "#766F65"}, "flowchart": {"rankSpacing": 30, "nodeSpacing": 42, "subGraphTitleMargin": {"top": 14, "bottom": 6}}}}%%
flowchart TB
  subgraph CEN["Centralised"]
    direction TB
    C(["coordinator (bottleneck)"])
    C --> W1(["agent"])
    C --> W2(["agent"])
    C --> W3(["agent"])
    C --> W4(["agent"])
    C --> W5(["agent"])
  end
  subgraph HIER["Hierarchy"]
    direction TB
    T(["coordinator"])
    T --> M1(["sub-coordinator"])
    T --> M2(["sub-coordinator"])
    M1 --> A1(["agent"])
    M1 --> A2(["agent"])
    M2 --> A3(["agent"])
    M2 --> A4(["agent"])
    M2 --> A5(["agent"])
    M2 -.->|"escalation"| T
  end
  subgraph MESH["Decentralised (mesh)"]
    direction TB
    N["every pair must stay consistent"]
    P1(["agent"]) --- P4(["agent"])
    P1 --- P5(["agent"])
    P2(["agent"]) --- P4
    P2 --- P5
    P3(["agent"]) --- P4
    P3 --- P5
    N ~~~ P4
  end
  W3 ~~~ T
  A3 ~~~ P1
  classDef gate fill:#F7E6B5,stroke:#8A5A00,color:#16171B
  classDef world fill:#EFE9DC,stroke:#766F65,color:#16171B
  class C gate
  class N world
Figure 8.1: The three coordination topologies drawn as wiring, five agents apiece: centralisation’s single hub, hierarchy’s coordinators of coordinators, and decentralisation’s leaderless mesh. Each carries its price on its face — the hub a bottleneck, the hierarchy paying an escalation hop across cluster boundaries, the mesh obliging every pair to stay consistent by themselves.

Centralised coordination is the easiest to build and the easiest to trust: one mind sees everything, so consistency comes free. The orchestrator-worker pattern is centralisation in modern dress, and its popularity is no accident: it is the arrangement a single designer can hold in their head. What it charges is threefold: the coordinator is a bottleneck, serialising work that might have run in parallel; it is a single point of failure; and it must acquire the global picture it relies on, costly in messages and stale under partial observability. Decentralisation makes the opposite trade. With no hub to overload it scales; with no coordinator to lose it survives, degrading gracefully as agents drop. The price is the mirror image: consistency must be worked for, convergence is slower and not always assured, and the system’s behaviour is emergent, hard to predict and harder to debug.

Hierarchy is the compromise the world mostly settles on: coordinate locally within small clusters, set a coordinator over each, and escalate upward only what crosses a boundary. It bounds the communication any one node must bear and keeps a measure of oversight, at the cost of the rigidity and reporting delay that every layer of management adds — a truth about human organisations that transfers to agent organisations without amendment. Table 8.2 sets the options side by side.

Table 8.2: The three coordination topologies and the chief price each pays. No topology wins outright: centralisation and decentralisation make exactly opposite trades, and hierarchy buys a bounded compromise — which is why placing the coordinating is an architectural decision rather than a detail.
Topology Consistency and predictability Scalability and robustness Chief cost
Centralised High — one source of truth by construction; behaves like one program Poor — the coordinator is a bottleneck and a single point of failure Gathering a global picture — costly in messages, and stale under partial observability
Decentralised (peer-to-peer) Low — the concurrency hazards return, and behaviour is emergent, hard to debug High — growth adds only local coordination, and losing agents degrades gracefully Slower, not-always-assured convergence
Hierarchy Moderate — consistent within clusters, escalation across boundaries Bounded — no node bears more than its cluster; a failed sub-coordinator costs one cluster, not the team Rigidity and reporting delay from every layer of management

Underneath the choice lie three quantities the preface named, and no topology holds all three at their best at once. The first is communication cost: coordination is made of messages, and a topology decides who sends how many to whom. The second is concurrency: how much may proceed at once — centralisation serialises through its coordinator; decentralisation unlocks parallelism but reopens the races. The third, and the deepest, is partial observability: no agent sees the whole, and the cost of manufacturing a global view can exceed the value of ever holding it — the standing case for keeping coordination local: a global view is often too dear, too stale, or too fleeting to be worth assembling. Each topology is a different answer to which of the three to spend to spare the others.

Every section of this chapter has circled one fact, and here it can be said plainly: coordination is never free. It was paid in contention when agents waited on a lock (Section 8.2), in rigidity when a convention forbade the safe along with the unsafe (Section 8.3), in opacity when the environment did the coordinating (Section 8.4), and in messages when interlocked choices had to be reconciled (Section 8.5). In a system of language-model agents the bill is itemised in tokens and time: every status report, every read of the shared state, every round of the converge-and-revise loop is tokens off the budget and latency on the clock; the running example’s bounded budget is consumed by the coordinating as surely as by the work. A team that coordinates lavishly can spend its whole allowance staying in step and ship nothing — the standing meeting that should have been an email, re-enacted at machine speed.

This turns the engineer’s task on its head: the goal is not to maximise coordination but to buy just enough of it — enough coherence to avert the catastrophes of unmanaged concurrency without letting the coordinating devour the doing. The chastening evidence is that multi-agent systems routinely cost several times a lone agent’s tokens for the same result, and repay the overhead only when the task genuinely decomposes and the parallelism earns its keep (Anthropic, 2025); a great many would be faster, cheaper, and sturdier as a single agent with a good tool. And when such systems do fail, they fail overwhelmingly at the joins — not agents too dim to do their parts, but a team that never managed to act as one (Cemri et al., 2025).

So the chapter’s thesis arrives, earned: a topology is not a coordination mechanism. An architecture diagram — boxes for agents, arrows for messages, a supervisor perched on top — names a placement of the coordinating and supplies none of it; the coordination is the machinery these pages have catalogued, and every arrow in the diagram is a cost that something has to pay. To choose a topology is to choose which of those costs to bear. With this the cooperative half of the book is complete: Chapter 7 taught willing agents to share a goal and a plan; this one taught them to carry it out at once, over a shared world, without colliding. Two assumptions now come due. The agents have been supposed to want the same thing — and Part IV withdraws the supposition, asking what coordination becomes when agents pursue their own ends and a topology must be not merely efficient but a mechanism robust to those who would game it. And the coordination here was composed, each mechanism chosen and placed by hand, where a capable agent might instead learn to coordinate; which of the two the field should reach for, the warehouse robots have already whispered and Chapter 14 asks outright. The team can now act as one; whether it is best built to, or taught to, is where the book goes next.

8.7 Summary

  • Coordination is not teamwork; it is what teamwork still needs. A shared goal and a joint plan (Chapter 7) settle what to do and who does it; coordination settles when, in what order, and over whose copy of the shared state — and a perfect plan can still deadlock.
  • Concurrent action over shared state is hazardous in old, well-charted ways. Races, lost updates, stale reads, and deadlock are the distributed-systems canon; two agents editing one file is a race condition with a decades-old fix that the framework probably did not apply for you.
  • Some coordination can be bought in advance, for nothing at runtime. A convention or social law — drive on the right; one agent owns this module — lets agents stay clear of one another without communicating: the cheapest message is the one no one ever has to send.
  • Agents can coordinate through the world instead of through each other. Blackboards and stigmergy read and write a shared medium — the task board, the repository itself; one agent’s commit is a trace the next one acts upon.
  • When choices interlock, coordination becomes distributed constraint solving. Where no clean division of the work exists, agents trade tentative partial results toward a consistent whole; distributed constraint optimisation is the canonical machinery, multi-agent path finding the canonical hard case.
  • Topology is a design decision, and coordination is never free. Centralised is simple but bottlenecks; decentralised scales but is harder to keep coherent; and every mechanism now bills in latency and tokens: buy just enough coherence to avoid collision, and no more.

8.8 Exercises

Exercise 1. The orchestrator splits add CSV export into five tickets, each costing 2,000 tokens of work and placeable on either of two coders: t_1, the serialiser, which edits export/ and schema.py; t_2, the round-trip tests, which are written against t_1’s interface and must run against the migrated schema; t_3, the docs page, which documents t_1’s finished API; t_4, the schema migration, which edits schema.py; and t_5, a repository-wide lint sweep that rewrites files under export/, schema.py, and the docs, but is configured to leave tests/ alone. (a) List every dependency among the five tickets and classify each by kind — shared resource, producer–consumer, simultaneity, or task–subtask — justifying each verdict in a sentence; apply the subtraction test of Section 8.1 to the pair (t_2, t_3); and say where the task–subtask dependency lives, since it is not an edge between any two tickets. (b) Draw the coordination graph on the five tickets: how many of the \binom{5}{2} = 10 pairs interlock? (c) The orchestrator proposes scheduling the lint sweep in a slot of its own, after everything else has landed. Which edges does that one decision delete, and what fraction of the graph’s coordination does it design out? Then explain why the team’s token budget, which all five tickets draw on, is better governed by one global meter than by pairwise coordination — what would the coordination graph look like if that dependency were drawn in? (d) Price the proposal. With two coders and 2,000-token slots, compute three makespans: the whole job on one coder; the best schedule with the lint sweep run concurrently, shared-resource pairs kept out of each other’s slots by mutual exclusion, and every producer finishing before its consumer starts; and the best schedule under the solo-lint rule. Exhibit an optimal schedule for each of the two parallel regimes, and state the condition under which the solo-lint convention is the bargain — the trade of Section 8.3 in one number.

Exercise 2. Each of n agents performs one read-modify-write on the team’s shared board: agent i reads (R_i), works, then writes back its revision (W_i), and the 2n operations interleave in an order that preserves each agent’s R_i-before-W_i but is otherwise arbitrary. An interleaving is safe when every revision survives, which happens exactly when the n read-to-write intervals are pairwise disjoint — if two overlap, the later writer worked from a copy that never saw the earlier write, and destroys it. (a) For n = 2, list all the interleavings, mark the safe ones, and give the probability that a uniformly random interleaving is safe. (b) Show that the interleavings number (2n)!/2^n, that exactly n! of them are safe, and hence that \Pr(\mathrm{safe}) = 1/(2n-1)!!; evaluate this for the running team’s four agents. (c) Show that any two given agents’ intervals overlap with probability 2/3 whatever n is, compute the expected number of overlapping pairs at n = 4, and confirm (b) and (c) by enumerating all 2,520 interleavings. (d) Price the cure: untangling one overlapping pair costs r = 1{,}200 tokens; a lock serialises the four sessions, each 500 tokens long, with waiting priced at one token per unit of wall-clock. Compute the expected untangling bill without the lock and the total waiting with it, name the winner, and find the break-even r^* at which the lock stops paying. (e) A convention — each agent owns one region of the board and writes nowhere else — makes every interleaving safe at zero runtime cost. Say what it surrenders that the lock preserves, and why Section 8.3 still predicts the convention wins for a pattern repeated hundreds of times a run — provided one thing is added, and say which thing.

Exercise 3. A sprint’s traffic, reduced to ten events. The orchestrator o, in program order: o_1 fixes the sprint plan; o_2 sends the brief to the coder; o_3 receives the tester’s lint report; o_4 receives the coder’s “done”; o_5 marks the ticket complete. The coder c: c_1 receives the brief; c_2 commits the fix; c_3 sends “done”. The tester t: t_1 begins a lint pass; t_2 sends its report. The message pairs are o_2 \to c_1, c_3 \to o_4, and t_2 \to o_3. (a) Apply the chapter’s tick/recv rules (Section 8.2) with every counter starting at nought, and give all ten Lamport stamps. (b) For the pairs (o_2, c_1), (t_2, c_1), (o_3, c_2), and (c_1, o_3): which are ordered by happens-before and which concurrent? Use them to draw the boundary of the clock condition exactly — exhibit a pair with C(a) < C(b) yet a \parallel b, and a concurrent pair with equal stamps, and say why neither embarrasses the condition. (c) Prove that under these rules every event’s stamp equals the number of events on the longest happens-before chain ending at it, and verify the claim on o_4 by exhibiting its chain. (d) Break ties alphabetically by agent name to extend the stamps to a total order; list all ten events in that order; and make the chapter’s “manufactured rather than found” precise: of the \binom{10}{2} = 45 pairs of events, how many does causality order, and how many are settled only by the clocks’ accidents and the alphabet?

Exercise 4. The sprint has gone quiet. The coder holds the write-lock on export/writer.py and waits for the architect to approve an interface change; the architect holds ownership of schema.py and waits for the reviewer to sign off the migration; the reviewer holds the team’s single review slot and waits for the tester’s suite run; the tester needs the write-lock on export/writer.py to run the suite; and the docs agent waits for the architect’s approved interface before it writes a word. (a) Draw the wait-for graph and apply has_deadlock from the companion repository’s foundations/algorithms/lamport.py; then sort the five agents into three classes — on the cycle, blocked behind the cycle without being on it, and free — and say why the docs agent’s plight is not deadlock, to whom the distinction matters, and to whom it does not. (b) has_deadlock answers only yes or no, and a supervisor needs names: extend it to a find_cycle that returns the circular wait itself, and give its output on this graph. (c) Audit the scene against Coffman’s four conditions, pointing to where each holds — noting what stands in for a “resource” on the reviewer-to-tester edge, where nothing is locked at all — and for each condition give one concrete denial and the price the denial exacts; verify for the timeout (the tester abandons its wait) that the graph is cycle-free afterwards. (d) The team adopts a social law instead: resources are globally ranked — write-locks below schema ownership below the review slot below suite runs — and no agent may request a resource ranked at or below any it currently holds. Prove that under this law a circular wait can never form, whatever the agents do and in whatever order.

Exercise 5. Four tickets must be placed on two coders, and the choices interlock: any two tickets on the same coder queue behind each other, costing 2 per such pair; t_2 consumes t_1’s interface, so splitting that pair across coders costs a further 3 in handoff; and t_3 and t_4 edit the same file, so splitting that pair costs a further 6 in merge risk. (a) Write the placement as a distributed constraint optimisation problem in the notation of Section 8.5 — variables, domains, cost functions, constraint graph, and which edges carry which functions — then encode it for solve in the companion repository’s foundations/algorithms/dcop.py and give the minimum total cost and every optimal assignment. (b) Now give each ticket to an agent that controls only its own variable and sees only its own edges, all four starting on coder 1, and run sequential best response: in ticket order, each agent moves to the value minimising the cost of its own edges given the others’ current choices, sweeping until no one moves. Trace every move with the global cost after it. Where does the loop stop, and what did each agent never see? (c) Next, two ticket-agents joined by a single “match your sibling” edge (cost 1 if their values differ, 0 otherwise) revise simultaneously from mismatched values, each best-responding to the other’s current choice: trace four rounds, name the behaviour after its cousin in Section 8.2, and give the one-word change of update discipline that cures it. (d) Finally, two ticket-agents whose edge costs 0 if both choose b, 1 if both choose a, and 5 if they differ, starting from (a, a): show that sequential best response is already stuck, state what Lesser and Corkill’s functionally-accurate-cooperative principle does and does not promise about such loops, and name one mechanism that recovers the optimum.

Exercise 6. A week of the running team’s post-mortems, five exhibits. (i) The nightly changelog run: the journal shows coder 2’s entry written to the shared changelog, but the shipped file contains only the reviewer’s; a rerun, changing nothing, ships both. (ii) A run that hung: the journal’s last two entries are the orchestrator “awaiting the tester’s verdict before dispatching further work” and the tester “awaiting the orchestrator’s go-ahead to run the suite” — then forty minutes of nothing. (iii) The docs agent’s pull-request description walks through three functions by name; all three had been deleted from the repository two hours before it wrote, though its context still contained them. (iv) Coder 1 and coder 2, in the same afternoon, each implemented a flatten helper, in different files, both correct. (v) Two coders and one repository lock: the journal shows two hundred alternating acquire–fail–back-off entries from each, in near-perfect alternation, and no commit from either. (a) Diagnose each exhibit against Table 8.1, naming the hazard or declining to — exactly one exhibit is no concurrency hazard at all but a failure the chapter files elsewhere; say which, what it is instead, and which of this chapter’s mechanisms addresses it. For each diagnosis cite the discriminating evidence in the exhibit itself — in particular, what separates (v) from (ii) in a journal, and why (i)’s vanishing on rerun is not reassurance but the fingerprint. (b) For each of the four hazards, give the classical cure and a convention that would have prevented it for nothing at runtime. (c) The retrospective proposes a reorganisation: insert a sub-orchestrator between the orchestrator and the workers. For each exhibit, say whether any change of topology alone could even in principle remove it, and use the five verdicts to restate the chapter’s closing thesis about diagrams and mechanisms in one sentence.

Further exercises for this chapter continue in the web edition’s exercise bank.

“They’ve been giving way to each other since March.”