Distributed Knowledge and Belief

"I know the plan. I think you know the plan. I am almost sure you think I know the plan. After that the tower of 'I think you think' got too tall, so I just attacked and hoped."

A Consensus Round That Refuses to Commit

Earlier sections of this chapter gave agents protocols to coordinate: the blackboard of Section 27.4, the contract net of Section 27.5, and the coordination mechanisms of Section 27.7. Every one of those protocols rests on an unstated assumption that we now make explicit and then interrogate: that the agents share enough of a common picture to act together. A bidder and an auctioneer must agree on which task was awarded; two robots clearing a corridor must agree on who yields. Agreement is an epistemic state, a fact about who knows what, and distributing it across unreliable machines turns out to be one of the subtlest problems in the whole field. This section is about why.

The trouble is that knowledge in a distributed system has structure. It is not a single bit that is either shared or not. There is what one agent knows on its own, what the group could know if it pooled its views, and what the group has genuinely made common. These are different things with different costs, and confusing them is the source of a great many coordination bugs. We climb that hierarchy first, then show what breaks at the top.

1. Three Kinds of Knowing Beginner

Fix a group of agents and a fact $p$ about the world, say "the warehouse aisle is blocked." We can ask, with increasing strength, what the group knows about $p$. The weakest level is individual knowledge: some particular agent $i$ knows $p$, written $K_i\,p$. The robot at the end of the aisle sees the blockage; no other robot does. Individual knowledge is cheap and local, and it is all an agent has by default, because in a distributed system each agent perceives only its own slice of the world.

The next level is distributed knowledge, written $D\,p$. The group has distributed knowledge of $p$ if $p$ follows from the union of what its members individually know, even though no single member knows $p$ alone. One robot knows the aisle is blocked; another knows the only detour was closed for cleaning; neither alone can conclude that the shipment will be late, but together their facts imply it. Distributed knowledge is the knowledge that would exist if the agents pooled everything, a latent group asset that is real only after communication realizes it. It is the epistemic mirror of the distributed-data view: the full picture exists, but it is shattered across machines and must be gathered to be used.

The strongest level is common knowledge, written $C\,p$. A fact is common knowledge when everyone knows it, and everyone knows that everyone knows it, and everyone knows that, without end. Formally, writing $E\,p = \bigwedge_i K_i\,p$ for "everyone knows $p$," common knowledge is the infinite conjunction

Common knowledge is what coordinated action needs. To attack together, each general must not merely know the plan; each must know the other knows it, and know that the other knows that they know it, because otherwise some agent hesitates, fearing the other will hesitate, fearing the first will hesitate, and the whole plan unravels from the top of the tower down. Figure 27.8.1, left, stacks these three levels. The jump from distributed to common knowledge is the expensive one, and the rest of this section is about how expensive it really is.

2. The Coordinated Attack and Why Common Knowledge Is Unattainable Intermediate

The classical illustration is the two-generals problem, also called coordinated attack. Two generals on opposite hills must attack a city in the valley at the same time; if only one attacks, that army is destroyed. They can communicate only by sending a messenger through the valley, where the messenger may be captured, meaning any message may be lost. The question is whether any protocol, however clever, lets both generals reach a state where attacking together is guaranteed.

The answer is no, and the proof is a short argument by contradiction that every distributed-systems engineer should carry around. Suppose some protocol guarantees coordinated attack and uses the fewest possible messages. Consider its last message. Because the channel is lossy, that message might be lost, and the sender cannot tell whether it arrived. If the protocol is correct whether or not the last message arrives, then the last message was not needed, contradicting minimality. If the protocol is correct only when the last message arrives, then it is not guaranteed, because that message can always be lost. Either way the assumption fails. No finite protocol attains common knowledge of the attack time over a lossy channel; the generals can climb the tower of mutual knowledge one rung per round but never reach the top.

This is not an engineering limitation that a better network erases. It is an impossibility of the same family as the agreement and consensus limits you met in Section 2.6, where unreliable processes and channels make certain guarantees unachievable, and it has the same flavor as the consistency limits of Section 2.5, where keeping replicas in perfect agreement collides with the realities of partitions and delay. Knowledge, agreement, and consistency are three views of the same coordination problem, and all three meet the same wall.

3. Settling for Probabilistic Agreement Intermediate

Since guaranteed common knowledge is off the table, working systems aim lower and quantify the residual risk. The agents exchange many rounds of plan-and-acknowledgement, and each extra round that survives the lossy channel raises confidence that the plan is shared, shrinking the chance that one agent acts alone while the other holds back. The chance never reaches exactly zero, but it can be driven below any operational threshold the application can tolerate. The code below simulates this directly: two generals run a repeated send-and-ack handshake over a channel that drops each message independently, and we measure how often they attack together, how often one attacks alone (the catastrophe), and how often neither moves.

import random

# Two generals must attack at the SAME time. They agree only by exchanging
# acknowledgements over a lossy channel. A commits to attack only once it has
# received an ack (it knows B has the plan); B commits once it has the plan.

def run_protocol(loss_prob, max_rounds, rng):
    a_heard_ack = False    # A received an ack: A knows B got the plan
    b_heard_plan = False   # B received the plan at least once
    for _ in range(max_rounds):
        if rng.random() >= loss_prob:        # A -> B: plan delivered
            b_heard_plan = True
            if rng.random() >= loss_prob:    # B -> A: ack delivered
                a_heard_ack = True
    # Residual disaster: B has the plan but every ack to A was lost, so B
    # attacks while A holds back. No finite round count removes this case.
    return a_heard_ack, b_heard_plan         # (attack_A, attack_B)

