A formal model of knowledge, action, and communication in distributed systems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A formal model of knowledge, action, and communication in distributed systems: preliminary report

Full text

Pdf (1.31 MB)

Source

Annual ACM Symposium on Principles of Distributed Computing archive
Proceedings of the fourth annual ACM symposium on Principles of distributed computing table of contents

Minaki, Ontario, Canada

Pages: 224 - 236

Year of Publication: 1985

ISBN:0-89791-168-7

Authors

Joseph Y. Halpern	IBM Research Laboratory, San Jose, CA
Ronald Fagin	IBM Research Laboratory, San Jose, CA

Sponsors

SIGOPS: ACM Special Interest Group on Operating Systems
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 27, Citation Count: 40

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/323596.323617 What is a DOI?

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.

	BS	N.D. Belnap and T.B. Steel, The Logic of Questions and Answers, Yale University Press, 1976.
	CM	K. Mani Chandy , Jayadev Misra, How processes learn, Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.204-214, August 1985, Minaki, Ontario, Canada [doi>10.1145/323596.323615]
	DHS	Danny Dolev , Joe Halpern , H. Raymond Strong, On the possibility and impossibility of achieving clock synchronization, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.504-511, December 1984 [doi>10.1145/800057.808720]
	Dw	Cynthia Dwork, Bounds on fundamental problems in parallel and distributed computation, 1983
	DFIL	C. Dwork, M.J. Fischer, N. Immerman, and N.A. Lynch, A theory of protocols, unpublished note, 1984.
	FLM	Michael J. Fischer , Nancy A. Lynch , Michael Merritt, Easy impossibility proofs for distributed consensus problems, Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.59-70, August 1985, Minaki, Ontario, Canada [doi>10.1145/323596.323602]
	Gr	J. Gray, Notes on database operating systems, IBM Research Report RJ 2188, 1978.
	GS	J. Groenendijk and M. Stokhof, Studies on the semantics of questions and the pragmatics of answers, Ph.D. Thesis, U. of Amsterdam, 1984.
	HM1	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]
	HM2	J.Y. Halpern and Y.O. Moses, A guide to the modal logics of knowledge and belief, to appear in Proceedings of the International Joint Conference on Artificial Intelligenc, (IJCAI.85), 1985.
	Ka	H.W. Kamp, Tense logic and the theory of linear order, Ph.D. thesis, U.C.L.A., 1968.
	Leh1	Daniel Lehmann, Knowledge, common knowledge and related puzzles (Extended Summary), Proceedings of the third annual ACM symposium on Principles of distributed computing, p.62-67, August 27-29, 1984, Vancouver, British Columbia, Canada [doi>10.1145/800222.806736]
	Leh2	D.J. Lehmann, private communication.
	Lev	H.J. Levesque, A formal treatment of incomplete knowledge bases, Fairchild Technical Report 614, FLAIR Technical Report 3, 1982.
	Mo	R.C. Moore, Reasoning about knowledge and action, Artificial Intelligence Center Technical Note 191, SRI International, 1980.
	MDH	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 [doi>10.1145/323596.323616]
	PR	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
	PSL	M. Pease , R. Shostak , L. Lamport, Reaching Agreement in the Presence of Faults, Journal of the ACM (JACM), v.27 n.2, p.228-234, April 1980 [doi>10.1145/322186.322188]
	RP	S. Rosenschein and F. Pereira, Knowledge and action in situated automata, unpublished manuscript, 1985.
	Sa	M. Sato, A study of Kripke-style methods of some modal logics by Gentzen's sequential method, Publications of the Research Institute for Mathematical Sciences, K3oto University, 13:2, 1977.
	Sm	R. Smullyan, What is the Name of This Book?, Prentice-Hall, 1978.
	SD	H.R. Strong and D. Dolev, Byzantine agreement, IBM Research Report RJ 3714, 1982.

