Reasoning About Knowledge

Reference: Fagin, Ronald; Halpern, Joseph Y.; Moses, Yoram; & Vardi, Moshe Y. (1995). Reasoning About Knowledge. MIT Press, Cambridge, MA. 477 pp. ISBN 0-262-06162-7 (cloth, 978-0-262-06162-9); paperback ed. 2003 (978-0-262-56200-3). Publisher: https://mitpress.mit.edu/9780262061629/reasoning-about-knowledge/.

Summary

Reasoning About Knowledge is the standard graduate reference for the modal logic of knowledge and its application to multi-agent and distributed systems. Its central object is the operator K_i (“agent i knows”), interpreted over possible-worlds (Kripke) semantics: an agent knows a fact φ exactly when φ holds in every world it considers possible. The accessibility relation that fixes which worlds are “considered possible” is an equivalence relation, yielding the system S5 — knowledge is truthful (the T axiom), and positively and negatively introspective (the 4 and 5 axioms) — which the authors contrast with weaker logics for belief (KD45) and with notions appropriate to resource-bounded reasoners.

The book’s distinctive contribution is the runs-and-systems (interpreted systems) framework, which grounds this abstract logic in concrete computation. A run is a complete history of a multi-agent system over time; a point is a (run, time) pair; an agent’s local state determines which global points it cannot distinguish, and that indistinguishability relation is the epistemic accessibility relation. Knowledge thereby becomes an objective, ascribed property of a system’s information flow — “agent i knows φ” means φ holds at every point i cannot tell apart from the actual one — rather than a claim about anyone’s mental state. On this base the authors build the hierarchy of group knowledge: everyone-knows (E), common knowledge (C, the infinite fixpoint E^ω), and distributed/implicit knowledge (D, what the group would know by pooling). Worked epistemic puzzles — the muddy children, the coordinated-attack / two-generals problem — show why common knowledge is necessary for simultaneous coordinated action yet unattainable by message exchange in asynchronous systems, recovering the impossibility result of the authors’ own Knowledge and Common Knowledge in a Distributed Environment as a special case.

The later chapters develop the engineering payoff and the hard problems. Knowledge and time are combined into logics whose completeness and (often very high) complexity the authors chart precisely. Knowledge-based programs specify agent behaviour in terms of tests on knowledge (“if you do not know that the channel is clear, resend”), giving an implementation-independent way to design and verify protocols. Finally the book confronts logical omniscience — the unrealistic prediction of S5 that agents know all logical consequences of their knowledge — and surveys remedies: explicit-vs-implicit knowledge via awareness, local reasoning (non-omniscient societies of sub-agents), and impossible/non-standard worlds. The result is a unified treatment spanning AI, distributed computing, game theory, and philosophy.

Key Ideas

Knowledge as possible-worlds quantification: K_i φ holds iff φ is true in every world i considers possible; the logic of an equivalence accessibility relation is S5 (axioms K, T, 4, 5).
Interpreted systems / runs-and-systems: an agent’s indistinguishability over global histories defines its knowledge — an ascribed, externalist account requiring no mentalistic commitment.
Group-knowledge hierarchy: implicit/distributed knowledge D ⊒ everyone-knows E ⊒ common knowledge C; C is the fixpoint needed for simultaneous action.
Muddy children & coordinated attack: canonical puzzles showing how public announcement creates common knowledge and why no finite message chain can in asynchronous settings.
Knowledge and time: epistemic + temporal logics, with completeness axiomatisations and sharp complexity bounds (often PSPACE-complete to non-elementary).
Knowledge-based programs: protocol specifications written against knowledge tests, separating what an agent must know to act from how it represents that knowledge.
Logical omniscience and its cures: awareness operators, explicit vs implicit knowledge, local reasoning, and non-standard worlds for resource-bounded agents.
Belief vs knowledge: dropping veridicality (T) gives KD45 belief; the framework cleanly parameterises the modal strength to the application.

Connections

