Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell Computing and Information Science
  3. Computer Science
  4. Computer Science Technical Reports
  5. Concurrent Common Knowledge: A New Definition of Agreement for Asynchronous Systems

Concurrent Common Knowledge: A New Definition of Agreement for Asynchronous Systems

File(s)
89-1011.ps (806.78 KB)
89-1011.pdf (4.22 MB)
Permanent Link(s)
https://hdl.handle.net/1813/6811
Collections
Computer Science Technical Reports
Author
Panangaden, Prakash
Taylor, Kimberly E.
Abstract

In this paper we discuss a new, knowledge-theoretic definition of agreement appropriate to asynchronous systems. This definition has two important features: first, it uses causality, rather than time, in its definition and, second, this form of agreement is attainable. In analogy with common knowledge, it is called concurrent common knowledge. In defining concurrent common knowledge we give a logic with new model operators and a 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 can attain concurrent common knowledge and prove that two simple and efficient algorithms do so. We also present several applications of our logic, including necessary and sufficient local preconditions for the concurrent performance of distributed actions. In general, applications that involve all processes reaching agreement about some property of a consistent global state are protocols that use concurrent common knowledge.

Date Issued
1989-05
Publisher
Cornell University
Keywords
computer science
•
technical report
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR89-1011
Type
technical report

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance