Summary
In this paper we present a new, knowledgetheoretic definition of agreement designed for asynchronous systems. In analogy with common knowledge, it is calledconcurrent common knowledge. Unlike common knowledge, it is a form of agreement that is attainable asynchronously. In defining concurrent common knowledge, we give a logic with new modal operators and a formal semantics, both of which are based on causality and consequently capture only the relevant structure of purely asynchronous systems. We give general conditions by which protocols attain concurrent common knowledge and prove that two simple and efficient protocols do so. We also present several applications of our logic. We show that concurrent common knowledge is a necessary and sufficient condition for the concurrent performance of distributed actions. We also demonstrate the role of knowledge in taking snapshots for stable property detection and asynchronous broadcasts. In general, applications that involve all processes reaching agreement about some porperty of a consistent global state can be understood in terms of concurrent common knowledge.
Similar content being viewed by others
References
Birman K, Joseph T: Reliable communication in the presence of failures. ACM Trans Comp Syst 5(1):47–76 (1987)
Bracha G, Toueg S: Distributed deadlock detection. Distrib Comput 2(3):127–138 (1987)
Chandy M, Lamport L: Finding global states of a distributed system. ACM Trans Comp Syst 3(1):63–75 (1985)
Chandy M, Misra J: How processes learn. Distrib Comput 1(1):40–52 (1986)
Chang EJH: Echo algorithms: depth parallel operations on graphs. IEEE Trans Software Eng SE-8(4):391–400 (1982)
Critchlow C: On inhibition and atomicity in asynchronous consistent-cut protocols. Tech Rep 89-1069, Cornell University Department of Computer Science, 1989
Critchlow C, Taylor K: The inhibition spectrum and the achievement of causal consistency. Proc 9th ACM Symp on Principles of Distributed Computing, pp 31–42 (1990)
Dwork C, Moses Y: Knowledge and common knowledge in a byzantine enbironment: the case of crash failures. In: Halpern J (ed) Proc Conf on Theoretical Aspects of Reasoning About Knowledge. Kaufmann M, 1986, pp. 149–170 (to appear in Inf Comput)
Francez N: Distributed termination. ACM Trans Program Lang Syst 2(1):42–55 (1980)
Halpern JY, Fagin R: Modelling knowledge and action in distributed systems. Distrib Comput 3(4):139–179 (1989)
Halpern JY, Moses Y: Knowledge and common knowledge in a distributed environment. J ACM 37(3):549–587 (1990)
Knaster B: Un théoréme sur les functions d'ensembles. Ann Polish Math Soc 6:133–134 (1928)
Koo R, Toueg S: Checkpointing and rollback-recovery for distributed systems. IEEE Trans Software Eng SE-13(1):23–31 (1987)
Kozen D: Results on the propositional μ-calculus. Theor Comput Sci 27:333–354 (1983)
Lamport L: Paradigms for distributed computing. In: Paul M, Siegert HJ (eds) Methods and tools for specification, an advanced course. Lect Notes Comput Sci, vol 190. Springer, Berlin Heidelberg New York 1985, pp 19–30, 454–468
Lamport L: Time, clocks, and the ordering of events in a distributed system. Commun ACM 21(7):558–565 (1978)
Moses Y, Tuttle M: Programming simultaneous actions using common knowledge. Algorithmica 3:121–169 (1988)
Neiger G, Toueg S: Substituting for real time and common knowledge in asynchronous distributed systems. Proc 6th ACM Symp on Principles of Distributed Computing, pp 281–293, 1987 (to appear in J ACM)
Parikh R, Ramanujam R: Distributed processing and the logic of knowledge. Proc Brooklyn College Workshop on Logics of Programs, pp 256–268 (1985)
Russell DL: Process backup in producer-consumer systems. Proc ACM Symp on Operating Systems Principles (1977)
Tarski A: A lattice-theoretic fixpoint theorem and its applications. Pac J Math 5:285–309 (1955)
Taylor K: The role of inhibition in asynchronous consistent-cut protocols. In: Bermond J-C, Raynal M (eds) Proc 3rd Int Workshop on Distributed Algorithms, Nice, France, September 1989. (Lect Notes Comput Sci, vol 392: Distributed algorithms.) Springer, Berlin Heidelberg New York 1989, pp 280–291
Author information
Authors and Affiliations
Additional information
Prakash Panangaden was born in Pune, India in 1954. He attended Calcutta Boys' School and subsequently attended the Indian Institute of Technology, Kanpur where he received an M.Sc. in Physics in 1975. He went to graduate school at the University of Chicago where he studied relativity. He moved to the University of Wisconsin-Milwaukee to study with Leonard Parker to work on quantum field theory on curved space times. After a post-doc at the University of Utah, he decided that it was time for something completely different. He began a Masters with Robert Keller on the semantics of indeterminate dataflow networks. He became an Assistant professor at Cornell University in 1985 and an Associate Professor at McGill University in 1990. He has also made extended visits to the Computer Laboratory, University of Cambridge and to the C.W.I. Amsterdam.
Kim Taylor has been an assistant professor at the University of California at Santa Cruz since July 1990. Her research interests are in the design and analysis of algorithms for distributed systems. She received the BS degree in Electrical Engineering and Computer Science from Rice University in May 1985, and the PhD in Computer Science from Cornell University in August 1990.
An earlier version of this work appears in Proceedings of the Seventh Annual ACM Symposium on Principles of Distributed Computing, August 1988
Supported in part by NSF grants DCR-8602072 and CCR-8818979.
Supported in part by an AT&T Ph.D. Scholarship.
Rights and permissions
About this article
Cite this article
Panangaden, P., Taylor, K. Concurrent common knowledge: defining agreement for asynchronous systems. Distrib Comput 6, 73���93 (1992). https://doi.org/10.1007/BF02252679
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/BF02252679