Skip to Main content Skip to Navigation
Reports

Failure Detectors to Solve Asynchronous k-Set Agreement: a Glimpse of Recent Results

Michel Raynal 1
1 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems
IRISA-D1 - SYSTÈMES LARGE ÉCHELLE, Inria Rennes – Bretagne Atlantique
Abstract : In the k-set agreement problem, each process proposes a value and has to decide a value in such a way that a decided value is a proposed value and at most k different values are decided. This problem can easily be solved in synchronous systems or in asynchronous systems prone to t process crashes when t < k. In contrast, it has been shown that k-set agreement cannot be solved in asynchronous systems when k < t. Hence, since several years, the failure detector-based approach has been investigated to circumvent this impossibility. This approach consists in enriching the underlying asynchronous system with an additional module per process that provides it with information on failures. Hence, without becoming synchronous, the enriched system is no longer fully asynchronous. This paper surveys this approach in both asynchronous shared memory systems and asynchronous message passing systems. It presents and discusses recent results and associated k-set agreement algorithms.
Document type :
Reports
Complete list of metadatas

Cited literature [39 references]  Display  Hide  Download

https://hal.inria.fr/inria-00536089
Contributor : Ist Rennes <>
Submitted on : Monday, November 15, 2010 - 1:08:41 PM
Last modification on : Wednesday, December 18, 2019 - 5:11:02 PM
Long-term archiving on: : Wednesday, February 16, 2011 - 2:53:31 AM

File

PI-1959.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00536089, version 1

Citation

Michel Raynal. Failure Detectors to Solve Asynchronous k-Set Agreement: a Glimpse of Recent Results. [Research Report] PI-1959, 2010. ⟨inria-00536089⟩

Share

Metrics

Record views

699

Files downloads

279