CITED BY 40

	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
	R. Michel, A categorical approach to distributed systems expressibility and knowledge, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.129-143, June 1989, Edmonton, Alberta, Canada
	Joseph Halpern , Vardi, Reasoning about knowledge and time in asynchronous systems, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.53-65, May 02-04, 1988, Chicago, Illinois, United States
	Michael Merritt , Gadi Taubenfeld, Knowledge in shared memory systems (preliminary version), Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.189-200, August 19-21, 1991, Montreal, Quebec, Canada
	Ching Tsun Chou , Eli Gafni, Understanding and verifying distributed algorithms using stratified decomposition, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.44-65, August 15-17, 1988, Toronto, 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
	Brendan Machado , K. M. George, A model for multiparadigm systems, Proceedings of the 19th annual conference on Computer Science, p.221-227, April 1991, San Antonio, Texas, United States
	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
	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
	Gil Neiger , Sam Toueg, Substituting for real time and common knowledge in asynchronous distributed systems, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.281-293, August 10-12, 1987, Vancouver, British Columbia, Canada
	Ronald Fagin , Yoram Moses , Joseph Y. Halpern , Moshe Y. Vardi, Knowledge-based programs, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.153-163, August 20-23, 1995, Ottowa, Ontario, Canada
	Joseph Y. Halpern, A little knowledge goes a long way: simple knowledge-based derivations and correctness proofs for a family of protocols, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.269-280, August 10-12, 1987, Vancouver, British Columbia, Canada
	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
	J Y Halpern , M Y Vardi, The complexity of reasoning about knowledge and time, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.304-315, May 28-30, 1986, Berkeley, California, United States
	Joseph Y. Halpern , Lenore D. Zuck, A little knowledge goes a long way: knowledge-based derivations and correctness proofs for a family of protocols, Journal of the ACM (JACM), v.39 n.3, p.449-478, July 1992
	Joseph Y. Halpern , Yoram Moses, Knowledge and common knowledge in a distributed environment, Journal of the ACM (JACM), v.37 n.3, p.549-587, July 1990
	Michael J. Fischer , Neil Immerman, Foundations of knowledge for distributed systems, Proceedings of the 1986 conference on Theoretical aspects of reasoning about knowledge, March 19-22, 1986, Monterey, California
	Aleta Ricciardi , Paul Grisham, Toward sofware synthesis for distributed applications, Proceedings of the 7th conference on Theoretical aspects of rationality and knowledge, July 22-24, 1998, Evanston, Illinois
	Rohit Parikh , Ramaswamy Ramanujam, A Knowledge Based Semantics of Messages, Journal of Logic, Language and Information, v.12 n.4, p.453-467, Fall 2003
	Timothy Porter, Interpreted systems and Kripke models for multiagent systems from a categorical perspective, Theoretical Computer Science, v.323 n.1-3, p.235-266, 14 September 2004
	Joseph Y. Halpern, Reasoning about knowledge: a tutorial, Proceedings of the 2nd conference on Theoretical aspects of reasoning about knowledge, March 07-09, 1988, Pacific Grove, California
	Aleta M. Ricciardi, Practical utility of knowledge-based analyses: optimizations and optimality for an implementation of asynchronous, fail-stop processes (extended abstract), Proceedings of the 4th conference on Theoretical aspects of reasoning about knowledge, p.15-28, March 22-25, 1992, Monterey, California
	Ronald Fagin , Joseph Y. Halpern , Yoram Moses , Moshe Y. Vardi, Knowledge-based programs, Distributed Computing, v.10 n.4, p.199-225, July 1997
	Ronald Fagin , Joseph Y. Halpern , Yoram Moses , Moshe Y. Vardi, Knowledge-based programs, Distributed Computing, v.10 n.4, p.199-225, July 1997
	Richard E. Ladner , John H. Reif, The logic of distributed protocols: preliminary report, Proceedings of the 1986 conference on Theoretical aspects of reasoning about knowledge, March 19-22, 1986, Monterey, California
	Joseph Y. Halpern , Yoram Moses, Using counterfactuals in knowledge-based programming, Distributed Computing, v.17 n.2, p.91-106, August 2004
	Moshe Y. Vardi, Implementing knowledge-based programs, Proceedings of the 6th conference on Theoretical aspects of rationality and knowledge, March 17-20, 1996, The Netherlands
	Joseph Y. Halpern, A note on knowledge-based programs and specifications, Distributed Computing, v.13 n.3, p.145-153, July 2000
	Joseph Y. Halpern, On ambiguities in the interpretation of game trees, Proceedings of the 6th conference on Theoretical aspects of rationality and knowledge, March 17-20, 1996, The Netherlands
	Deborah Shands , Chung-Kuo Chang, Characterizing distributed systems using knowledge-based models: preliminary version, Proceedings of the 4th conference on Theoretical aspects of reasoning about knowledge, p.29-42, March 22-25, 1992, Monterey, California
	Joseph Y. Halpern , Yoram Moses, Using counterfactuals in knowledge-based programming, Proceedings of the 7th conference on Theoretical aspects of rationality and knowledge, July 22-24, 1998, Evanston, Illinois
	Michael Merritt , Gadi Taubenfeld, Knowledge in shared memory systems, Distributed Computing, v.7 n.2, p.99-109, December 1993
	Gil Neiger, Knowledge consistency: a useful suspension of disbelief, Proceedings of the 2nd conference on Theoretical aspects of reasoning about knowledge, March 07-09, 1988, Pacific Grove, California
	Yoram Moses, Resource-bounded knowledge, Proceedings of the 2nd conference on Theoretical aspects of reasoning about knowledge, March 07-09, 1988, Pacific Grove, California
	Rohit Parikh, Logical omniscience and common knowledge: WHAT do we know and what do WE know?, Proceedings of the 10th conference on Theoretical aspects of rationality and knowledge, June 10-12, 2005, Singapore
	Ronald Fagin , Moshe Y. Vardi, Knowledge and implicit knowledge in a distributed environment: preliminary report, Proceedings of the 1986 conference on Theoretical aspects of reasoning about knowledge, March 19-22, 1986, Monterey, California
	Joseph Y. Halpern, Reasoning about knowledge: an overview, Proceedings of the 1986 conference on Theoretical aspects of reasoning about knowledge, March 19-22, 1986, Monterey, California
	Yoram Moses, Knowledge and communication: a tutorial, Proceedings of the 4th conference on Theoretical aspects of reasoning about knowledge, p.1-14, March 22-25, 1992, Monterey, California
	Reino Kurki-Suonio, Towards programming with knowledge expressions, Proceedings of the 13th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.140-149, January 01, 1986, St. Petersburg Beach, Florida
	Nir Friedman , Joseph Y. Halpern, Belief Revision: A Critique, Journal of Logic, Language and Information, v.8 n.4, p.401-420, October 1999