Distributed Problem Solving

"Each of us could see one corner of the room. It took eleven rounds of polite disagreement before we agreed there was an elephant."

A Sensor Node That Only Saw a Leg

Some problems are distributed before anyone decides to distribute them. A network of acoustic sensors monitoring a forest sees, at each node, only the sounds near that node; no single node hears the whole scene, yet the question (where is the moving vehicle, and on what heading?) is global. A team of warehouse robots each perceives a slice of the floor; the question (what is the safe, conflict-free set of routes right now?) spans the whole floor. In cases like these the input is already partitioned across machines by physics or geography, and gathering everything to one machine is either impossible, too slow, or too expensive. The discipline of solving such a problem in place, with cooperating solvers that pool partial conclusions rather than raw data, is distributed problem solving, and it is the oldest idea in distributed AI.

1. One Problem, Many Solvers, One Goal Beginner

It is worth fixing the boundary of the topic precisely, because the next chapters relax exactly the assumptions we make here. In distributed problem solving every solver is cooperative: the solvers are parts of one designed system, they share a single objective, and none of them gains by misleading the others. The classic illustration is a distributed sensor network for vehicle tracking. Each node has a directional microphone or a small radar and can estimate a vehicle's position only within its own coverage area, with its own noise and blind spots. No node can name the global track. Yet if the nodes share their local estimates with their neighbors, a node that sees a vehicle entering its area from the west can be cross-checked against the node to its west that just reported the vehicle leaving, and the fused interpretation is far better than any single node's guess.

This is genuinely different from the self-interested setting of Chapter 29, where agents may have private goals, negotiate, and strategize, and where the hard question is incentive design. Here the agents already agree on what a good global answer looks like; the only obstacle is that each one computed its piece without seeing the others' pieces, so the pieces have to be reconciled. The reconciliation is the work, and it is never free, because every piece of evidence one solver needs from another has to travel over a link.

2. The Two Hard Steps: Decomposition and Synthesis Beginner

Every distributed problem solving method is organized around two operations that bookend the local solving. The first is task decomposition: cutting the global problem into subproblems that can be assigned to solvers. A good decomposition produces subproblems that are roughly balanced in difficulty, that map naturally onto where the data already lives, and (the hard part) that interact as little as possible, because every interaction between two subproblems becomes communication between two solvers. The second is result synthesis: combining the local solutions into a global one. When the subproblems are truly independent this is a trivial concatenation, but when they share variables or constraints, synthesis must resolve the places where the local solutions disagree.

The trouble is that interesting problems do not decompose cleanly. Subproblems interact: a route chosen by one robot blocks a corridor another robot wanted, a color one map region picks forbids that color for its neighbors, a vehicle one sensor places at a coordinate must be the same vehicle the next sensor sees a moment later. Because of these interactions a solver cannot finish its subproblem in isolation; the locally optimal piece may be globally inconsistent. So the solvers must communicate intermediate, still-tentative results, discover the conflicts, and revise, possibly many times. This is why distributed problem solving is iterative rather than one-shot, and why its cost is dominated by rounds of communication rather than by local computation.

3. Functionally-Accurate, Cooperative Solving Intermediate

The foundational answer to "how should the solvers exchange?" is the functionally-accurate/cooperative (FA/C) approach, introduced by Lesser and Corkill for exactly the distributed-sensor setting above. Its insight is to abandon the idea that each solver must produce a complete, correct, final answer to its subproblem before sharing anything. Instead solvers exchange tentative, partial, possibly-inconsistent results as they go. Each solver treats incoming partials as additional, soft evidence, folds them into its own reasoning, and emits revised partials in turn. The system is "functionally accurate" because it reaches a correct global result even though no individual message is guaranteed correct, and "cooperative" because the solvers volunteer their best current guesses to help others converge rather than guarding them until certain.

Formally, picture the global problem as a set of variables with constraints, where variable $x_i$ is owned by solver $i$ and each constraint couples a few variables held by different solvers. A solution is a joint assignment that satisfies every constraint. Define the global cost as the number of violated constraints,

where $E$ is the set of interacting variable pairs. No solver can evaluate $C$ directly, because it spans the whole system. But solver $i$ can evaluate its local cost, the violations involving only its own variable and the neighbor values it has been told, and act to reduce that. The FA/C bet, which holds for a wide class of problems, is that if every solver keeps reducing its local cost while broadcasting its current value to the neighbors it interacts with, the global cost $C$ falls to zero. The exchange of tentative partial results is precisely the mechanism that keeps each solver's local view fresh enough for its local moves to be globally productive.

