Skip to Main content Skip to Navigation
Conference papers

(anti-Omega^x × Σ_z) based k-set agreement algorithms

Zohir Bouzid 1 Corentin Travers 2, 3, *
* Corresponding author
1 NPA - Networks and Performance Analysis
LIP6 - Laboratoire d'Informatique de Paris 6
2 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems
IRISA-D1 - SYSTÈMES LARGE ÉCHELLE, Inria Rennes – Bretagne Atlantique
Abstract : This paper considers the k-set agreement problem in a crashprone asynchronous message passing system enriched with failure detectors. Two classes of failure detectors have been previously identified as necessary to solve asynchronous k-set agreement: the class anti-leader anti−Ω k and the weak-quorum class Σk . The paper investigates the families of failure detector (anti−Ω x )1≤x≤n and (Σz )1≤z≤n . It characterizes in an n processes system equipped with failure detectors anti−Ω x and Σz for which values of k, x and z k-set-agreement can be solved. While doing so, the paper (1) disproves previous conjunctures about the weakest failure detector to solve k-set-agreement in the asynchronous message passing model and, (2) introduces the first indulgent algorithm that tolerates a majority of processes failures.
Complete list of metadata

Cited literature [31 references]  Display  Hide  Download

https://hal.inria.fr/hal-00992778
Contributor : Corentin Travers <>
Submitted on : Monday, May 19, 2014 - 11:51:09 AM
Last modification on : Friday, January 8, 2021 - 5:38:04 PM
Long-term archiving on: : Monday, April 10, 2017 - 11:42:49 PM

File

8.pdf
Files produced by the author(s)

Identifiers

Citation

Zohir Bouzid, Corentin Travers. (anti-Omega^x × Σ_z) based k-set agreement algorithms. OPODIS, Dec 2010, Tozeur, Tunisia. pp.189-204, ⟨10.1007/978-3-642-17653-1_16⟩. ⟨hal-00992778⟩

Share

Metrics

Record views

942

Files downloads

203