From <>W to Omega: a Simple Bounded Quiescent Reliable broadcast-based Transformation
Résumé
$\Diamond {\cal W}$ is the class of failure detectors that ensure that every crashed process is eventually suspected by a correct process, and eventually there is correct process that is never suspected. $\Omega$ is the class of failure detectors that ensure that eventually all the processes trust the same correct process. This paper presents two algorithms that transform any failure detector of $\Diamond {\cal W}$ into a failure detector of the class $\Omega$. Based on an underlying reliable broadcast facility, these algorithms are quiescent and use message whose size is bounded ($\log_2(n)$ bits and $2 \log_2(n)$, respectively, where $n$ is the number of processes). When we consider the additional cost of implementing the underlying reliable broadcast, they still compare favorably with existing algorithms. From a methodology point of view, it is worth noticing that the use of a reliable broadcast (i.e., a modular approach) allows designing simple and efficient transformations. \\ Ce rapport présente un protocole simple qui construit un détecteur de fautes de la classe Omega à partir de n'importe quel détecteur de fautes de la classe $\Diamond {\cal W}$.