Knowledge and Common Knowledge in a Distributed Environment — the 1990 Halpern–Moses paper this book generalises and systematises.
Epistemic Logic
Epistemic S5
Common Knowledge (Convention) — the same E^ω construction shared with Lewis and Aumann.
Convention - Lewis
The Synthesis of Digital Machines with Provable Epistemic Properties — Rosenschein & Kaelbling compile exactly this ascribed-knowledge semantics into machines.
The Knowledge Level — Newell’s knowledge-level ascription is the AI sibling of the interpreted-systems stance.
Intention Is Choice with Commitment — Cohen & Levesque’s BDI logic layers belief/goal modalities on this same possible-worlds machinery.
Impossibility of Distributed Consensus with One Faulty Process — FLP has an epistemic reading: common knowledge of a decision is unattainable.
Time Clocks and the Ordering of Events in a Distributed System — Lamport’s local histories underpin the indistinguishable-runs semantics.
Multi-Agent Systems
Possible Worlds Semantics, Kripke Structure, Interpreted Systems, Distributed Knowledge, Knowledge-Based Programs, Logical Omniscience, Muddy Children Puzzle

Conceptual Contribution

Claim: Knowledge in a multi-agent system is not a private mental fact but an objective, ascribable property of the system’s information flow: agent i knows φ exactly when φ holds at every global state i cannot distinguish from the actual one. With this externalist move, the full modal logic of knowledge (S5), group knowledge, and knowledge-over-time become rigorous, computable tools for specifying and verifying distributed and multi-agent protocols.
Mechanism: Possible-worlds (Kripke) semantics with an equivalence accessibility relation, grounded operationally in the runs-and-systems / interpreted-systems model; a group-knowledge hierarchy (D ⊒ E ⊒ C); combined knowledge-and-time logics with completeness and complexity results; knowledge-based programs as implementation-independent protocol specs; and awareness / local-reasoning constructions to escape logical omniscience.
Concepts introduced/used: Epistemic Logic, Epistemic S5, Possible Worlds Semantics, Kripke Structure, Interpreted Systems, Common Knowledge (Convention), Distributed Knowledge, Knowledge-Based Programs, Logical Omniscience, Muddy Children Puzzle
Stance: formal / foundational textbook (logic + theory)
Relates to: Direct book-length expansion of Knowledge and Common Knowledge in a Distributed Environment; provides the semantic substrate operationalised by The Synthesis of Digital Machines with Provable Epistemic Properties; the modal-logic foundation under BDI agent theory (Intention Is Choice with Commitment) and under the game-theoretic common-knowledge of Convention - Lewis; epistemic counterpart to consensus impossibility (Impossibility of Distributed Consensus with One Faulty Process).

Tags

#epistemic-logic #common-knowledge #modal-logic #S5 #distributed-systems #knowledge-representation #multi-agent #interpreted-systems #foundational #fagin-halpern-moses-vardi

Backlinks

Linked Pages

Impossibility of Distributed Consensus with One Faulty Process

Reference

Fischer, M. J., Lynch, N. A., & Paterson, M. S. (1985). “Impossibility of Distributed Consensus with One Faulty Process.” Journal of the ACM, 32(2), 374-382. URL

Summary

The FLP result is the canonical impossibility theorem of asynchronous distributed computing. Its statement is sharp: no deterministic consensus protocol can guarantee termination in an asynchronous message-passing system if even a single process may crash. Unlike earlier results that required Byzantine faults or lossy networks, FLP assumes reliable messaging and only one benign crash failure — yet still derives impossibility.

The proof proceeds by showing that every consensus protocol admits an initial bivalent configuration (one from which either decision value is still reachable), and that from any bivalent configuration an adversary scheduler can always delay one message to force the system into another bivalent configuration. Thus an admissible run exists in which no process ever decides. The core technical tool is the commutativity of disjoint process steps (Lemma 1) and a careful analysis of “critical” configurations where a specific process’s next step is decision-forcing.

