PI-1557: A Weakest Failure Detector-Based Asynchronous Consensus
Protocol for f<n
Roy Friedman, Achour Mostéfaoui, Michel Raynal
http://www.irisa.fr/bibli/publi/pi/2003/1557/1557.html
11 pages - septembre 2003

Abstract
"Pf × diamond S" has been shown to be the weakest realistic failure
detector class needed to solve the consensus problem in an asynchronous
distributed system prone to f < n process crashes in which communication
is by message-passing. However, the only protocol that is know to meet
this bound is based on three layers of protocols construction, and is
therefore not efficient. This paper presents a surprisingly simple and
very efficient direct message-passing implementation of a consensus
protocol based on this optimal failure detector, and proves its
correctness.

Résumé
La classe de détecteurs de défaillances notée "Pf × losange S"
(introduite par Delporte-Gallet, Fauconnier et Guerraoui) est la plus
faible classe de détecteurs qui permette de résoudre le problème du
consensus dans les systèmes répartis asynchrones dans lesquels f
processus parmi les n qui composent le sytème peuvent crasher (f<n). Ce
rapport présente un protocole de consensus uniforme pour les systèmes
répartis asynchrones équipés d'un détecteur de défaillances de cette
classe. Ce protocole est particulèrement simple et efficace. Lorsqu'il
n'y a ni crash, ni fausse suspicion, trois étapes de communication sont
suffisantes pour permettre aux processus de décider.

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

Mots clefs: Système réparti asynchrone, Consensus, Crash, Détecteur de
défaillances, Tolérance aux fautes