HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information

# From <>W to Omega: a Simple Bounded Quiescent Reliable broadcast-based Transformation

Abstract : $\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}$.
Mots-clés :
Document type :
Reports

https://hal.inria.fr/inria-00000663
Contributor : Anne Jaigu Connect in order to contact the contributor
Submitted on : Monday, November 14, 2005 - 9:56:34 AM
Last modification on : Tuesday, June 15, 2021 - 4:13:49 PM
Long-term archiving on: : Friday, April 2, 2010 - 7:04:39 PM

### Identifiers

• HAL Id : inria-00000663, version 1

### Citation

Achour Mostefaoui, Sergio Rajsbaum, Michel Raynal, Corentin Travers. From <>W to Omega: a Simple Bounded Quiescent Reliable broadcast-based Transformation. [Research Report] PI 1759, 2005, pp.9. ⟨inria-00000663⟩

Record views