Skip to Main content Skip to Navigation

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

Cited literature [26 references]  Display  Hide  Download
Contributor : Anne Jaigu Connect in order to contact the contributor
Submitted on : Monday, May 18, 2009 - 10:04:54 AM
Last modification on : Thursday, January 20, 2022 - 4:19:59 PM
Long-term archiving on: : Thursday, June 10, 2010 - 11:19:48 PM


Files produced by the author(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⟩



Record views


Files downloads