|
 ABSTRACT
We argue that the right way to understand distributed protocols is by considering how messages change the state of knowledge of a system. We present a hierarchy of knowledge states that a system may be in, and discuss how communication can move the system's state of knowledge of a fact up the hierarchy. Of special interest is the notion of common knowledge. Common knowledge is an essential state of knowledge for reaching agreements and coordinating action. We show that in practical distributed systems, common knowledge is not attainable. We introduce various relaxations of common knowledge that are attainable in many cases of interest. We describe in what sense these notions are appropriate, and discuss their relationship to each other. We conclude with a discussion of the role of knowledge in distributed systems.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
R. J. Aumann, Agreeing to disagree, Annals of Statistics, 4:6, 1976.
|
| |
2
|
J. Barwise, Scenes and other situations, Journal of Philosophy, Vol. LXXVIII, No. 7, 1981, 369-397.
|
| |
3
|
H. H. Clark and C. R. Marshall, Definite reference and mutual knowledge, in A. K. Joshi, B. L. Webber, and I. A. Sag (Eds.), Elements of Discourse Understanding, Cambridge University Press, 1981.
|
| |
4
|
D. Dolev, C. Dwork, and L. Stockmeyer, On the minimal synchronization needed for distributed consensus, FOCS, 1983, pp. 369-397.
|
| |
5
|
D. Dolev, J. Y. Halpern, and Y. Moses, Cheating husbands and other stories: a case study of common knowledge, unpublished manuscript, 1984.
|
 |
6
|
|
| |
7
|
D. Dolev and H. R. Strong, Byzantine agreement, IBM Research Report RJ 3714, 1982.
|
| |
8
|
|
| |
9
|
Joseph Y. Halpern , Barbara Simons , Ray Strong , Danny Dolev, Fault-tolerant clock synchronization, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.89-102, August 27-29, 1984, Vancouver, British Columbia, Canada
[doi> 10.1145/800222.806739]
|
| |
10
|
J. Hintikka, Knowledge and Belief, Cornell University Press, 1962.
|
| |
11
|
D. Kozen and R. Parikh, An elementary proof of the completeness of PDL, Theoretical Computer Science, 14:1, 1981, pp. 113-118.
|
| |
12
|
|
| |
13
|
B. Lindsay et al., Notes on Distributed Databases, IBM Research Report RJ 2571, 1979.
|
| |
14
|
L. Lamport and M. Fischer, Byzantine generals and transaction commit protocols, SRI International Report, 1982.
|
| |
15
|
L. Lamport and P. M. Melliar-Smith, Synchronizing clocks in the presence of faults, SRI International Report, 1982.
|
| |
16
|
J. McCarthy, Lecture Notes 1968—1974.
|
| |
17
|
R.C. Moore, Reasoning about knowledge and action, Artificial Intelligence Center Technical Note 191, SRI International, 1980.
|
| |
18
|
|
| |
19
|
|
CITED BY 81
|
|
|
|
|
Joseph Y. Halpern , Yoram Moses , Orli Waalrts, A characterization of eventual Byzantine agreement, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.333-346, August 22-24, 1990, Quebec City, Quebec, Canada
|
|
|
Ajei Gopal , Ray Strong , Sam Toueg , Flaviu Cristian, Early-delivery atomic broadcast, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.297-309, August 22-24, 1990, Quebec City, Quebec, Canada
|
|
|
J. Y. Halpern , M. R. Tuttle, Knowledge, probability, and adversaries, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.103-118, June 1989, Edmonton, Alberta, Canada
|
|
|
Joseph Halpern , Yjoram Moses , Mark Tuttle, A knowledge-based analysis of zero knowledge, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.132-147, May 02-04, 1988, Chicago, Illinois, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
S Goldwasser , S Micali , C Rackoff, The knowledge complexity of interactive proof-systems, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.291-304, May 06-08, 1985, Providence, Rhode Island, United States
|
|
|
Lily B. Mummert , Jeannette M. Wing , M. Satyanarayanan, Using belief to reason about cache coherence, Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.71-80, August 14-17, 1994, Los Angeles, California, United States
|
|
|
|
|
|
|
|
|
M. J. Fischer , S. Moran , R. Rudich , G. Taubenfeld, The wakeup problem, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.106-116, May 13-17, 1990, Baltimore, Maryland, United States
|
|
|
|
|
|
|
|
|
Joseph Y. Halpern , Ronald Fagin, A formal model of knowledge, action, and communication in distributed systems: preliminary report, Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.224-236, August 1985, Minaki, Ontario, Canada
|
|
|
|
|
|
|
|
|
Yoram Moses , Danny Dolev , Joseph Y. Halpern, Cheating husbands and other stories (preliminary version): a case study of knowledge, action, and communication, Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.215-223, August 1985, Minaki, Ontario, Canada
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Wang Xianchang , Chen Huowang , Zhao Qingping , Li Wei, W: a logic system based on shared common knowledge views, Proceedings of the 13th international joint conference on Artifical intelligence, p.410-414, August 28-September 03, 1993, Chambery, France
|
|
|
|
|
|
|
|
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
I.2