Skip to Main content Skip to Navigation
Reports

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}$.
Document type :
Reports
Complete list of metadata

https://hal.inria.fr/inria-00000663
Contributor : Anne Jaigu <>
Submitted on : Monday, November 14, 2005 - 9:56:34 AM
Last modification on : Thursday, January 7, 2021 - 4:18:13 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⟩

Share

Metrics

Record views

361

Files downloads

160