Continuous consensus via common knowledge

This paper introduces the continuous consensus problem, in which a core Mk] of information is continuously maintained at all correct sites of the system. All local copies of the core must be identical at all times k, and every interesting event should eventually enter the core. The continuous consensus problem is studied in synchronous systems with crash and omission failures, assuming an upper bound of t on the number of failures in any given run of the system. A simple protocol for continuous consensus, called ConCon, is presented. This protocol is knowledge-based: The actions processes take depend explicitly on their knowledge, as well as on their knowledge of what other processes know about failures and about events that occurred in the system. A close connection between continuous consensus and knowledge is established by showing that in every continuous consensus protocol, the information in the core at any given time must be common knowledge. Based on the characterization of common knowledge by Moses and Tuttle, it is shown that ConCon is an optimum protocol for continuous consensus, maintaining the most up-to-date core possible at all times: For every pattern of failures and external inputs and each point in time, the core provided by ConCon contains the cores of all correct protocols for continuous consensus. Indeed, the ConCon protocol can be viewed as a simplification of the Moses and Tuttle construction for computing the common knowledge at a given point. Finally, a uniform version of continuous consensus is considered, in which all processes (faulty and nonfaulty) are guaranteed to maintain the same core at any given time. An algorithm for uniform continuous consensus is presented, and is also shown to be an optimum solution. A preliminary version of this paper appeared in the Proceedings of the TARK X conference, Singapore 2005. Work on this paper was performed in part during a sabbatical at the School of Computer Science and Engineering, The University of New South Wales, Sydney, NSW 2052, Australia, where it was partially supported by ARC Discovery Grant RM02036.