Knowledge and common knowledge in a distributed environment

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: K. Mani Chandy , Leslie Lamport, Distributed snapshots: determining global states of distributed systems, ACM Transactions on Computer Systems (TOCS), v.3 n.1, p.63-75, Feb. 1985 [doi>10.1145/214451.214456]
• 4: K. M. Chandy , Jayadev Misra, How processes learn, Distributed Computing, v.1 n.1, p.40-52, Jan. 1986 [doi>10.1007/BF01843569]
• 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: Danny Dolev , Joseph Y Halpern , Raymond H Strong, On the possibility and impossibility of achieving clock synchronization, Journal of Computer and System Sciences, v.32 n.2, p.230-250, April 1986 [doi>10.1016/0022-0000(86)90028-0]
• 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: C Dwork , Y Moses, Knowledge and common knowledge in a Byzantine environment I: crash failures, Proceedings of the 1986 Conference on Theoretical aspects of reasoning about knowledge, p.149-169, March 1986, Monterey, California, United States
• 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: R. Fagin , J. Y. Halpern, Belief, awareness, and limited reasoning, Artificial Intelligence, v.34 n.1, p.39-76, Dec. 1987 [doi>10.1016/0004-3702(87)90003-8]
• 12: Ronald Fagin , Joseph Y. Halpern, Reasoning about Knowledge and Probability, Proceedings of the 2nd Conference on Theoretical Aspects of Reasoning about Knowledge, p.277-293, March 01, 1988
• 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: M Fischer , N Immerman, Foundations of knowledge for distributed systems, Proceedings of the 1986 Conference on Theoretical aspects of reasoning about knowledge, p.171-185, March 1986, Monterey, California, United States
• 15: Michael J. Fischer , Nancy A. Lynch , Michael S. Paterson, Impossibility of distributed consensus with one faulty process, Journal of the ACM (JACM), v.32 n.2, p.374-382, April 1985 [doi>10.1145/3149.214121]
• 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: V. Hadzilacos, A knowledge-theoretic analysis of atomic commitment protocols, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.129-134, March 23-25, 1987, San Diego, California, United States [doi>10.1145/28659.28672]
• 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: 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 [doi>10.1145/323596.323617]
• 21: HALPERN, J. V., MEGIDDO, N., AND MUNSHI, A. Optimal precision in the presence of uncertainty. J. Complexity 1 (1985), 170-196.
• 22: Joseph Y. Halpern , Yoram Moses, Knowledge and common knowledge in a distributed environment, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.50-61, August 27-29, 1984, Vancouver, British Columbia, Canada [doi>10.1145/800222.806735]
• 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: Shmuel Katz , Gadi Taubenfeld, What processes know: Definitions and proof methods, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.249-262, August 11-13, 1986, Calgary, Alberta, Canada [doi>10.1145/10590.10612]
• 27: KOZEN, D. Results on the propositional ~-calculus. Theoret. Comput. Sci. 27, 1 (1983), 333-354.
• 28: R Ladner , J Reif, The logic of distributed protocols, Proceedings of the 1986 Conference on Theoretical aspects of reasoning about knowledge, p.207-222, March 1986, Monterey, California, United States
• 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: Zohar Manna , Pierre Wolper, Synthesis of Communicating Processes from Temporal Logic Specifications, ACM Transactions on Programming Languages and Systems (TOPLAS), v.6 n.1, p.68-93, Jan. 1984 [doi>10.1145/357233.357237]
• 31: Murray S. Mazer, A Knowledge Theoretic Account of Recovery in Distributed Systems: The Case of Negotiated Commitment, Proceedings of the 2nd Conference on Theoretical Aspects of Reasoning about Knowledge, p.309-323, March 01, 1988
• 32: John McCarthy , Masahiko Sato , Takeshi Hayashi , Shigeru Igarashi, On the model theory of knowledge, Stanford University, Stanford, CA, 1978
• 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: Yoram Moses, Resource-bounded Knowledge, Proceedings of the 2nd Conference on Theoretical Aspects of Reasoning about Knowledge, p.261-275, March 01, 1988
• 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: Gil Neiger, Knowledge Consistency: A Useful Suspension of Disbelief, Proceedings of the 2nd Conference on Theoretical Aspects of Reasoning about Knowledge, p.295-308, March 01, 1988
• 38: NF.IGER, G., AND TOUEG, S. Substituting for real time and common knowledge in asynchronous distributed systems. J. A CM.
• 39: Praskash Panangaden , Kim Taylor, Concurrent common knowledge: a new definition of agreement for asynchronous systems, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.197-209, August 15-17, 1988, Toronto, Ontario, Canada [doi>10.1145/62546.62579]
• 40: Rohit Parikh , R. Ramanujam, Distributed Processes and the Logic of Knowledge, Proceedings of the Conference on Logic of Programs, p.256-268, June 17-19, 1985
• 41: S J Rosenschein, Formal theories of knowledge in AI and robotics, New Generation Computing, v.3 n.4, p.345-357, 1985 [doi>10.1007/BF03037076]
• 42: S Rosenschein , L Kaelbling, The synthesis of digital machines with provable epistemic properties, Proceedings of the 1986 Conference on Theoretical aspects of reasoning about knowledge, p.83-98, March 1986, Monterey, California, United States
• 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.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Protocol verification

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

General Terms:
Algorithms, Reliability, Theory, Verification