Knowledge and common knowledge in a distributed environment

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'...

Full description

Saved in:
Bibliographic Details
Published in:Journal of the ACM 1990-07, Vol.37 (3), p.549-587
Main Authors: HALPERN, J. Y, MOSES, Y
Format: Article
Language:English
Subjects:
Applied sciences
Communication systems
Computer networks
Computer science
control theory
systems
Computer systems and distributed systems. User interface
Design analysis
Design engineering
Exact sciences and technology
Processors
Reasoning
Software
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0004-5411
1557-735X
DOI:10.1145/79147.79161