4. A Distributed Constraint Problem, Solved by Cooperation Intermediate

The cleanest runnable instance of all of this is distributed map coloring, a constraint problem small enough to read yet faithful to the structure of sensor fusion: each agent holds one piece (one region), the pieces interact through shared constraints (adjacent regions must differ), and no agent sees the whole map. The code below builds five region-agents. Each agent knows only its own neighbors, starts from a random tentative color, and in every round broadcasts its current color to its neighbors (the exchange of partial results), then, if it is in conflict, revises toward the locally best color with some probability. The probabilistic activation is the standard trick that stops neighboring agents from flipping in perfect lockstep forever; it is the distributed stochastic algorithm familiar from distributed constraint optimization, which Chapter 27 revisits in depth in its section on DCOP. We count the communication rounds and verify the synthesized global coloring.

import random

# The shared problem (no agent ever sees this whole structure).
# Adjacency of a small map: which regions touch which.
ADJ = {
    "A": ["B", "C"],
    "B": ["A", "C", "D"],
    "C": ["A", "B", "D", "E"],
    "D": ["B", "C", "E"],
    "E": ["C", "D"],
}
COLORS = ["R", "G", "B"]
random.seed(2)


class Agent:
    """Owns ONE region. Knows only its own neighbors, not the rest of the
    map. Holds a tentative color and the partial results it has received."""
    def __init__(self, region, neighbors):
        self.region = region
        self.neighbors = neighbors                 # local view only
        self.color = random.choice(COLORS)         # tentative guess
        self.inbox = {}                            # neighbor -> reported color

    def conflicts(self):
        """How many local constraints my current color violates."""
        return sum(1 for n in self.neighbors
                   if self.inbox.get(n) == self.color)

    def revise(self, activation):
        """If I violate a local constraint, with probability `activation`
        move to the local color that minimizes conflicts with what I have
        heard. Randomized activation breaks the symmetry that makes
        neighbors flip in lockstep. Returns True if I changed."""
        if self.conflicts() == 0:
            return False
        if random.random() > activation:
            return False                           # stay put this round
        taken = [self.inbox.get(n) for n in self.neighbors]
        best = min(COLORS, key=lambda c: taken.count(c))
        changed = best != self.color
        self.color = best
        return changed


# Build the solver society: one agent per region, each with a local view.
agents = {r: Agent(r, ADJ[r]) for r in ADJ}
print("Initial tentative colors :", {r: a.color for r, a in agents.items()})

total_msgs = 0
for rnd in range(1, 21):
    # Communication phase: every agent shares its tentative partial result.
    for r, a in agents.items():
        for n in a.neighbors:
            agents[n].inbox[r] = a.color           # send my color to neighbor
            total_msgs += 1
    # Conflicts visible AFTER exchange, BEFORE this round's revision.
    conflicts = sum(a.conflicts() for a in agents.values()) // 2
    # Local solve phase: conflicted agents revise against received partials.
    changed = sum(agents[r].revise(activation=0.7) for r in agents)
    print(f"round {rnd:2d}: {dict((r, a.color) for r, a in agents.items())} "
          f"| edge-conflicts={conflicts} | revised={changed}")
    if conflicts == 0 and changed == 0:
        print(f"\nConverged after {rnd} rounds, "
              f"{total_msgs} partial-result messages exchanged.")
        break

# Synthesis: collect local colors into the global solution and verify it.
solution = {r: a.color for r, a in agents.items()}
ok = all(solution[u] != solution[v] for u in ADJ for v in ADJ[u])
print("Synthesized global coloring :", solution)
print("Globally consistent          :", ok)

Initial tentative colors : {'A': 'R', 'B': 'R', 'C': 'R', 'D': 'G', 'E': 'R'}
round  1: {'A': 'R', 'B': 'B', 'C': 'B', 'D': 'G', 'E': 'B'} | edge-conflicts=4 | revised=3
round  2: {'A': 'R', 'B': 'R', 'C': 'R', 'D': 'G', 'E': 'R'} | edge-conflicts=2 | revised=3
round  3: {'A': 'G', 'B': 'B', 'C': 'R', 'D': 'G', 'E': 'R'} | edge-conflicts=4 | revised=2
round  4: {'A': 'G', 'B': 'B', 'C': 'R', 'D': 'G', 'E': 'B'} | edge-conflicts=1 | revised=1
round  5: {'A': 'G', 'B': 'B', 'C': 'R', 'D': 'G', 'E': 'B'} | edge-conflicts=0 | revised=0

