Chasing the Weakest Failure Detector for k-Set Agreement in Message-passing Systems - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2011

Chasing the Weakest Failure Detector for k-Set Agreement in Message-passing Systems

Résumé

This paper continues our quest for the weakest failure detector which allows the k-set agreement problem to be solved in asynchronous message-passing systems prone to any number of process failures. It has two main contributions which (we hope) will be instrumental to complete this quest. The first contribution is a new failure detector (denoted ∏∑x,y). This failure detector has several noteworthy properties. (a) It is stronger than ∑x which has been shown to be necessary. (b) It is equivalent to the pair (∑, Ω) when x = y = 1 (from which it follows that ∏∑1,1 is optimal to solve consensus). (c) It is equivalent to the pair (∑n−1, Ωn−1) when x = y = n − 1 (from which it follows that ∏∑n−1, n−1) is optimal for (n − 1)-set agreement). (d) It is strictly weaker than the pair (∑x,Ωy) (which has been investigated in previous works) for the pairs (x, y) such that 1 < y < x < n. (e) It is operational: the paper presents a ∏∑x,y-based algorithm that solves k-set agreement for k ⩾ xy. The second contribution of the paper is a proof that, for 1 < k < n − 1, the eventual leaders failure detector k (which eventually provides each process with the same set of k process identities, this set including at least one correct process) is not necessary to solve k-set agreement problem. More precisely, the paper shows that the weakest failure detector for k-set agreement and k cannot be compared.
Fichier principal
Vignette du fichier
PI-1981-1.pdf (292.53 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00606918 , version 1 (07-07-2011)

Identifiants

  • HAL Id : inria-00606918 , version 1

Citer

Achour Mostefaoui, Michel Raynal, Julien Stainer. Chasing the Weakest Failure Detector for k-Set Agreement in Message-passing Systems. [Research Report] PI-1981, 2011, pp.15. ⟨inria-00606918⟩
153 Consultations
300 Téléchargements

Partager

Gmail Facebook X LinkedIn More