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

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