article

Free access

Knowledge and common knowledge in a distributed environment

Authors:

Joseph Y. Halpern,

Yoram MosesAuthors Info & Claims

Journal of the ACM (JACM), Volume 37, Issue 3

Pages 549 - 587

https://doi.org/10.1145/79147.79161

Published: 01 July 1990 Publication History

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.

References

[1]

AUMANN, R.J. Agreeing to disagree. Ann. Stat. 4, 6(1976), 1236-1239.

[2]

BARWlSV, J. Scenes and other situations. J. Philo. LXXVIII 7 (1981), 369-397.

[3]

CHANDY, K. M., AND LAMPORT, L. Distributed snapshots: Determining global states of distributed systems. ACM Trans. Comput. Syst. 3, 1 (1985), 63-75.

[4]

CHANDY, K. M., AND MISRA, J. How processes learn. Dist. Comput. 1, 1 (1986), 40-52.

[5]

CLARK, H. H., AND MARSHALL, C.R. Definite reference and mutual knowledge. In Elements of Discourse Understanding, A. K. Joshi, B. L. Webber, and I. A. Sag, eds. Cambridge University Press, Cambridge, Mass., 1981, pp. 10-63.

[6]

CRISTIAN, F., AGHILI, H., STRONG, H. R., AND DOLLY, n. Atomic broadcast: From simple diffusion to Byzantine agreement. In Proceedings of the 15th International Annual Symposium on Fault- Tolerant Computing Systems. IEEE, Washington, D.C., 1985, pp. 200-206.

[7]

DOLEV, D., HALPERN, J. Y., AND STRONG, H.R. On the possibility and impossibility of achieving clock synchronization. J. Comput. Syst. Sci. 32, 2 (1986), 230-250.

[8]

DOLEV, D., REISCHUK, R., AND STRONG, H.R. Eventual is earlier than immediate. In Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science. IEEE, Washington, D.C., 1982, pp. 196-203.

[9]

DWORK, C., AND MOSES, Y. Knowledge and common knowledge in a Byzantine environment I: Crash failures (extended abstract). In Theoretical Aspects of Reasoning about Knowledge: Proceedings of the 1986 Conference, J. Y. Halpern, ed. Morgan Kaufmann, San Mateo, Calif., 1986, pp. 149-170. Inf. Computation, in press.

[10]

EMERSON, E. A., AND CLARKE, E. M. Using branching time temporal logic to synthesize synchronization skeletons. Sci. Comput. Prog. 2 (1982), 241-266.

[11]

FAGIN, R., AND HALPERN, J.Y. Belief, awareness, and limited reasoning. Artif. Int. 34 (1988), 39-76.

[12]

FAGIN, R., AND HALPERN, J.Y. Reasoning about knowledge and probability: Preliminary report. In Proceedings of the 2nd Conference on Theoretical Aspects of Reasoning about Knowledge, M. Y. Vardi, ed. Morgan Kaufmann, San Mateo, Calif., 1988, pp. 277-293.

[13]

FAGIN, R., HALPERN, J. V., AND VARDI, i.V. What can machines know? On the epistemic properties of machines. In Proceedings of the National Conference on Artificial Intelligence (AAAI- 86), 1986, pp. 428-434. A revised and expanded version appears as: What can machines know? On the properties of knowledge in distributed systems. IBM Res. Rep. RJ56250. IBM, 1988.

[14]

FISCHER, M. J., AND IMMERMAN, N. Foundations of knowledge for distributed systems. In Theoretical Aspects of Reasoning about Knowledge: Proceedings of the 1986 Conference, J. Y. Halpern, ed. Morgan Kaufmann, San Mateo, Calif., 1986, pp. 171-186.

[15]

FISCHER, i. J., LYNCH, N. A., AND PATERSON, M.S. Impossibility of distributed consensus with one faulty processor. J. ACM 32, 2 (1985), 374-382.

[16]

GALLAGER, R.G. Seminar on computer communication networks. Office of Industrial Liaison, NIT, Cambridge, Mass., 1979.

[17]

GRAY, j. Notes on database operating systems. IBM Res. Rep. RJ 2188. IBM, Aug. 1987.

[18]

HADZILACOS, V. A knowledge-theoretic analysis of atomic commitment protocols. In Proceedings of the 6th ACM Symposium on Principles of Database Systems. ACM, New York, 1987, pp. 129-134. A revised version has been submitted for publication.

[19]

HALPERN, J. Y. Using reasoning about knowledge to analyze distributed systems. In Annual Review of Computer Science, Vol. 2, J. Traub, B. Grosz, B. Lampson, and N. Nilson, eds. Annual Reviews, Inc., Palo Alto, Calif., 1987, pp. 37-68.

[20]

HALPERN, J. Y., AND FAGIN, R. A formal model of knowledge, action, and communication in distributed systems: Preliminmary report. In Proceedings of the 4th ACM Symposium on Principles of Distributed Computing. ACM, New York, 1985, pp. 224-236. A revised version appears as: Modelling knowledge and action in distributed systems. Dist. Computations 3 (1989), 159-177.

