Looking for the Weakest Failure Detector for $k$-Set Agreement in Message-passing Systems: Is $\Pi_k$ the End of the Road?

François Bonnet 1 Michel Raynal 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 : In the $k$-set agreement problem, each process (in a set of $n$ processes) proposes a value and has to decide a proposed value in such a way that at most $k$ different values are decided. While this problem can easily be solved in asynchronous systems prone to $t$ process crashes when $k>t$, it cannot be solved when $k\leq t$. Since several years, the failure detector-based approach has been investigated to circumvent this impossibility. While the weakest failure detector class to solve the $k$-set agreement problem in read/write shared-memory systems has recently been discovered (PODC 2009), the situation is different in message-passing systems where the weakest failure detector classes are known only for the extreme cases $k=1$ (consensus) and $k=n-1$ (set agreement). This paper introduces a candidate for the general case. It presents a new failure detector class, denoted $\Pi_k$, and shows $\Pi_1=\Sigma\times \Omega$ (the weakest class for $k=1$), and $\Pi_{n-1}={\cal L}$ (the weakest class for $k=n-1$). Then, the paper investigates the structure of $\Pi_k$ and shows it is the combination of two failures detector classes denoted $\Sigma_k$ and $\Omega_k$ (that generalize the previous ``quorums'' and ``eventual leaders'' failure detectors classes). Finally, the paper proves that $\Sigma_k$ is a necessary requirement (as far as information on failure is concerned) to solve the $k$-set agreement problem in message-passing systems. The paper presents also a $\Pi_{n-1}$-based algorithm that solves the $(n-1)$-set agreement problem. This algorithm provides us with a new algorithmic insight on the way the $(n-1)$-set agreeement problem can be solved in asynchronous message-passing systems (insight from the point of view of the non-partitioning constraint defined by $\Sigma_{n-1}$).
Type de document :
[Research Report] PI 1929, 2009, pp.13
Liste complète des métadonnées

Littérature citée [26 références]  Voir  Masquer  Télécharger

Contributeur : Anne Jaigu <>
Soumis le : lundi 18 mai 2009 - 10:04:54
Dernière modification le : mercredi 28 février 2018 - 10:22:57
Document(s) archivé(s) le : jeudi 10 juin 2010 - 23:19:48


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


  • HAL Id : inria-00384993, version 1



François Bonnet, Michel Raynal. Looking for the Weakest Failure Detector for $k$-Set Agreement in Message-passing Systems: Is $\Pi_k$ the End of the Road?. [Research Report] PI 1929, 2009, pp.13. 〈inria-00384993〉



Consultations de la notice


Téléchargements de fichiers