The result cleaves distributed computing into what is possible under various synchrony assumptions. Real-world protocols respond by weakening one axis: Paxos and Raft adopt partial synchrony and accept that liveness can only be guaranteed “eventually”; randomized consensus (Ben-Or, Rabin) achieves termination with probability 1; failure detectors (Chandra-Toueg ◊S) encapsulate the synchrony needed. FLP remains the bedrock boundary against which all consensus engineering is measured.

Key Ideas

Consensus problem: N processes, binary inputs; non-faulty processes must all decide the same value; some initial configuration must admit each decision.
Asynchronous model: unbounded message delays; no clocks; no timeouts.
One crash failure: the weakest possible fault assumption that still breaks consensus.
Bivalent configurations: states from which both 0 and 1 outcomes are still reachable.
Adversary scheduler: by reordering message deliveries, keeps the system in a bivalent configuration forever.
Safety vs. liveness: FLP shows safety + liveness + fault-tolerance cannot coexist in pure async.
Escape hatches: partial synchrony, randomization, failure detectors, or accepting non-termination in corner cases.

Connections

CAP Theorem — CAP is a direct relative: in partition-prone systems, atomic read/write also unattainable.
CALM Theorem — monotonic logic sidesteps consensus by avoiding it.
Keeping CALM - When Distributed Consistency is Easy
Coordination Avoidance — the design pattern motivated by FLP.
Gossip Protocols — probabilistic convergence as an alternative to deterministic agreement.
Time Clocks and the Ordering of Events in a Distributed System — Lamport’s logical time underlies the proof’s commutation arguments.
Knowledge and Common Knowledge in a Distributed Environment — common knowledge likewise unattainable in async systems.

Conceptual Contribution

Convention - Lewis

Convention: A Philosophical Study

Reference: Lewis, D. K. (1969). Convention: A Philosophical Study. Harvard University Press, Cambridge MA. (Reprinted 2002, Blackwell.) SEP entry on Convention · Wiley publisher page (book; no full-text OA.)

Summary

Lewis offers the first rigorous game-theoretic analysis of how shared conventions — including, paradigmatically, the conventions of language — arise and sustain themselves among rational agents without explicit agreement. The book opens by defining a coordination problem: a situation in which several agents have multiple equilibria available, all parties prefer reaching some equilibrium to none, and they are largely indifferent (or have non-conflicting preferences) over which equilibrium they reach. Lewis’s central thesis is that a convention is a regularity in behaviour that is one solution to a coordination problem, sustained by mutual expectation — each party expects the others to follow the regularity, expects the others to expect them to follow it, and so on up an infinite hierarchy that Lewis was the first to formalise as common knowledge. The book applies this analysis to driving conventions (drive on the right vs left), signalling, currency, and at length to language: the conventions of meaning are coordination equilibria sustained by mutual expectation in a population of speakers; semantic content is what would be the case if the convention were followed. Lewis’s framework supplies the philosophical foundation for every later treatment of emergent and negotiated meaning — emergent-communication research in MAS and deep learning, the ACL evolution programme, and the language-games tradition (Wittgenstein operationally, Steels formally) all proceed in the conceptual space Lewis defined. The common-knowledge construction is independently a foundational result for distributed-systems theory (Halpern & Moses 1990) and game theory (Aumann 1976).

Key Ideas