def simulate(loss_prob, max_rounds, trials, seed=0):
    rng = random.Random(seed)
    both = lone = neither = 0
    for _ in range(trials):
        a, b = run_protocol(loss_prob, max_rounds, rng)
        if a and b:      both += 1
        elif a or b:     lone += 1            # one attacks alone: catastrophic
        else:            neither += 1
    return both, lone, neither

TRIALS = 20000
print(f"{'loss':>6} {'rounds':>7} {'both attack':>12} {'lone (loss)':>12} {'neither':>9}")
for loss in (0.0, 0.1, 0.3, 0.5):
    for rounds in (3, 10):
        both, lone, neither = simulate(loss, rounds, TRIALS)
        print(f"{loss:>6.1f} {rounds:>7d} {both/TRIALS:>12.4f} "
              f"{lone/TRIALS:>12.4f} {neither/TRIALS:>9.4f}")

  loss  rounds  both attack  lone (loss)   neither
   0.0       3       1.0000       0.0000    0.0000
   0.0      10       1.0000       0.0000    0.0000
   0.1       3       0.9932       0.0060    0.0008
   0.1      10       1.0000       0.0000    0.0000
   0.3       3       0.8667       0.1054    0.0279
   0.3      10       0.9986       0.0014    0.0000
   0.5       3       0.5752       0.3010    0.1238
   0.5      10       0.9426       0.0566    0.0008

Read the table as the impossibility result made quantitative. The top two rows, with a lossless channel, reach perfect coordination because common knowledge is buildable when nothing is ever dropped. Every other row has a nonzero lone-attack column that more rounds shrink but cannot erase, exactly as Section 2 proved. A practical multi-agent system picks a round budget that pushes the catastrophe probability under its tolerance and accepts the rest as risk, the same bargain a distributed database strikes when it chooses an eventual-consistency level instead of demanding the impossible.

4. Modeling and Revising the Beliefs of Others Advanced

Knowing what the group knows is only half the problem. To coordinate well, an agent must maintain an explicit model of what each other agent believes, because it must predict their actions and choose its own to mesh with them. This is the engineering form of what cognitive science calls a theory of mind: agent $i$ carries a representation of agent $j$'s beliefs, possibly including $j$'s model of $i$, nested as deeply as the task rewards. A negotiating agent that models its counterpart's reservation price bids differently from one that does not; a robot that models a human's belief about its intentions can move so as to be legible rather than alarming.

Because the world and the messages keep changing, these models cannot be static. Belief revision is the discipline of updating an agent's beliefs as new information arrives, ideally minimally, so that incorporating a new fact disturbs as little of the existing belief set as possible while restoring consistency. When a robot that believed the aisle was clear receives a report that it is blocked, it must retract the clear-aisle belief and everything that depended on it, then absorb the new fact, without throwing away unrelated knowledge. Done probabilistically this is Bayesian updating over hypotheses; done symbolically it follows the rationality postulates of belief-revision theory. Either way, the agent's beliefs about the world and about other agents form a structure that communication continuously rewrites, and keeping that structure coherent under a stream of partial, sometimes contradictory updates is the core difficulty of distributed belief.

The reason this is hard is the reason the whole section is hard: there is no global oracle. Each agent revises from its own vantage, so two agents that receive different messages in different orders can end up with genuinely inconsistent beliefs about the same world and about each other, and nothing inside the system flags the divergence. Reconciling those views costs synchronization, and synchronization is exactly the tax the coordinated-attack result says we cannot fully escape. The agents face a CAP-like choice in epistemic clothing: stay responsive on local beliefs and risk inconsistency, or block until views agree and pay in latency, the same tension formalized for replicated data in Section 2.5.

5. The Modern Echo: Shared Context Across LLM Agents Intermediate

This decades-old theory describes, with uncomfortable precision, a problem at the frontier of today's systems. A team of large language model agents collaborating on a task each carries a context window and often a slice of a shared memory or scratchpad. That shared memory is exactly distributed knowledge: the union of what the agents have written down would solve the task, but no single agent holds it, and realizing it requires reading and reconciling the others' notes. When two agents update the shared memory concurrently, or when one agent's summary of a sub-result never reaches another, their working beliefs about the task state diverge, and they begin to act on inconsistent context, the lone-attack failure wearing a new costume.

The fixes echo the classical ones. Systems append to a shared log rather than overwriting, so updates are ordered; they have agents acknowledge and re-summarize what they received, building mutual knowledge rung by rung; and they accept that perfect consistency of context across a fleet is unattainable, designing instead for graceful behavior under stale or conflicting memory. The orchestration machinery that makes a shared agent memory consistent enough to be useful is the subject of Section 32.7; the point here is that it is solving the distributed-knowledge problem of this section, now with natural-language beliefs instead of formal propositions.

# Conceptual sketch with a shared, ordered memory (e.g. a LangGraph-style store).
from agent_runtime import SharedMemory, Agent          # illustrative API

memory = SharedMemory(ordered=True, versioned=True)    # append-only, timestamped

def step(agent: Agent):
    snapshot = memory.read(at=memory.latest_version())  # consistent view to revise from
    belief = agent.update_beliefs(snapshot)             # local belief revision
    memory.append(agent.id, belief.summary)             # ordered write; others will see it
    return belief

We have climbed from individual to distributed to common knowledge, seen why the top rung is unreachable over a lossy channel, watched practical systems buy probability in place of certainty, and traced the same structure into belief revision and modern shared-context agents. The next section steps back to survey where distributed AI lives in modern AI systems as a whole, carrying these epistemic limits forward as a constraint every multi-agent design must respect. That survey begins in Section 27.9.