[21]

HALPERN, J. V., MEGIDDO, N., AND MUNSHI, A. Optimal precision in the presence of uncertainty. J. Complexity 1 (1985), 170-196.

[22]

HALPERN, J. Y., AND MOSES, Y. Knowledge and common knowledge in a distributed environment. In Proceedings of the 3rd ACM Conference on Distributed Computing. ACM, New York, 1984, pp. 50-61. A revised and expanded version appears as: IBM Res. Rep. RJ 4421. IBM, Yorktown Heights, N.Y., 1988.

[23]

HALPERN, J. V., AND MOSES, Y. A guide to the modal logics of knowledge and belief. In Proceedings of the 9th International Joint Conference on Artificial Intelligence (IJCAI-85). 1985, pp. 480-490.

[24]

HALPERN, J. Y., AND ZUCK, L.D. A little knowledge goes a long way: Simple knowledge-based derivations and correctness proofs for a family of protocols. IBM Res. Rep. RJ 5857. IBM, 1987.

[25]

HINTIKKA, J. Knowledge and Belief Cornell University Press, Ithaca, N.Y., 1962.

[26]

KATZ, S., AND TAUBENFELD, G. What processes know: Definitions and proof methods. In Proceedings of the 5th ACM Symposium on Principles of Distributed Computing. ACM, New York, 1986, pp. 249-262.

[27]

KOZEN, D. Results on the propositional ~-calculus. Theoret. Comput. Sci. 27, 1 (1983), 333-354.

[28]

LADNER, R., AND REIF, J. The logic of distributed protocols (preliminary report). In Theoretical Aspects of Reasoning about Knowledge: Proceedings of the 1986 Conference, J. Y. Halpern, ed. Morgan Kaufman, San Mateo, Calif., 1986, pp. 207-222.

[29]

LEVESQtJE, H. A logic of implicit and explicit belief. In Proceedings of the National Conference on Artificial Intelligence (AAAI-84 ). 1984, pp. 198-202.

[30]

MANNA, Z., AND WOLPER, P. L. Synthesis of communication processes from temporal logic specifications. ACM Trans. Program. Lang. Syst. 6, 1 (1984), 68-93.

[31]

MAZER, M.S. A knowledge theoretic account of recovery in distributed systems: The case of negotiated commitment. In Proceedings of the 2nd Conference on Theoretical Aspects of Reasoning about Knowledge, M. Y. Vardi, ed. Morgan Kaufman, San Mateo, Calif., 1988, pp. 309-324.

[32]

MCCARTHY, J., SATO, M., HAYASHh T., AND IGARISm, S. On the model theory of knowledge. Tech. Rep. STAN-CS-78-657. Stanford Univ., Stanford, Calif., 1979.

[33]

MOORE, R.C. A formal theory of knowledge and action. In Formal Theories of the Commonsense World, J. Hobbs and R. C. Moore, eds. Ablex Publishing Corp., Norwood, N.J., 1985, pp. 319-358.

[34]

MOSES, Y. Resource-bounded knowledge. In Proceedings of the 2nd Conference on Theoretical Aspects of Reasoning about Knowledge, M. Y. Vardi, ed. Morgan Kaufmann, San Mateo, Calif., 1988, pp. 261-276.

[35]

MOSES, Y., DOLEV, D., AND HALPERN, J.Y. Cheating husbands and other stories: A case study of knowledge, action, and communication. Dist. Comput. 1, 3 (1986), 167-176.

[36]

MOSES, Y., AND TUTTLE, M.R. Programming simultaneous actions using common knowledge. Algorithmica 3 (1988), 121-169.

[37]

NEIGER, G. Knowledge consistency: A useful suspension of disbelief. In Proceedings of the 2nd Conference on Theoretical Aspects of Reasoning about Knowledge, M. Y. Vardi, ed. Morgan Kaufman, San Mateo, Calif., 1988, pp. 295-308.

[38]

NF.IGER, G., AND TOUEG, S. Substituting for real time and common knowledge in asynchronous distributed systems. J. A CM.

[39]

PANANGADEN, P., AND TAYLOR, S. Concurrent common knowledge: a new definition of agreement for asynchronous systems. In Proceedings of the 7th ACM Symposium on Principles of Distributed Computing. ACM, New York, 1988, pp. 197-209.

[40]

PARIKH, R. AND RAMANUJAM, R. Distributed processing and the logic of knowledge. In Proceedings of the Workshop on Logics of Programs, R. Parikh, ed. Springer-Verlag, Berlin, 1985, pp. 256-268.

[41]

ROSENSCHEIN, S.J. Formal theories of AI in knowledge and robotics. New Gen. Comput. 3 (1985), 345-357.

[42]

ROSENSCHEIN, S. J., AND KAELBLING, L. P. The synthesis of digital machines with provable epistemic properties. In Theoretical Aspects of Reasoning about Knowledge: Proceedings of the 1986 Conference, J. Y. Halpern, ed. Morgan Kaufmann, San Mateo, Calif., 1986, pp. 83-97.