Coordination problem: a strategic situation with multiple Pareto-comparable equilibria where no party prefers a non-equilibrium outcome and the parties’ preferences over equilibria largely coincide. The classical examples — driving side, meeting place — generalise to language, money, social roles.
Convention as a self-sustaining regularity: a regularity R is a convention iff (i) almost everyone conforms to R, (ii) almost everyone expects almost everyone else to conform to R, (iii) almost everyone prefers conforming on the assumption that others conform, and (iv) some alternative regularity could have been the convention instead (no party of the convention is intrinsically preferred).
Common knowledge: the infinite hierarchy of mutual expectation that sustains a convention — A knows that B follows R; A knows that B knows that A follows R; and so on. Lewis was the first to give a formal account of this in social terms; the construction was rediscovered by Aumann in game theory and Halpern–Moses in distributed systems.
Salience and precedent as convention selectors: when multiple equilibria are available, salient features (Schelling’s focal points, see The Strategy of Conflict) and historical precedent select among them. There is no rationality-driven argument for which equilibrium becomes conventional; the answer is contingent on saliency.
Language as convention: meaning is what would obtain if the convention were followed. Truth-conditions, communicative force, and reference are all conventionally fixed — but the convention is not arbitrary, it is sustained by everyone’s expectation that everyone else will use words a particular way.
Conventions vs explicit agreements: Lewis argues that explicit agreement is neither necessary nor sufficient for convention — many conventions arise without agreement (precedent does the work) and many agreements never become conventions (because mutual expectation does not develop).
Population vs pair: conventions are population-level facts; one cannot have a convention with a single partner. Mutual expectation must extend across the relevant community for the regularity to be convention-grade.

Connections

Conceptual Contribution

Claim: Conventions — including the conventions of language — are best analysed as solutions to coordination problems sustained by mutual expectation (formally, common knowledge) in a population of rational agents. There is nothing arbitrary about the convention’s function, but the particular regularity that becomes conventional is contingent on salience, precedent, and historical accident.
Mechanism: Game-theoretic analysis of coordination problems with multiple equilibria; definition of convention via four clauses (conformity, mutual expectation, conditional preference, alternativeness); explicit construction of common knowledge as an infinite hierarchy of expectations; application to driving conventions, signalling, currency, and at length to language semantics.
Concepts introduced/used: Coordination Game, Convention (Lewis), Common Knowledge (Convention), Mutual Expectation, Focal Point (via dialogue with Schelling), Salience, Precedent, Convention vs Agreement.
Stance: foundational philosophical monograph.
Relates to: Direct philosophical foundation for every later treatment of emergent meaning and negotiated language: Steels’ language games are operational realisations of Lewis’s coordination-problem analysis with explicit interaction protocols; Lazaridou et al. and the deep-learning emergent-communication line train neural agents to converge on Lewis-style conventions in referential games. The ACL-evolution programme (Toward Automated Evolution of ACLs, Towards Automating the Evolution of Linguistic Competence) treats the ACL itself as an evolving Lewis-convention. Lewis’s common-knowledge construction is independently the foundation of Halpern & Moses 1990 in distributed systems and Aumann (1976) in game theory — distributed protocols and conventional language share the same mathematical object. The framework also clarifies what is at stake in the Mentalistic Semantics vs Public Semantics debate in ACLs: Lewis-style conventions are public-semantics objects (mutual-expectation regularities) but their stability depends on something close to mentalistic conditions (each agent’s expectations about others’ beliefs), so the two semantic families are dual aspects of the same phenomenon rather than competitors. Why AI Agents Communicate In Human Language revisits Lewis from the LLM-agent angle: natural language is a particular Lewis-convention (a contingent equilibrium) and not necessarily the optimal one for inter-agent coordination.

Tags

#convention #coordination #common-knowledge #lewis #philosophy-of-language #foundations #emergent-meaning

Intention Is Choice with Commitment

Reference: Cohen, P.R. & Levesque, H.J. (1990). Artificial Intelligence 42(3): 213–261. Source file: cohen-levesque-intention-is-choice-with-commitment.pdf. URL

Summary

Cohen and Levesque formalise the “rational balance” that holds between an autonomous agent’s beliefs, goals, actions, and intentions. They define intention as a composite mental attitude: a persistent goal that the agent is committed to pursuing until it is achieved, known to be impossible, or no longer relevant. This yields a modal logic whose axioms capture Bratman’s three functional roles for intention — posing problems for means-end reasoning, acting as a screen of admissibility for future intentions, and prompting the agent to track (and re-try) the success of its actions.

