Mutual Belief

The doxastic counterpart of common knowledge: A believes p, A believes B believes p, A believes B believes A believes p, … — without requiring that p be true. The operative epistemic condition in SharedPlans (Grosz & Kraus 1996), Cohen & Levesque’s joint-intention models, and most BDI-style multi-agent reasoning. Easier to attain in distributed asynchronous systems than common knowledge (Halpern & Moses 1990 — common knowledge is often unattainable; mutual belief is a practical relaxation).

In this vault

Backlinks

Linked Pages

BDI

Belief-Desire-Intention

Dominant agent-architecture paradigm: agents maintain beliefs, desires, and intentions and deliberate over them.

In this vault

Belief

In agent theory, the propositional content an agent treats as (probably) true. The B in BDI / Belief-Desire-Intention; the operand of the modal operator believes in BAN Logic and the BDI-logic family (Cohen & Levesque, Rao & Georgeff). Distinguished from knowledge (which classically requires truth) and from desire / goal. The unit of Belief Revision under the AGM postulates. In Mentalistic Semantics the meaning of an ACL message is given in terms of the belief updates it induces in sender and receiver — the locus of Singh’s critique that beliefs are unverifiable from message traces.

In this vault

Common Knowledge (Convention)

The infinite hierarchy of mutual expectation introduced by Lewis (1969) and rediscovered by Aumann (1976) in game theory and Halpern–Moses (1990) in distributed systems: A knows p, A knows that B knows p, A knows that B knows that A knows p, … all the way up. A convention is sustained by common knowledge of the regularity. The construction has the same mathematical content in three independent fields — Lewis-style social philosophy, game theory, and distributed-systems epistemology — and is unattainable in fully asynchronous distributed systems (Halpern & Moses), with deep consequences for what coordination protocols can achieve.

In this vault

Knowledge and Common Knowledge in a Distributed Environment

Reference

Halpern, J. Y., & Moses, Y. (1990). “Knowledge and Common Knowledge in a Distributed Environment.” Journal of the ACM, 37(3), 549-587. URL

Summary

Halpern and Moses recast distributed protocol design as knowledge transformation: sending a message changes the knowledge state of the system, and correctness specifications can be stated in terms of what individual processes, groups, or “the system” know at various points. The paper develops a formal epistemic logic for distributed systems with operators K_i (agent i knows), E (everyone knows), and C (common knowledge — everyone knows that everyone knows, to infinite depth).

The central technical result is striking: in a truly asynchronous distributed system, common knowledge is unattainable. The classical “coordinated attack” problem (two generals must attack simultaneously but communicate only via lossy messengers) is unsolvable because simultaneous action requires common knowledge of the time to attack, and no finite message chain ever reaches the fixpoint. The muddy children puzzle — a beloved epistemic set piece walked through in the opening — shows how a public announcement can create common knowledge that sequential private reasoning cannot, illuminating why synchronous broadcast matters.

Because strict common knowledge is unattainable, the paper introduces and characterises weaker variants: eventual common knowledge, ε-common knowledge (bounded delay), timestamped common knowledge, and concurrent common knowledge. Each corresponds to a different system model (synchronous, partially synchronous, etc.) and a different class of solvable coordination tasks. This framework turned “what does a protocol achieve?” into a precise epistemic question and seeded the entire field of Theoretical Aspects of Reasoning about Knowledge (TARK).

Key Ideas

Epistemic hierarchy: distributed knowledge ⊑ someone knows ⊑ everyone knows (E) ⊑ common knowledge (C).
Common knowledge (C): fixpoint E^ω — needed for any simultaneous coordinated action.
Coordinated attack / muddy children: canonical illustrations of how public announcements create C.
Impossibility: in async or even synchronous-with-uncertain-delivery systems, C cannot be attained by message exchange.
Weakenings: ε-C (bounded-time C), eventual C, timestamped C, concurrent C — each aligned with a synchrony assumption.
Protocols as knowledge transformers: specifications are claims about K_i, E, C; message sends are knowledge updates.
Runs-and-systems semantics: each global history is a “run”; agent’s knowledge is the set of runs it cannot distinguish from the actual one.

Connections

Epistemic Logic
Epistemic S5
Knowing What vs Knowing That
The Synthesis of Digital Machines with Provable Epistemic Properties — Rosenschein-Kaelbling operationalise this framework.
Time Clocks and the Ordering of Events in a Distributed System — the “local history” underpinning indistinguishable runs is Lamport’s past-cone.
Impossibility of Distributed Consensus with One Faulty Process — consensus impossibility has an epistemic reading: common knowledge of a decision cannot be attained.
CAP Theorem

Conceptual Contribution

Joint Intentions

Cohen & Levesque’s theory of teamwork: joint persistent goals with mutual belief commitments.

In this vault

SharedPlans

Grosz & Kraus’s (1996) computational framework for collaborative joint action: a SharedPlan is a group-level structure carrying mutual beliefs about who is doing what, why, and how, with two intention modalities (Int.To for own actions, Int.Th for actions of others or the group). Most real collaboration involves partial SharedPlans, refined incrementally through meta-intentions to complete the plan, help others, and communicate. The canonical computational realisation of Bratman’s Shared Cooperative Activity.