Knowledge and common knowledge in a distributed environment

By Joseph Y. Halpern, Yoram Moses. 1984

Reasoning about knowledge seems to play a fundamental role in distributed systems. Indeed, such reasoning is a central part of the informal intuitive arguments used in the design of distributed protocols. Communication in a distributed system can be viewed as the act of transforming the system's state of knowledge. This paper presents a general framework for formalizing and reasoning about knowledge in distributed systems. It is shown that states of knowledge of groups of processors are useful concepts for the design and analysis of distributed protocols. In particular, distributed knowledge corresponds to knowledge that is “distributed” among the members of the group, while common knowledge corresponds to a fact being “publicly known.” The relationship between common knowledge and a variety of desirable actions in a distributed system is illustrated. Furthermore, it is shown that, formally speaking, in practical systems common knowledge cannot be attained. A number of weaker variants of common knowledge that are attainable in many cases of interest are introduced and investigated.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Multi-Agent Common Knowledge Reinforcement Learning (2018, background): “Korkmaz et al. (2014) examine common knowledge in scenarios where agents use Facebook-like communication.”
Complex Epistemic Modalities in the Situation Calculus (2008, background): “This paper clearly owes much to the heritage of dynamic epistemic logics in general (Halpern & Moses 1990; Batlag, Moss, & Solecki 1998) and the development of LCC in particular (van Benthem, van Eijck, & Kooi 2006).”
Synchronization risk and delayed arbitrage (2002, background): “Morris (1995) develops a dynamic coordination game based on the idea of ''asynchronous clocks'' of Halpern and Moses (1990), which has some similarities to the model we develop.”
Cooperation, Knowledge, and Time: Alternating-time Temporal Epistemic Logic and its Applications (2003, background): “Schema (xxix) expresses that it is common knowledge in the group that it can bring about (next, or sometime, or always) ’. Note that this is the kind of scenario made famous in the coordinated attack problem, and the associated negative result, to the eect that, if message delivery is not guaranteed”
Toward a mechanistic psychology of dialogue (2004, methodology): “However, there is no foolproof procedure for establishing mutual knowledge expressed in terms of this iterative formulation because it requires formulating recursive models of interlocutors’ beliefs (see Barwise 1989; Clark 1996, Ch 4; Halpern & Moses 1990; Lewis 1969).”
The limits to designed orders: Authority under “distributed knowledge” conditions (2006, background): “when there are “costs of using the price mechanism”: Why exactly should judgment become increasingly ineffective as firm size increased? Kaldor (1934) argue that the “entrepreneur” is the fixed, limiting factor: Firm size will be constrained by the amount of judgment that could be derived from this ”