Synchronous condition-based consensus

The condition-based approach studies restrictions on the inputs to a distributed problem, called conditions, that facilitate its solution. Previous work considered mostly the asynchronous model of computation. This paper studies conditions for consensus in a synchronous system where processes can fail by crashing. It describes a full classification of conditions for consensus, establishing a continuum between the asynchronous and synchronous models, with the following hierarchy where includes all conditions (and in particular the trivial one made up of all possible input vectors). For a condition , we have:

–	For values of consensus is solvable in an asynchronous system with t failures, and we obtain the known hierarchy of conditions that allows solving asynchronous consensus with more and more efficient protocols as we go from d = 0 to d = −t.
–	For values of consensus is solvable in an asynchronous system with t failures, and we obtain the known hierarchy of conditions that allows solving asynchronous consensus with more and more efficient protocols as we go from d = 0 to d = −t.
–	For values of d<0 consensus is known not solvable in an asynchronous system with t failures, but we obtain a hierarchy of conditions that allows solving synchronous consensus with protocols that can take more and more rounds, as we go from d = 0 to d = t.
–	d = 0 is the borderline case where consensus can be solved in an asynchronous system with t failures, and can be solved optimally in a synchronous system.

After having established the complete hierarchy, the paper concentrates on the two last items: . The main result is that the necessary and sufficient number of rounds needed to solve uniform consensus for a condition (such that ) is d +1. In more detail, the paper presents a generic synchronous early-deciding uniform consensus protocol that enjoys the following properties. Let f be the number of actual crashes, I the input vector and the condition the protocol is instantiated with. The protocol terminates in two rounds when and , and in at most d +1 rounds when and . (It also terminates in one round when and .) Moreover, whether I belongs or not to C, no process requires more than min rounds to decide. The paper then proves a corresponding lower bound stating that at least d +1 rounds are necessary to get a decision in the worst case when (for and ). This paper is based on the DISC’03 and DISC’04 conference versions MRR03,MRR04 A. Mostefaoui is currently Associate Professor at the Computer Science Department of the University of Rennes, France. He received his Engineer Degree in Computer Science in 1990 from the University of Algiers, and a Ph.D. in Computer Science in 1994 from the University of Rennes, France. His research interests include fault-tolerance and synchronization in distributed systems, group communication, data consistency and distributed checkpointing. Achour Mostefaoui has published more than 70 scientific publications and served as a reviewer for more than 20 major journals and conferences. Moreover, Achour Mostéfaoui is heading the software engineer degree of the University of Rennes S. Rajsbaum received a degree in Computer Engineering from the National Autonomous University of Mexico (UNAM) in 1985, and a PhD in the Computer Science from the Technion, Israel, in 1991. Since then he has been a member of the Institute of Mathematics at UNAM, where he is now a Full Professor with Tenure. He has been a regular visiting scientist at the Laboratory for Computer Science of MIT. Also, he was a member of the Cambridge Research Laboratory of HP from 2000 to 2002. He was chair of the program committee for Latin American Theoretical Informatics LATIN2002, and for ACM Principles of Distributed Computing PODC03, and member of the Program Committee of various international conferences such as ADHOC, DISC, ICDCS, IPDPS, LADC, PODC, and SIROCCO. His research interests are in the theory of distributed computing, especially issues related to coordination, complexity and computability, and fault-tolerance. He has also published in graph theory and algorithms. Overall, he has published over fifty papers in journals and international conferences. He runs the Distributed Computing Column of SIGACT News, the newsletter of the ACM Special Interest Group on Algorithms and Computation Theory. He has been editor of several special journal issues, such as the Special 20th PODC Anniversary Special Issue of Distributed Computing Journal (with H. Attiya) and of Computer Networks journal special issue on algorithms. M. Raynalhas been a professor of computer science since 1981. At IRISA (CNRS-INRIA-University joint computing research laboratory located in Rennes), he founded a research group on Distributed Algorithms in 1983. His research interests include distributed algorithms, distributed computing systems, networks and dependability. His main interest lies in the fundamental principles that underly the design and the construction of distributed computing systems. He has been Principal Investigator of a number of research grants in these areas, and has been invited by many universities all over the world to give lectures on distributed algorithms and distributed computing. He belongs to the editorial board of several international journals. Professor Michel Raynal has published more than 90 papers in journals (JACM, Acta Informatica, Distributed Computing, Comm. of the ACM, Information and Computation, Journal of Computer and System Sciences, JPDC, IEEE Transactions on Computers, IEEE Transactions on SE, IEEE Transactions on KDE, IEEE Transactions on TPDS, IEEE Computer, IEEE Software, IPL, PPL, Theoretical Computer Science, Real-Time Systems Journal, The Computer Journal, etc.); and more than 190 papers in conferences (ACM STOC, ACM PODC, ACM SPAA, IEEE ICDCS, IEEE DSN, DISC, IEEE IPDPS, Europar, FST&TCS, IEEE SRDS, etc.). He has also written seven books devoted to parallelism, distributed algorithms and systems (MIT Press and Wiley). Michel Raynal has served in program committees for more than 70 international conferences (including ACM PODC, DISC, ICDCS, IPDPS, DSN, LADC, SRDS, SIROCCO, etc.) and chaired the program committee of more than 15 international conferences (including DISC -twice-, ICDCS, SIROCCO and ISORC). He served as the chair of the steering committee leading the DISC symposium series in 2002-2004. Michel Raynal received the IEEE ICDCS best paper Award three times in a row: 1999, 2000 and 2001. He is a general co-chair of the IEEE ICDCS conference that will be held in Lisbon in 2006.