PI-1547: On the Respective Power of diamond P and diamond S to
Solve One-Shot Agreement Problems
Roy Friedman, Achour Mostéfaoui, Michel Raynal
http://www.irisa.fr/bibli/publi/pi/2003/1547/1547.html
20 pages - juillet 2003

Abstract
Unreliable failure detectors are abstract devices that, when added to
asynchronous distributed systems, allow to solve distributed computing
problems (e.g. Consensus) that otherwise would be impossible to solve in
these systems. This paper focuses on two classes of failure detectors
defined by Chandra and Toueg, namely, the classes denoted diamond P
(eventually perfect) and diamond S (eventually strong). Both classes
include failure detectors that eventually detect permanently all process
crashes, but while the failure detectors of diamond P eventually make no
erroneous suspicions, the failure detectors of diamond S are only
required to eventually not suspect a single correct process. In such a
context, this paper addresses the following question related to the
comparative power of these classes, namely: ``Are there one-shot
agreement problems that can be solved in asynchronous distributed
systems with reliable links but prone to process crash failures
augmented with diamond P, but cannot be solved when those systems are
augmented with diamond S?'' Surprisingly, the paper shows that the
answer to this question is ``no''. An important consequence of this
result is that diamond P cannot be the weakest class of failure
detectors that allows to solve one-shot agreement problems in unreliable
asynchronous distributed systems. These results are then extended to the
case of more severe failure modes.

Résumé
Cet article présente une preuve que les détecteurs de défaillances
inéluctables (losange P et losange S) ont la même puissance dès qu'il
s'agit de résoudre des problèmes d'accord (e.g., le consensus). Pour
cela, il définit la notion de nombre véto qui peut être associé à chaque
problème d'accord. Il représente en quelques sorte la difficulté de
celui-ci. Nous avons montré que pour un nombre de défaillances possibles
et un problème ayant un nombre véto donné, soit les détecteurs losange P
et losange S permettent tous les deux de le résoudre soit aucun ne le
peut.

Keywords: Agreement Problem, Asynchronous Distributed System, Consensus,
Computational Power, Input Vector, One-Shot Problem, Process Crash,
Unreliable Failure Detector, diamond P, diamond S

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