# Narrowing power vs efficiency in synchronous set agreement

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
Keywords :
Document type :
Reports
Complete list of metadata

Cited literature [28 references]

https://hal.inria.fr/inria-00139286
Contributor : Anne Jaigu <>
Submitted on : Friday, March 30, 2007 - 10:44:08 AM
Last modification on : Thursday, January 7, 2021 - 4:18:25 PM
Long-term archiving on: : Wednesday, April 7, 2010 - 1:48:08 AM

### Files

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

### Identifiers

• HAL Id : inria-00139286, version 1

### Citation

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