Coordination is the allocation layer, not the conversation
Fix vocabulary first. A multi-agent system stacks several concerns: agents communicate (exchange messages in some protocol), sometimes negotiate or debate to resolve conflicting views, and must coordinate — agree on a division of labor and an execution order so the collective finishes the job. This article is about the third only.
Concretely, coordination answers scheduling and assignment questions — what are the sub-tasks, which agent takes each, what must finish first, who assembles the parts — none of which require an agent to hold an opinion or persuade anyone, the same questions a project manager or an OS scheduler faces. Treating it as its own layer lets you reason about speedup and overhead cleanly, without tangling it up in the harder problem of how agents agree on contested facts.
Decomposition: from one goal to a task graph
Coordination begins with decomposition: splitting a goal into sub-tasks small enough to hand out. The natural representation is a directed acyclic graph (DAG). Each node is a task; an edge A → B means B consumes A’s output, so B waits for A. Tasks with no path between them are independent and may run in parallel.
For example, ‘write a market report’ might decompose into gather_sources, three independent analyze_segment_i tasks, a synthesize depending on all three, and a proofread. The analyses form a parallel band; everything else is serial. The shape of this graph, not the number of agents, sets the parallelism ceiling: one long dependency chain has none to exploit however many agents you own. Decomposition quality — how well you expose genuinely independent work — is the single biggest lever on whether a multi-agent setup pays off.
The allocation problem, stated precisely
Given a set of tasks and a set of agents, allocation (or assignment) is choosing a mapping from tasks to agents. If every agent is identical, allocation is pure load-balancing; more realistically agents differ — a ‘researcher’ has web tools, a ‘coder’ a sandbox, a small local model is cheap but weak — so each task t has a cost c(t, a) depending on which agent a runs it. The clean formulation minimizes total cost (or makespan — the finish time of the last task) subject to the DAG’s ordering constraints. With independent tasks and one per agent this is the classic assignment problem, solved exactly by the Hungarian algorithm in O(n^3). Add precedence constraints and shared agents and it becomes DAG scheduling, NP-hard in general — exactly why real systems reach for heuristics and market mechanisms rather than optimal solvers.
Orchestrator/worker versus decentralized
The most common pattern in LLM agent systems is orchestrator/worker (manager/worker, supervisor). One privileged agent holds the task graph, decides the decomposition, hands sub-tasks to workers, collects outputs, and synthesizes the answer; workers are typically stateless toward each other. The appeal is control: allocation lives in one place, giving a single coherent view of progress, and assembly is easy because the orchestrator holds every piece. The cost is that it is a bottleneck and single point of failure whose context window must summarize a growing pile of worker output — the constraint on how many workers it can manage.
The alternative is decentralized coordination, where no agent owns the plan. A shared blackboard — a common workspace of tasks and partial results — is the classic realization: any idle agent claims a suitable task and posts its output for others to build on. This removes the bottleneck, survives an agent dying, and scales because no central context holds everything. The price is harder guarantees: two agents can claim the same task, a dropped task can go unnoticed, and detecting that the job is done becomes a distributed-termination problem. Centralization trades scalability for coherence; decentralization makes the opposite bet.
Role assignment and specialization
A middle layer between structure and allocation is role assignment: giving agents durable identities — planner, researcher, coder, critic — rather than treating them as interchangeable. Roles pre-constrain allocation: a task tagged ‘needs code execution’ routes to the coder without any per-task bidding, collapsing the assignment search space. Specialization also lifts quality, since a prompt, tool set, and context tuned for one role beats a generalist and keeps each agent’s context focused rather than bloated. The risk is rigidity and imbalance — if roles are too fine-grained, some specialists sit idle while others form a queue, and a task spanning two roles has no clean owner. Good role design mirrors the actual distribution of work: enough to route cheaply, not so much that specialists starve.
Contract-net and auction-based assignment
When agents are heterogeneous and you do not want a central planner computing an optimal assignment, let the agents bid. The Contract Net Protocol is canonical: a manager announces a task, capable agents respond with bids estimating their cost or suitability, and the manager awards the contract to the best bid — a market mechanism that distributes the assignment decision without giving up a final award step.
Auctions generalize this. In the simplest, each agent submits a private cost and the lowest bidder wins — a reverse auction that approximates the optimal assignment when agents bid true costs. Auctioning tasks one at a time gives a greedy allocation that is fast and often within a constant factor of optimal, avoiding the NP-hard global solve, and each agent needs only local knowledge of its own cost, so the mechanism scales and adapts as agents join or leave. The catch: greedy one-at-a-time awards can look good locally yet box in later assignments.