Synchronous condition-based consensus |
| |
Authors: | Achour Mostefaoui Sergio Rajsbaum Michel Raynal |
| |
Affiliation: | (1) IRISA, Campus de Beaulieu, 35042 Rennes Cedex, France;(2) Instituto de Matem′ticas, UNAM, D. F., 04510, Mexico |
| |
Abstract: | 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. |
| |
Keywords: | Consensus Early deciding Input vector Process crash failure Synchronous distributed system |
本文献已被 SpringerLink 等数据库收录! |
|