The paper opens with the now-classic “Willie the robot” vignette (uncommitted, overcommitted, then homicidally committed), framing intention as what an agent must reason about to be both reliable and responsive. By relativising intentions to beliefs about another agent’s intentions the authors also sketch a theory of interpersonal commitment that anticipates speech-act and multi-agent communication semantics.

Key Ideas

Persistent goal (P-GOAL): a goal an agent will not drop until it is believed achieved, believed impossible, or its relevance condition fails.
Intention defined as a P-GOAL to have done an action while believing one is about to do it — closing Bratman’s gap between intending and acting intentionally.
Avoids the “side-effect problem”: agents don’t intend foreseen side-effects of their actions.
Mutual/relativised intentions as a foundation for interpersonal commitments and speech acts.
Desiderata list (beliefs, feasibility, non-futility, tracking) becomes a standard benchmark for intention logics.

Connections

Agent-Oriented Programming
Belief-Desire-Intention
BDI Logic
BDI Architecture
Joint Intentions
Commitment
Mental State
Rational Action Semantics
Speech Act Theory
Intentional Stance
Flexible Protocol Specification and Execution
A Commitment-Based Approach to Agent Communication
Communicative Actions for Artificial Agents - Cohen Levesque — the 1995 ICMAS sequel that turns the 1990 framework into an explicit speech-act / ACL semantics; direct ancestor of FIPA-ACL.
FIPA-ACL Specifications
Mentalistic Semantics
ACL Rethinking Principles — Singh’s critique of the BDI-based ACL semantics built on this foundation.

Conceptual Contribution

Claim: Intention is not a primitive mental state but a choice with commitment — a goal plus a meta-policy for when to drop it.
Mechanism: Modal logic over beliefs and goals plus a temporal operator for persistence; intention defined compositionally so its functional roles (planning, filtering, tracking) are theorems rather than axioms.
Concepts introduced/used: Persistent Goal, Commitment, Rational Balance, Mental State, Nested Beliefs, Joint Intentions.
Stance: foundational/formal.
Relates to: Shoham’s Agent-Oriented Programming cites this paper as the prime candidate for grounding AOP’s mental-state semantics; Shoham deliberately chooses a simpler obligation/commitment primitive for AGENT-0 but frames C&L as the rigorous theory AOP languages should eventually implement. The paper also underwrites FIPA-style Mentalistic Semantics and Rational Action Semantics for ACLs.

Tags

The Synthesis of Digital Machines with Provable Epistemic Properties

Reference: Rosenschein, S.J. & Kaelbling, L.P. (1986). Theoretical Aspects of Reasoning about Knowledge: Proceedings of the 1986 Conference (J.Y. Halpern, ed.), Morgan Kaufmann, pp. 83–98. Source file: rosenschein-kaelbling-synthesis-digital-machines.pdf. URL

Summary

Rosenschein and Kaelbling introduce the situated-automata approach to knowledge: rather than treating K(x, phi) as “machine x stores a syntactic representation of phi in its knowledge base”, they define it in terms of a correlation between the state of the machine and the state of its environment. A machine “knows” phi iff phi holds in every environment-state consistent with the machine’s internal state. Under this definition the S5 axioms of epistemic logic fall out as theorems about well-designed embedded systems — without any symbolic storage of formulas.

The paper extends earlier situated-automata work to compositional hardware: synchronous digital machines are analysed by treating their gates and delay elements as agents in a multi-agent system and reasoning about information flow among them. The authors introduce Rex, a language for recursively computing machine descriptions that lets designers build machines with provable epistemic properties from the gate level up. This is the technical foundation for “knowledge as situatedness” that underpins reactive agent architectures.

Key Ideas

Situated-automata semantics: knowledge = correlation between machine state and environment state, not syntactic storage.
S5 axioms (truth, consequential closure, positive and negative introspection) provable for embedded systems under this definition.
Compositional reasoning: gates and delays modelled as agents; knowledge of the whole follows from information flow among components.
Rex: a hierarchical specification language that compiles to digital machines with guaranteed epistemic properties.
Provides a bridge between epistemic logic, control theory, and reactive robotics.

