Skip to Main content Skip to Navigation
Reports

Anonymous Obstruction-free $(n,k)$-Set Agreement with $n-k+1$ Atomic Read/Write Registers

Zohir Bouzid 1 Michel Raynal 2 Pierre Sutra 3
1 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems
UR1 - Université de Rennes 1, Inria Saclay - Ile de France, INSA - Institut National des Sciences Appliquées, CNRS - Centre National de la Recherche Scientifique : UMR
2 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 consensus problem. Namely, assuming each process proposes a value, each non-faulty process has to decide a value such that each decided value was proposed, and no more than $k$ different values are decided. This is a hard problem in the sense that it cannot be solved in asynchronous systems as soon as $k$ or more processes may crash. One way to circumvent this impossibility consists in weakening its termination property, requiring that a process terminates (decides) only if it executes alone during a long enough period. This is the well-known obstruction-freedom progress condition. Considering a system of $n$ {\it anonymous asynchronous} processes, which communicate through atomic {\it read/write registers only}, and where {\it any number of processes may crash}, this paper addresses and solves the challenging open problem of designing an obstruction-free $k$-set agreement algorithm with $(n-k+1)$ atomic registers only. From a shared memory cost point of view, this algorithm is the best algorithm known so far, thereby establishing a new upper bound on the number of registers needed to solve the problem (its gain is $(n-k)$ with respect to the previous upper bound). The algorithm is then extended to address the repeated version of $(n,k)$-set agreement. As it is optimal in the number of atomic read/write registers, this algorithm closes the gap on previously established lower/upper bounds for both the anonymous and non-anonymous versions of the repeated $(n,k)$-set agreement problem. Finally, for $1 \leq x\leq k < n$, a generalization suited to $x$-obstruction-freedom is also described, which requires $(n-k+x)$ atomic registers only.
Complete list of metadata

https://hal.inria.fr/hal-01169693
Contributor : Michel Raynal <>
Submitted on : Tuesday, June 30, 2015 - 1:10:03 PM
Last modification on : Friday, April 30, 2021 - 9:58:16 AM
Long-term archiving on: : Tuesday, April 25, 2017 - 8:02:05 PM

Files

RR-2027-V2.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01169693, version 1
  • ARXIV : 1507.00474

Citation

Zohir Bouzid, Michel Raynal, Pierre Sutra. Anonymous Obstruction-free $(n,k)$-Set Agreement with $n-k+1$ Atomic Read/Write Registers. [Research Report] 2027, univzrité de rennes 1. 2015, pp.18. ⟨hal-01169693⟩

Share

Metrics

Record views

1330

Files downloads

179