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

Achour Mostefaoui 1 Michel Raynal 1 Julien Stainer 1
1 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems
Inria Rennes – Bretagne Atlantique , IRISA-D1 - SYSTÈMES LARGE ÉCHELLE
Abstract : 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.
Type de document :
[Research Report] PI-1981, 2011, pp.15
Liste complète des métadonnées

Littérature citée [28 références]  Voir  Masquer  Télécharger
Contributeur : Ist Rennes <>
Soumis le : jeudi 7 juillet 2011 - 15:38:02
Dernière modification le : vendredi 16 novembre 2018 - 01:40:20
Document(s) archivé(s) le : lundi 12 novembre 2012 - 10:23:54


Fichiers produits par l'(les) auteur(s)


  • HAL Id : inria-00606918, version 1


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〉



Consultations de la notice


Téléchargements de fichiers