The Contract-Net Protocol

"I announced one small task to the whole cluster. Four agents bid, one undercut the rest, and somehow nobody had to ask me who was free."

A Manager Agent That Stopped Keeping a Schedule

The previous sections of this chapter built up the picture of distributed artificial intelligence as many semi-autonomous agents that must coordinate without a single mind directing them. The natural next question is mechanical: given a set of tasks and a set of agents, who does what? One answer is to elect a coordinator that knows every agent's capabilities and current load, then have it compute an assignment and hand out orders. That is a central scheduler, and it is exactly what a cluster manager or a load balancer does. It works, but it concentrates knowledge and decision-making in one place, which is the opposite of what a distributed system is for. The Contract-Net Protocol, introduced by Reid Smith in 1980, takes the other path. It treats task allocation as a negotiation in which agents advertise work and bid for it, and it remains, more than four decades later, the cleanest illustration of decentralized coordination through a market.

1. Announce, Bid, Award Beginner

The protocol has three message types and a strict order. A manager with a task to delegate broadcasts a task announcement that describes the work and, usually, an eligibility specification that lets uninterested agents stay silent. Every agent that hears the announcement and could plausibly do the work evaluates it against its own local state, its capabilities, its current load, the cost it would incur, and replies with a bid that summarizes its fitness as one or a few numbers. The manager waits for bids to arrive (or for a deadline), ranks them, and sends an award message to the single best bidder, which now holds the contract and executes it. Nothing in this exchange requires the manager to know who the contractors are in advance, how many there are, or what they are currently doing. The manager learns exactly what it needs, the bids, and nothing more.

This inversion of control is the heart of the idea. In a central scheduler, the scheduler pulls information toward itself: it must maintain a model of every worker's capability and availability, and that model goes stale the instant a worker's situation changes. In Contract-Net, the information stays where it is generated. Each agent assesses itself at bidding time, so the bid reflects the agent's true current state rather than a possibly outdated central record. The manager never builds a global picture; it makes one local decision from the bids in hand. That is why the protocol handles heterogeneous agents and changing availability so gracefully: an agent that is overloaded simply bids high or stays silent, and an agent that just acquired a new capability simply starts bidding on tasks it could not do before, with no central registry to update.

2. The Bid and the Award, Made Precise Intermediate

To turn the protocol into something runnable we need to say what a bid is and how the award is chosen. Let the agents be $\mathcal{A} = \{a_1, \dots, a_n\}$ and consider a single announced task $t$. Each agent $a$ computes a private cost $c_a(t) \in [0, \infty]$ of performing $t$, where $c_a(t) = \infty$ encodes that $a$ cannot do $t$ at all. A useful and realistic refinement makes the bid depend on the agent's current load $\ell_a$, so that a busy agent bids higher even when its raw cost is low,

where $\lambda$ tunes how strongly congestion is penalized. The manager collects the bids and awards the contract to the agent with the smallest finite bid,

Run this announce-bid-award cycle once per task, updating each winner's load $\ell_a$ as contracts are awarded, and a complete allocation falls out. Notice what is absent: there is no joint optimization over all tasks and all agents at once. Each task is awarded greedily to whoever bids best for it given the awards made so far. That greedy, myopic structure is both the protocol's great virtue, it is simple, local, and fast, and its main limitation, which we examine in Section 4.

The code below implements exactly this cycle. Four agents have different per-capability costs (some capabilities are impossible for some agents), six tasks arrive one at a time, and the manager runs an announce-bid-award round for each. We compare the resulting total cost against a baseline that assigns each task to a uniformly random capable agent, the kind of allocation you get with no negotiation at all.

import random

random.seed(7)
INF = float("inf")

# Each agent has a per-capability unit cost. "inf" means it cannot do that work.
agents = {
    "A1": {"vision": 2.0, "nlp": 9.0, "planning": 5.0, "control": 3.0},
    "A2": {"vision": 8.0, "nlp": 1.5, "planning": 4.0, "control": INF},
    "A3": {"vision": 4.0, "nlp": 3.0, "planning": 1.0, "control": 6.0},
    "A4": {"vision": INF, "nlp": 7.0, "planning": 6.0, "control": 1.5},
}
tasks = [("scan_perimeter", "vision", 3), ("summarize_logs", "nlp", 2),
         ("route_mission", "planning", 4), ("steady_gimbal", "control", 2),
         ("read_signage", "vision", 1), ("draft_report", "nlp", 3)]

def bid(costs, cap, work):                      # a contractor's private cost
    return costs.get(cap, INF) * work

