Foundations of Knowledge for Distributed Systems.
Abstract
Halpern and Moses present an interesting discussion of knowledge and common knowledge and common knowledge for distributed systems. They argue that while common knowledge is desirable, it is unattainable in certain settings. They suggest a hierarchy of weakened versions of common knowledge and discuss when these can be achieved. One difficulty with the Halpern and Moses paper is that it is informal and the concepts dealt with are not rigourous defined. Given one interpretation, their theorems are true as claimed, but given another, the opposite occurs, as we show with appropriate counterexamples. Thus, their theorems are not wrong in spirit, but the concepts are subtle and the terms must be more carefully defined. This paper gives quite general and precise definitions of distributed protocol, knowledge and common knowledge. It also provides precise settings and rigorous proofs for many of the results in Halpern's and noses' paper. This paper proposes some alternate definitions in which the same results become false. The authors desire to develop a way to design clear distributed algorithms and write clear proofs about them. Additional keywords: Distributed data processing.
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 01, 1985
- Accession Number
- ADA160233
Entities
People
- M. J. Fisher
- N. Immerman
Organizations
- Yale University