[43]

TARSKI, A. A lattice-theoretic fixpoint theorem and its applications. Pacific J. Math. 5 (1955), 285-309.

[44]

YEMINI, Y., AND COHEN, D. Some issues in distributed processes communication. In Proceedings of the 1st International Conference on Distributed Computing Systems. IEEE, Washington, D.C., 1979, pp. 199-203.

Cited By

Beutner RFinkbeiner BFrenkel HMetzger NDastani MSichman JAlechina NDignum V(2024)Monitoring Second-Order HyperpropertiesProceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems10.5555/3635637.3662865(180-188)Online publication date: 6-May-2024
https://dl.acm.org/doi/10.5555/3635637.3662865
Katarzyniak RPopek GŻurawski M(2024)Implementing Cognitive Semantics of Autoepistemic Membership Statements: The Case of Categories with PrototypesApplied Sciences10.3390/app1404160914:4(1609)Online publication date: 17-Feb-2024
https://doi.org/10.3390/app14041609
Wojtowicz Z(2024)Context and CommunicationSSRN Electronic Journal10.2139/ssrn.4765417Online publication date: 2024
https://doi.org/10.2139/ssrn.4765417
Show More Cited By

Index Terms

Knowledge and common knowledge in a distributed environment

Recommendations

Knowledge and common knowledge in a distributed environment
PODC '84: Proceedings of the third annual ACM symposium on Principles of distributed computing

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 ...
Concurrent common knowledge: defining agreement for asynchronous systems

In this paper we present a new, knowledge-theoretic definition of agreement designed for asynchronous systems. In analogy with common knowledge, it is called concurrent common knowledge. Unlike common knowledge, it is a form of agreement that is ...
Perspective---Tacit Knowledge and Knowledge Conversion: Controversy and Advancement in Organizational Knowledge Creation Theory

Nonaka's paper [1994. A dynamic theory of organizational knowledge creation. Organ. Sci.5(1) 14--37] contributed to the concepts of “tacit knowledge” and “knowledge conversion” in organization science. We present work that shaped the development of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 37, Issue 3

July 1990

247 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/79147

Issue’s Table of Contents

Copyright © 1990 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 1990

Published in JACM Volume 37, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

669
Total Citations
View Citations
5,115
Total Downloads

Downloads (Last 12 months)653
Downloads (Last 6 weeks)70

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Beutner RFinkbeiner BFrenkel HMetzger NDastani MSichman JAlechina NDignum V(2024)Monitoring Second-Order HyperpropertiesProceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems10.5555/3635637.3662865(180-188)Online publication date: 6-May-2024
https://dl.acm.org/doi/10.5555/3635637.3662865
Katarzyniak RPopek GŻurawski M(2024)Implementing Cognitive Semantics of Autoepistemic Membership Statements: The Case of Categories with PrototypesApplied Sciences10.3390/app1404160914:4(1609)Online publication date: 17-Feb-2024
https://doi.org/10.3390/app14041609
Wojtowicz Z(2024)Context and CommunicationSSRN Electronic Journal10.2139/ssrn.4765417Online publication date: 2024
https://doi.org/10.2139/ssrn.4765417
van Ditmarsch HKuznets R(2024)Wanted dead or alive: epistemic logic for impure simplicial complexesJournal of Logic and Computation10.1093/logcom/exae055Online publication date: 7-Oct-2024
https://doi.org/10.1093/logcom/exae055
Bouchard Y(2024)Inferential knowledge and epistemic dimensionsLogic Journal of the IGPL10.1093/jigpal/jzae095Online publication date: 6-Sep-2024
https://doi.org/10.1093/jigpal/jzae095
Castañeda Avan Ditmarsch HRosenblueth DVelázquez D(2024)Pattern Models: A Dynamic Epistemic Logic For Distributed SystemsThe Computer Journal10.1093/comjnl/bxae01667:7(2421-2440)Online publication date: 17-Feb-2024
https://doi.org/10.1093/comjnl/bxae016
Wilby M(2024)Common Knowledge and Hinge EpistemologyInternational Journal of Philosophical Studies10.1080/09672559.2024.232870332:1(169-190)Online publication date: 28-Mar-2024
https://doi.org/10.1080/09672559.2024.2328703
van Ditmarsch HGattinger M(2024)You can only be lucky once: optimal gossip for epistemic goalsMathematical Structures in Computer Science10.1017/S0960129524000082(1-28)Online publication date: 19-Apr-2024
https://doi.org/10.1017/S0960129524000082
Goubault ÉKniazev RLedent JRajsbaum S(2024)Simplicial models for the epistemic logic of faulty agentsBoletín de la Sociedad Matemática Mexicana10.1007/s40590-024-00656-x30:3Online publication date: 9-Sep-2024
https://doi.org/10.1007/s40590-024-00656-x
Galimullin RVelázquez-Quesada F(2024)Topic-Based Communication Between AgentsStudia Logica10.1007/s11225-024-10119-zOnline publication date: 31-Aug-2024
https://doi.org/10.1007/s11225-024-10119-z
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents