PI-1583: Building and Using Pt-Based Quorums Despite any Number t
of Process of Crashes
Roy Friedman, Achour Mostefaoui, Michel Raynal
http://www.irisa.fr/bibli/publi/pi/2003/1583/1583.html
16 pages - décembre 2003

Abstract
Failure detectors of the class denoted Pt eventually suspect all crashed
processes in a permanent way (completeness) and ensure that, at any
time, no more than n-t-1 alive processes are falsely suspected
(accuracy), n being the total number of processes. This paper shows that
a simple combination of such a failure detector with a two-step
communication pattern can provide the processes with an interesting
intersection property on sets of values. As an example illustrating the
benefit and the property that such a combination can provide when
designing protocols, a leader-based consensus protocol whose design
relies on its systematic use is presented.

Résumé
Cet article présente une manière simple de construire et d'utiliser des
quorums qui satisfont des propriétés d'intersection sur les ensembles de
valeurs collectées et ce en dépit d'un nombre quelconque de défaillances
de processus. Pour cela, il est fait usage d'un détecteur de
défaillances de la classe Pt. Il est prouvé qu'il est nécessaire et
suffisant que l'échange de messages qui met en oeuvre la construction du
quorum soit en deux étapes de communication. La seconde partie de cet
article montre comment un tel quorum peut être utilisé pour concevoir un
algorithme de résolution du consensus fondé sur une combinaison des
détecteurs de la classe Pt et de la classe W.

Keywords: Asynchronous distributed system, Consensus, Distributed
algorithm, Fault tolerance, Leader oracle, Quorum, Process crash,
Unreliable failure detector

Mots clefs: Problème d'accord, système asynchrone, consensus,
défaillance de processus, détecteur de défaillances non fiable, quorum