In classical philosophy and modal logic, "knowledge" is often treated as an abstract relation over an infinite set of abstract possible worlds. While elegant, this formulation fails when applied to computer systems. A distributed protocol, a software agent, or a robot cannot reason about abstract metaphysics; its reality is strictly bounded by physical constraints like memory logs, network packets, and bit-level variable values.
To bridge this gap, a powerful framework emerged that grounds epistemic logic (the logic of knowledge) directly into the concrete states of physical machines. The core intuition is simple: an agent's knowledge is defined by what it cannot distinguish. If two entirely different global configurations of a system look identical from an agent's local perspective, those configurations are indistinguishable. By formalizing this indistinguishability, we can transform subjective notions of "mental state" into objective, mathematically verifiable properties of computer programs.
The Mechanics of Local-Global Mapping
To understand why this framework works, we must look at how it structures a system. As formalized by Joseph Halpern et al. in What Can Machines Know? On the Epistemic Properties of Machines, a system is modeled as a collection of execution paths, or "runs," over time. At any given moment, the system is in a specific global state. This global state is a combination of the environment's state and the internal local states of all individual processes or agents.
An agent does not have access to the full global state; it can only "see" its own local state (its memory, program counter, and input logs). This creates an equivalence relation over global states:
$$\text{Global State } s \sim_i \text{Global State } s' \iff \text{Agent } i \text{ has the same local state in } s \text{ and } s'$$
Using this relation, we define knowledge strictly through a local lens: an agent knows a fact $\phi$ if $\phi$ is true in all global states that are indistinguishable from its current state. As Joseph Halpern et al. point out in Knowledge and Probability in Distributed Systems (Abstract), an agent's knowledge is a direct function of its local state. If its internal memory and logs are identical in two different scenarios, it cannot distinguish between them, and its reasoning must account for both possibilities.
This perspective shifts knowledge from a vague philosophical concept to an objective property of program execution. As Michael J. Wooldridge demonstrates in Verifying that Agents Implement a Communication Language, this allows us to verify whether an agent is adhering to a protocol by checking its bit-level variables and control flow against the set of indistinguishable global states.
Bounding Strategy by Perspective
Grounding knowledge in local states fundamentally changes how we reason about multi-agent interactions and game theory. Traditional game theory relies on abstract "information sets" to represent what a player knows. However, using local states provides a much more granular model.
In A computer scientist looks at game theory, Joseph Halpern et al. argue that by tracking local states across system runs, we can naturally capture complex informational constraints like imperfect recall (where an agent forgets past states) or incomplete information. For instance, the authors demonstrate in Characterizing Solution Concepts in Games Using Knowledge-Based Programs that standard game-theoretic equilibria (like Nash Equilibrium) can be re-framed as "knowledge-based programs" executing across different informational contexts.
Crucially, this framework enforces that an agent's actions must be bounded by its unique perspective. As Francesco Belardinelli shows in Reasoning about Knowledge and Strategies: Epistemic Strategy Logic, an agent cannot choose a strategy that requires information it does not possess. If two global states are indistinguishable to an agent, the agent's protocol must prescribe the exact same action in both states.
This distinction is vital when moving from individual knowledge to collective action. For a coalition of agents to achieve a goal, it is not enough for a winning strategy to exist abstractly; the group must actually know how to execute it based on their collective information. Pavel Naumov formalizes this interplay between information and action in Together We Know How to Achieve: An Epistemic Logic of Know-How (Extended Abstract) and Strategic Coalitions with Perfect Recall. By utilizing epistemic transition systems, these frameworks show that a coalition can successfully execute a strategy only if their distributed knowledge allows them to select the correct joint actions across all indistinguishable states.
Collective Knowledge and Information Hiding
When multiple agents interact, coordination requires tracking not just what an agent knows, but what it knows about others' knowledge. For example, distributed coordination often requires "common knowledge"—the state where everyone knows that everyone knows a fact ad infinitum. Joseph Halpern et al. explore this in Common knowledge revisited, demonstrating how agents navigate through states of local uncertainty toward shared epistemic goals.
Conversely, some systems are designed to prevent knowledge. In security and privacy, the same indistinguishability relation is used to define information hiding. In Anonymity and Information Hiding in Multiagent Systems, Joseph Halpern et al. show that anonymity can be mathematically defined using indistinguishable execution paths. If an observer's local state is identical regardless of whether User A or User B performed an action, then the system guarantees perfect anonymity.
Making Knowledge Computable
The ultimate power of grounding knowledge in local states is that it makes epistemic properties algorithmically verifiable. If knowledge were purely abstract, verifying it would be impossible. But because knowledge is mapped to variables, we can evaluate knowledge operators via automated model checking.
As Kaile Su demonstrates in Model Checking Temporal Logics of Knowledge in Distributed Systems, evaluating what an agent knows reduces to quantifying over the variables that the agent cannot observe. By leveraging Ordered Binary Decision Diagrams (OBDDs), this approach automatically identifies all global states that match an agent's local variables, allowing for direct verification of distributed protocols. This interpreted systems framework is similarly utilized by Xiaowei Huang et al. in Model Checking Knowledge in Pursuit Evasion Games to verify complex, multi-agent strategic objectives over time.
Managing the State Explosion
The primary challenge of this approach is computational complexity. Tracking every possible combination of indistinguishable global states quickly leads to a combinatorial explosion. To make verification practical, researchers use abstraction techniques to simplify the state space while preserving epistemic properties:
- Three-Valued Abstraction: Francesco Belardinelli et al. introduce a method in A Three-valued Approach to Strategic Abilities under Imperfect Information that groups indistinguishable states into single equivalence classes. It uses a three-valued logic (true, false, and undefined) with "must" transitions (actions valid across all concrete states in a class) and "may" transitions (actions valid in at least one) to verify strategic abilities without exploring every concrete state.
- Common Knowledge Neighborhoods: In Bisimulations for verifying strategic abilities with an application to the ThreeBallot voting protocol, Francesco Belardinelli et al. utilize "common knowledge neighborhoods." This groups states that agents cannot collectively distinguish, allowing bisimulation algorithms to operate on collective knowledge blocks rather than individual states, drastically reducing the state space.
Despite these optimizations, reasoning about local state indistinguishability remains inherently challenging. As Krzysztof R. Apt et al. prove in On the Computational Complexity of Gossip Protocols, evaluating an agent's local "guards" (decisions based on current knowledge) requires reasoning over all valid sequences of interactions that could have led to that local observation. This makes protocol verification highly complex ($P^{NP}$-complete to $coNP^{NP}$).
Yet, it is precisely this rigorous, state-grounded complexity that makes the framework so valuable. By defining knowledge through the lens of local state indistinguishability, computer scientists can reason about information, secrecy, and strategy with the exact same precision they use to debug a physical circuit or a distributed database.
Key Foundational Work
What Can Machines Know? On the Epistemic Properties of Machines (1986) — contributed 1 concept elements to this direction.
Knowledge and Common Knowledge in a Distributed Environment (1984) — contributed 1 concept elements to this direction.