def contract_net(agents, tasks):
    alloc, total, load = {}, 0.0, {a: 0 for a in agents}
    for name, cap, work in tasks:
        # ANNOUNCE the task; collect a BID from every contractor (load adds congestion).
        bids = {a: bid(c, cap, work) + 0.5 * load[a] for a, c in agents.items()}
        winner = min(bids, key=bids.get)        # AWARD to the lowest finite bid
        alloc[name] = None if bids[winner] == INF else winner
        if alloc[name]:
            total += bids[winner]; load[winner] += work
    return alloc, total

def random_assign(agents, tasks):               # baseline: no negotiation
    alloc, total = {}, 0.0
    for name, cap, work in tasks:
        capable = [a for a in agents if agents[a].get(cap, INF) < INF]
        w = random.choice(capable); alloc[name] = w
        total += agents[w][cap] * work
    return alloc, total

cnp_alloc, cnp_cost = contract_net(agents, tasks)
rnd_alloc, rnd_cost = random_assign(agents, tasks)
print("Contract-Net allocation (task -> awarded agent):")
for name, _, _ in tasks: print(f"  {name:<16} -> {cnp_alloc[name]}")
print(f"Contract-Net total cost : {cnp_cost:.1f}\n")
print("Random capable allocation:")
for name, _, _ in tasks: print(f"  {name:<16} -> {rnd_alloc[name]}")
print(f"Random total cost       : {rnd_cost:.1f}\n")
print(f"Cost reduction          : {100 * (rnd_cost - cnp_cost) / rnd_cost:.0f}%")

Contract-Net allocation (task -> awarded agent):
  scan_perimeter   -> A1
  summarize_logs   -> A2
  route_mission    -> A3
  steady_gimbal    -> A4
  read_signage     -> A1
  draft_report     -> A2
Contract-Net total cost : 25.0

Random capable allocation:
  scan_perimeter   -> A2
  summarize_logs   -> A2
  route_mission    -> A4
  steady_gimbal    -> A4
  read_signage     -> A1
  draft_report     -> A1
Random total cost       : 83.0

Cost reduction          : 70%

The numbers tell the story the protocol promises. The bid-driven allocation routes each capability to an agent that is genuinely good at it, because that agent bids low for it, while the random assignment repeatedly sends work to agents that merely can do it. The 70% cost reduction was bought with three message types and a per-task minimum, no global optimizer in sight. That said, "lowest bid per task, in arrival order" is greedy, and Section 4 shows where greediness leaves cost on the table.

3. A Market in Place of a Load Balancer Intermediate

It is worth seeing Contract-Net as the same problem you met earlier in the book, wearing different clothes. A load balancer in a serving fleet decides which replica handles an incoming request, and a cluster scheduler decides which node runs a job; both are central deciders that pull worker state toward themselves and push out assignments. The distributed-inference systems of Section 23.2 lean on exactly this central-router design, and it is the right design when one router can see the whole fleet cheaply. Contract-Net is the decentralized alternative to that router. Instead of a dispatcher choosing a worker, the workers bid and the cheapest one self-selects. The two designs trade the same currency: the central router pays the cost of maintaining a global view, while the market pays the cost of broadcasting announcements and collecting bids.

This is the decentralized-coordination thread that Section 1.4 opened, now made concrete as a negotiation protocol. A central scheduler is a single point of knowledge and a single point of failure; a contract net has neither, because any agent can announce and any agent can bid. The parameter-server-versus-all-reduce contrast of Chapter 11 is the same tension in the training world: a central server that coordinates, against a peer protocol where every node participates symmetrically. Contract-Net sits firmly on the peer side, which is why it scales naturally as agents come and go and degrades gracefully when some of them fall silent.

4. What the Market Costs and What It Misses Advanced

Two limits keep Contract-Net honest. The first is communication. A single allocation costs one broadcast announcement plus one bid from every interested agent plus one award, so for $n$ contractors and $m$ tasks the message count grows like $O(nm)$ in the simplest scheme, and the manager must wait for the slowest relevant bid or impose a deadline that risks excluding a good but slow bidder. In a small team this is nothing; across thousands of agents, or for tasks announced at high frequency, the announce-bid-award chatter becomes the dominant cost, exactly the communication tax that the rest of this book spends so much effort minimizing. Real deployments prune it with eligibility specifications (so only plausible agents bid), focused announcements to a candidate subset, and bid deadlines.

The second limit is that the allocation is greedy and myopic. Each task is awarded to the locally best bidder without considering how that award constrains the tasks still to come. The protocol never reconsiders a contract in light of later announcements, so it can settle into an allocation that is good task-by-task yet globally suboptimal: an agent that wins an early, cheap task may have been the only good fit for a later, expensive one, and by then it is loaded. Extensions soften this, contractors can decommit (break a contract, possibly for a penalty) when a better opportunity appears, and managers can run iterative or combinatorial auctions that let agents bid on bundles of tasks, recovering some of the joint optimization that the basic protocol forgoes. We treat those richer auction mechanisms and their equilibrium properties when we reach game-theoretic task allocation later in this part.