Skip to Main content Skip to Navigation

Narrowing power vs efficiency in synchronous set agreement

Achour Mostefaoui 1 Michel Raynal 1 Corentin Travers 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 : The $k$-set agreement problem is a generalization of the uniform consensus problem: each process proposes a value, and each non-faulty process has to decide a value such that a decided value is a proposed value, and at most $k$ different values are decided. It has been shown that any algorithm that solves the $k$-set agreement problem in synchronous systems that can suffer up to $t$ crash failures requires $\lfloor \frac{t}{k} \rfloor +1$ rounds in the worst case. It has also been shown that it is possible to design early deciding algorithms where no process decides and halts after $\min\big( \lfloor \frac{f}{k} \rfloor +2, \lfloor \frac{t}{k} \rfloor +1\big)$ rounds, where $f$ is the number of actual crashes in a run ($0\leq f\leq t$). This paper explores a new direction to solve the $k$-set agreement problemin a synchronous system. It considers that the system is enriched with base objects (denoted $[m,\ell]$\_SA objects) that allow solving the $\ell$-set agreement problem in a set of $m$ processes ($m
Document type :
Complete list of metadata

Cited literature [28 references]  Display  Hide  Download
Contributor : Anne Jaigu Connect in order to contact the contributor
Submitted on : Friday, March 30, 2007 - 10:44:08 AM
Last modification on : Thursday, January 20, 2022 - 4:20:25 PM
Long-term archiving on: : Wednesday, April 7, 2010 - 1:48:08 AM


Files produced by the author(s)


  • HAL Id : inria-00139286, version 1


Achour Mostefaoui, Michel Raynal, Corentin Travers. Narrowing power vs efficiency in synchronous set agreement. [Research Report] PI 1836, 2007, pp.13. ⟨inria-00139286⟩



Record views


Files downloads