Connections

Conceptual Contribution

Claim: Knowledge in an embedded agent can be defined by state-environment correlation, so epistemic properties can be compiled into hardware rather than reasoned about at runtime.
Mechanism: Possible-worlds semantics where a machine’s internal state partitions environment states; Rex language synthesises circuits whose state partitions provably realise specified knowledge predicates.
Concepts introduced/used: Situated Automata, Correlational Knowledge, Rex Language, Epistemic S5, Embedded Agent.
Stance: foundational/formal; engineering-oriented counterpoint to symbolic AI.
Relates to: Shoham’s Agent-Oriented Programming cites this work as a key alternative route to agenthood: where AOP implements mental state as explicit data structures interpreted at runtime, Rosenschein & Kaelbling show mental state can be compiled away while preserving the same logical semantics. Shoham’s discussion of “natural vs artificial automata” and of Reactive vs Deliberative Agents directly engages with this programme.

Tags

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

Muddy Children Puzzle

The canonical worked example of Epistemic Logic and Common Knowledge. n children have muddy foreheads; each sees the others’ faces but not their own. A father announces publicly “at least one of you is muddy” and then repeatedly asks “does anyone know whether they are muddy?”. Although the announcement seemingly tells the children nothing they cannot already see, it creates common knowledge of the fact, and after k rounds of simultaneous “no” the k muddy children can all deduce their state. The puzzle shows how a public announcement changes group knowledge and how reasoning about others’ knowledge yields conclusions about one’s own.

In this vault

Logical Omniscience

The standard idealisation in possible-worlds models of knowledge: because an agent knows everything true in all worlds it considers possible, it automatically knows all logical consequences of its knowledge and every valid formula. This is unrealistic for resource-bounded reasoners (real agents do not instantly know every theorem entailed by their beliefs), and motivates weaker accounts — awareness logics, impossible-worlds, algorithmic/explicit knowledge — that relax closure under logical consequence.

In this vault

Knowledge-Based Programs

A high-level specification style (Fagin, Halpern, Moses, Vardi) in which an agent’s actions are conditioned on explicit knowledge tests — if K_i(φ) then a — rather than on concrete local-state values. The program says what an agent must know to act, abstracting away from how that knowledge is represented or attained; it is then implemented by a concrete protocol relative to a class of Interpreted Systems. Knowledge-based programs make the epistemic preconditions of coordination explicit and are a bridge from Epistemic Logic to executable distributed protocols.

In this vault

Distributed Knowledge

A group-level epistemic operator (D_G φ): the knowledge that would result if the members of group G pooled everything they individually know. It is the strongest of the standard group notions — implied by any single member’s knowledge and itself implying that the group could, by communicating, come to know φ — sitting above “everyone knows” and Common Knowledge in strength only in the sense of combining information (common knowledge is harder to attain). Formally, D_G φ holds at a world when φ is true in every world consistent with the intersection of the members’ accessibility relations.

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

Interpreted Systems

The Fagin–Halpern–Moses–Vardi model for reasoning about knowledge in distributed and multi-agent systems. A global state is a tuple of each agent’s local state plus the environment; a run is a function from time to global states, and a system is a set of runs. Two global states are indistinguishable to agent i exactly when i’s local state is the same in both — this indistinguishability relation induces the Kripke accessibility used to interpret knowledge formulae. Interpreted systems ground knowledge in what an agent can actually observe, connecting Epistemic Logic to protocol analysis.

In this vault

Kripke Structure

A model for modal/epistemic logic: a set of possible worlds (states) together with binary accessibility relations — one per agent — and a valuation fixing which atomic propositions hold at each world. An agent knows φ at a world w iff φ holds at every world the agent considers accessible from w. Equivalence (reflexive, symmetric, transitive) accessibility relations give the standard S5 logic of knowledge.

