Anne Jaigu
07-25-2004, 02:49 AM
PI-1584: The Synchronous Condition-Based Consensus Hierarchy
Achour Mostefaoui, Sergio Rajsbaum, Michel Raynal
http://www.irisa.fr/bibli/publi/pi/2003/1584/1584.html
26 pages - décembre 2003
Abstract
The condition-based approach studies restrictions on the inputs to a
distributed problem, called conditions, for which it is possible to
design more efficient solutions. Previous work studied conditions for
consensus and other agreement problems in an asynchronous system. Only
recently, conditions for consensus in a synchronous system where at most
t processes can crash started to be considered. This paper extends these
results. It studies a full classification of conditions for consensus,
establishing a continuum between the asynchronous and synchronous
models, with the following hierarchy St[-t]Ì···Ì St[0]Ì···Ì St[t] where
St[t] includes all conditions (and in particular the trivial one made up
of all possible input vectors). For a condition C Î St[d], -t £ d £ t,
we have:
- For values of d £ 0 consensus is solvable in an asynchronous system
with t failures, and we get the hierarchy of conditions (we introduced
in PODC'01) that allows to solve asynchronous consensus with more and
more efficient protocols as we go from d=0 to d=-t.
- For values of d>0 consensus is not solvable in an asynchronous system
with t failures, but we get the hierarchy of conditions that allows to
solve synchronous consensus with protocols that take more and more
rounds, as we go from d=0 to d=t.
- d=0 is the borderline case where consensus is solvable in an
asynchronous system with t failures, and optimally in a synchronous
system.
Our main results are for the second item, d>0. A generic synchronous
early-deciding uniform consensus protocol that, when instantiated with a
condition C Î St[d], processes decide in at most min(a+1,f+2,t+1), where
f is the number of actual crashes, and a=d if the input vector I belongs
to C, or a=+¥ otherwise. A corresponding lower bound stating that at
least d rounds are necessary to get a decision.
Résumé
Ce rapport investigue l'approche fondée sur les conditions pour
accélérer le consensus dans les systèmes synchrones.
Keywords: Condition, Consensus, Early deciding, Input Vector,
Message-passing, Process crash failure, Synchronous distributed system
Mots clefs: Condition, Consensus, Crash de processus, Message, Motif
d'entrée, Système synchrone
Achour Mostefaoui, Sergio Rajsbaum, Michel Raynal
http://www.irisa.fr/bibli/publi/pi/2003/1584/1584.html
26 pages - décembre 2003
Abstract
The condition-based approach studies restrictions on the inputs to a
distributed problem, called conditions, for which it is possible to
design more efficient solutions. Previous work studied conditions for
consensus and other agreement problems in an asynchronous system. Only
recently, conditions for consensus in a synchronous system where at most
t processes can crash started to be considered. This paper extends these
results. It studies a full classification of conditions for consensus,
establishing a continuum between the asynchronous and synchronous
models, with the following hierarchy St[-t]Ì···Ì St[0]Ì···Ì St[t] where
St[t] includes all conditions (and in particular the trivial one made up
of all possible input vectors). For a condition C Î St[d], -t £ d £ t,
we have:
- For values of d £ 0 consensus is solvable in an asynchronous system
with t failures, and we get the hierarchy of conditions (we introduced
in PODC'01) that allows to solve asynchronous consensus with more and
more efficient protocols as we go from d=0 to d=-t.
- For values of d>0 consensus is not solvable in an asynchronous system
with t failures, but we get the hierarchy of conditions that allows to
solve synchronous consensus with protocols that take more and more
rounds, as we go from d=0 to d=t.
- d=0 is the borderline case where consensus is solvable in an
asynchronous system with t failures, and optimally in a synchronous
system.
Our main results are for the second item, d>0. A generic synchronous
early-deciding uniform consensus protocol that, when instantiated with a
condition C Î St[d], processes decide in at most min(a+1,f+2,t+1), where
f is the number of actual crashes, and a=d if the input vector I belongs
to C, or a=+¥ otherwise. A corresponding lower bound stating that at
least d rounds are necessary to get a decision.
Résumé
Ce rapport investigue l'approche fondée sur les conditions pour
accélérer le consensus dans les systèmes synchrones.
Keywords: Condition, Consensus, Early deciding, Input Vector,
Message-passing, Process crash failure, Synchronous distributed system
Mots clefs: Condition, Consensus, Crash de processus, Message, Motif
d'entrée, Système synchrone