Converged after 5 rounds, 70 partial-result messages exchanged.
Synthesized global coloring : {'A': 'G', 'B': 'B', 'C': 'R', 'D': 'G', 'E': 'B'}
Globally consistent          : True

Two features of Output 27.2.1 are the whole lesson in miniature. First, convergence is not monotone: the conflict count climbs before it falls, because each agent acts on a snapshot of its neighbors that is already one round out of date, so well-meant local fixes can briefly create new global clashes. This is the price of having no agent that sees everything. Second, the work is counted in rounds and messages, not in arithmetic: five rounds and seventy messages settled a problem whose local computation was trivial. Scale the map to thousands of regions on thousands of machines and the message count, not the coloring logic, is what determines whether the system is practical, which is exactly why Chapter 4 treats the cost of communication as a first-class quantity.

# pip install pydcop ; then:  dcop.py solve --algo dsa map_coloring.yaml
# map_coloring.yaml declares one variable per region over domain [R, G, B]
# and an "all_diff"-style constraint on each adjacent pair. pydcop builds the
# agents, runs the chosen distributed algorithm, and reports the assignment.
from pydcop.dcop.dcop import DCOP
from pydcop.dcop.objects import Variable, AgentDef
from pydcop.dcop.relations import constraint_from_str
# ... define variables/constraints, pick algo="dsa", and call the solver:
#     pydcop solve --algo dsa --timeout 5 map_coloring.yaml

5. The MapReduce Parallel and the Modern Agent Parallel Intermediate

The decompose-solve-synthesize shape should feel familiar, because it is the shape of MapReduce. The map phase decomposes the input and applies a local function to each shard; the reduce phase synthesizes the per-shard results into a global one. The difference is exactly the interaction question of Section 2. MapReduce is built for problems whose subproblems do not interact within a phase: every mapper is independent, every reducer is independent, and the only communication is the single shuffle between the two phases. Distributed problem solving is what you need when that assumption fails, when the "mappers" must talk to each other repeatedly because their pieces are coupled. Seen this way, MapReduce is the degenerate, one-round case of distributed problem solving, the case where the synthesis is a single reduce because the partial results never conflict.

The pattern has returned, scaled out and modernized, in multi-agent LLM workflows. A complex task (write a researched report, fix a bug across a large codebase, plan a multi-step trip) is decomposed across role-specialized agents: a planner, several workers each owning a sub-task, a critic, an integrator. The workers solve their sub-tasks with their own local context, exchange intermediate results (a draft section, a candidate patch, a partial itinerary), and an integrator synthesizes the global deliverable, often looping when the pieces do not cohere. This is FA/C with language models in the solver role: tentative partial results flow between agents, each agent refines on what it receives, and the system is functionally accurate even though no single agent produced a complete correct answer alone. The orchestration machinery that makes this reliable at scale is the subject of Chapter 32.

6. When It Helps, and When It Is Just Overhead Advanced

Distributed problem solving earns its complexity in a specific regime, and it is worth naming the boundary so it is not reached for reflexively. It helps when the data or sensing is genuinely distributed and cannot be centralized cheaply (sensor networks, robot teams, federated sites under privacy constraints), when the problem is large enough that local solving across many machines is faster than one machine grinding through the whole thing, and when the interactions between subproblems are sparse, so that a few rounds of partial-result exchange resolve most conflicts. In that regime the communication is modest and the parallelism pays.

It is pure overhead in the opposite regime. If all the data could be gathered to one machine quickly and that machine could solve the problem outright, a centralized solver is simpler, exact, and usually faster, because it pays no communication tax and never revises on stale views. If the subproblems interact densely, every solver ends up talking to nearly every other solver every round, the message count explodes, and the system spends more time exchanging tentative results than it would have spent solving the problem centrally. The honest design question, echoing the one this book asks of every distribution decision, is whether the coupling is sparse enough that cooperation converges in few rounds; when it is not, the right move is to centralize, and the trade-off between centralized, decentralized, and hybrid designs is exactly what Section 27.3 takes up next.

We now have the founding pattern of distributed AI: cut one problem into coupled subproblems, hand them to cooperative solvers, exchange tentative partial results until the local solutions stop contradicting each other, and synthesize the global answer. The pattern's cost is rounds of communication, its benefit is solving problems whose data is already spread out, and its boundary is the density of the interactions. The natural next question is architectural: should the coordination that makes this work live in one place, in no place, or somewhere in between? That is the centralized-versus-decentralized-versus-hybrid question, and it is the subject of Section 27.3.