In this vault

Possible Worlds Semantics

The semantic foundation for modal and epistemic reasoning (Hintikka, Kripke): the meaning of “necessarily φ” or “agent i knows φ” is given by quantifying over a set of possible worlds. An agent knows φ when φ is true in all worlds it cannot distinguish from the actual one; uncertainty is modelled as the set of worlds an agent holds possible. Formalised concretely by Kripke structures and, for distributed settings, by Interpreted Systems.

In this vault

Epistemic S5

Standard modal logic of knowledge: knowledge is truthful (T), positively introspective (4) and negatively introspective (5).

In this vault

Epistemic Logic

Modal logic of knowledge and belief; foundational to formal agent theory (knowledge-level specifications, BDI logics, multi-agent epistemics).

In this vault

Multi-Agent Systems

Systems of multiple autonomous agents that interact, coordinate, and sometimes compete.

Foundations

Intelligent Agents Theory and Practice — Wooldridge
Multiagent Systems Sycara
Agent-Oriented Programming — Shoham

Coordination & robustness

Time, Clocks, and the Ordering of Events in a Distributed System

Reference

Lamport, L. (1978). “Time, Clocks, and the Ordering of Events in a Distributed System.” Communications of the ACM, 21(7), 558-565. URL

Summary

Lamport’s seminal paper reframes time in distributed systems. Rather than depending on physical clocks that cannot be perfectly synchronized, he defines a partial order on events — the “happened-before” relation (→) — using only causality derived from local process order and message exchange. Two events are concurrent iff neither happened before the other. This reorientation showed that a distributed system’s truth about “when” is inherently relational, not absolute, mirroring the space-time view of special relativity.

Lamport then introduces logical clocks — counters per process that assign numbers to events such that a → b implies C(a) < C(b). A simple algorithm (increment on local events; piggyback timestamps on messages; bump local clock on receipt) provides this. Extending the partial order to a total order via tiebreaking by process ID enables the classic distributed mutual exclusion algorithm that uses only message passing without a central coordinator.

The final portion generalises to physical clocks, deriving synchronization bounds that tolerate clock drift and message delay. The paper is foundational: it underlies vector clocks, causal broadcast, state-machine replication, Paxos, version vectors in Dynamo/Riak, CRDT causality tracking, and distributed snapshotting.

Key Ideas

Happened-before (→): irreflexive partial order capturing causal precedence.
Concurrency: a ∦ b when neither a → b nor b → a; cannot be eliminated in a distributed system.
Logical clocks: monotone counters satisfying the Clock Condition; do not measure real time but respect causality.
Total ordering: arbitrary tie-break on process IDs yields a global total order usable for coordination.
Distributed mutual exclusion: a worked example of using total ordering of timestamped requests to implement a resource without a central arbiter.
Space-time diagrams: process lines + message arrows — a durable visual vocabulary for distributed reasoning.
Physical clock synchronization: bounded drift + bounded message delay yield clock-sync with provable error.

Connections

CAP Theorem — partitions and concurrent writes are grounded in Lamport’s concurrent events.
CALM Theorem — monotonic computation avoids the coordination that Lamport’s algorithms provide.
Keeping CALM - When Distributed Consistency is Easy
Coordination Avoidance — when → does not need to be totally ordered.
Gossip Protocols — epidemic dissemination implicitly maintains a causal partial order.
Impossibility of Distributed Consensus with One Faulty Process — FLP shows limits of coordination Lamport makes feasible in fault-free settings.
Knowledge and Common Knowledge in a Distributed Environment — epistemic reading of causal pasts.

Conceptual Contribution

The Knowledge Level

Reference: Allen Newell (1982). “The Knowledge Level.” Artificial Intelligence 18(1): 87-127. (AAAI Presidential Address, Stanford, 19 Aug 1980; also in AI Magazine 2(2), 1981.) URL

Summary

