Continuous consensus via common knowledge |
| |
Authors: | Tal Mizrahi Yoram Moses |
| |
Affiliation: | (1) Department of Electrical Engineering, Technion, Haifa, 32000, Israel |
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|