Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation

The Combined Power of Conditions and Information on Failures to Solve Asynchronous Set Agreement

Abstract : To cope with the impossibility of solving agreement problems in asynchronous systems made up of n processes and prone to t process crashes, system designers tailor their algorithms to run fast in “normal” circumstances. Two orthogonal notions of “normality” have been studied in the past through failure detectors that give processes information about process crashes, and through conditions that restrict the inputs to an agreement problem. This paper investigates how the two approaches can benefit from each other to solve the k-set agreement problem, where processes must agree on at most k of their input values (when k = 1 we have the famous consensus problem). It proposes novel failure detectors for solving k-set agreement, and a protocol that combines them with conditions, establishing a new bridge among asynchronous, synchronous and partially synchronous systems with respect to agreement problems. The paper proves also a lower bound when solving the k-set agreement problem with a condition.
Document type :
Complete list of metadata

Cited literature [52 references]  Display  Hide  Download
Contributor : Anne Jaigu Connect in order to contact the contributor
Submitted on : Thursday, July 10, 2008 - 4:32:16 PM
Last modification on : Thursday, January 20, 2022 - 4:20:32 PM
Long-term archiving on: : Friday, May 28, 2010 - 11:22:44 PM


Files produced by the author(s)


  • HAL Id : inria-00294706, version 1


Achour Mostefaoui, Sergio Rajsbaum, Michel Raynal, Corentin Travers. The Combined Power of Conditions and Information on Failures to Solve Asynchronous Set Agreement. [Research Report] PI 1897, 2008, pp.30. ⟨inria-00294706⟩



Record views


Files downloads