Newell’s AAAI-80 presidential address proposes that above the symbol level (data structures manipulated by programs) there exists a distinct knowledge level whose medium is knowledge and whose laws are rationality. At the knowledge level an agent is characterised by what it knows and what goals it has; its behaviour is predicted by the principle of rationality — “if an agent knows that one of its actions will lead to a goal, it will select that action” — without commitment to any particular representation or processing mechanism.

The paper motivates the proposal by diagnosing three tensions in early-1980s AI: the mystification of “representation,” the residue of the 1960s-70s theorem-proving controversy (Planner/Microplanner/Conniver’s “uniform procedures will not work” reaction against resolution), and the diversity of answers in the SIGART Special Issue on Knowledge Representation (Brachman and Smith’s survey showing no consensus on quantification, quotation, self-description, or evaluation). Newell’s resolution: treat knowledge as a competence-level notion analogous to physicists’ treatment of temperature — a level with its own laws, reduced to but not replaced by the symbol level. Representations are then understood as symbol-level implementations of knowledge, and we gain a principled way to talk about what an AI system knows without confusing it with how that knowledge is stored.

The Knowledge Level is foundational for agent-oriented programming (Shoham’s “mental state” framing), for the BDI tradition, for KQML’s and FIPA’s claim that ACL semantics should be defined at the level of beliefs/intentions rather than byte-strings, and indirectly for McCarthy’s Elephant 2000, whose speech-act semantics presupposes that one can talk coherently about what a program knows and is committed to, independently of implementation.

Key Ideas

Computer systems are describable at multiple levels (device, circuit, logic, register-transfer, program/symbol); the knowledge level sits above the symbol level.
Medium of the knowledge level: knowledge (distinct from the data structures that represent it).
Law of behaviour at the knowledge level: the principle of rationality — actions selected to achieve goals given what is known.
The knowledge level is a competence-level account: it predicts behaviour without specifying mechanism, analogously to economic rationality.
Representation is the symbol-level realisation of knowledge; mystifying representation conflates the levels.
Diagnostic of the theorem-proving backlash: “uniform procedures will not work” was a symbol-level reaction to a knowledge-level question.

Connections

Agent-Oriented Programming — Shoham explicitly situates AOP at the knowledge level; mental states are Newell-level predicates over agents.
Elephant 2000 - A Programming Language Based on Speech Acts — Elephant commits to knowledge-level program variables (propositions, commitments, past speech acts), making knowledge-level description the native semantics of programs.
Ascribing Mental Qualities to Machines — McCarthy’s ascriptivism is the philosophical cousin of Newell’s levels argument.
Knowledge Representation
Agent Communication Languages — ACL semantics in the KQML/FIPA tradition are knowledge-level (beliefs/intentions) rather than symbol-level (bit patterns).
KIF — intended as a lingua franca at the symbol level that preserves knowledge-level content across heterogeneous systems.
Common Sense Reasoning

Conceptual Contribution

Claim: AI systems have a level of description above the symbol level — the knowledge level — whose medium is knowledge and whose law is rationality; this level is reducible to but not replaceable by the symbol level, and recognising it clarifies decades of representation debates.
Mechanism: Levels-of-description methodology imported from computer architecture; principle of rationality as the behaviour law; knowledge characterised competence-theoretically (what follows from what an agent knows and wants, not how); representations reconceived as symbol-level implementations of knowledge-level content; diagnostic application to the theorem-proving controversy and the SIGART Special Issue.
Concepts introduced/used: Knowledge Level, Symbol Level, Principle of Rationality, Competence vs Performance, Knowledge Representation, Levels of Description.
Stance: foundational
Relates to: The conceptual ground for agent-oriented and BDI programming; provides the “what an agent knows” vocabulary that KQML, Agent Communication Languages, and Elephant 2000 - A Programming Language Based on Speech Acts rely on; complements McCarthy’s ascriptivist argument in Ascribing Mental Qualities to Machines.