Knowledge and common knowledge in a distributed environment
- 1 July 1990
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 37 (3), 549-587
- https://doi.org/10.1145/79147.79161
Abstract
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.Keywords
This publication has 19 references indexed in Scilit:
- Belief, awareness, and limited reasoningArtificial Intelligence, 1987
- On the possibility and impossibility of achieving clock synchronizationJournal of Computer and System Sciences, 1986
- How processes learnDistributed Computing, 1986
- FOUNDATIONS OF KNOWLEDGE FOR DISTRIBUTED SYSTEMSPublished by Elsevier BV ,1986
- Knowledge and Common Knowledge in a Byzantine Environment I: Crash failuresPublished by Elsevier BV ,1986
- Optimal precision in the presence of uncertaintyJournal of Complexity, 1985
- Impossibility of distributed consensus with one faulty processJournal of the ACM, 1985
- Distributed snapshotsACM Transactions on Computer Systems, 1985
- Using branching time temporal logic to synthesize synchronization skeletonsScience of Computer Programming, 1982
- Agreeing to DisagreeThe Annals of Statistics, 1976