2026-09-29T08:21:10Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6609 2026-09-22T20:53:32Z ddc:004 open_access

Anonymous Obstruction-Free (n,k)-Set Agreement with n-k+1 Atomic Read/Write Registers Bouzid, Zohir Raynal, Michel Sutra, Pierre Anonymous processes Asynchronous system Atomic read/write register Consensus Fault-tolerance $k$-Set agreement Obstruction-freedom Upper bound The k-set agreement problem is a generalization of the consensus problem. Namely, assuming that each process proposes a value, every non-faulty process should decide one of the proposed values, and no more than k different values should be decided. This is a hard problem in the sense that we cannot solve it in an asynchronous system, as soon as k or more processes may crash. One way to sidestep this impossibility result consists in weakening the termination property, requiring that a process must decide a value only if it executes alone during a long enough period of time. This is the well-known obstruction-freedom progress condition. Consider a system of n anonymous asynchronous processes that communicate through atomic read/write registers, and such that any number of them may crash. In this paper, we address and solve the challenging open problem of designing an obstruction-free k-set agreement algorithm using only (n-k+1) atomic registers. From a shared memory cost point of view, our algorithm is the best algorithm known so far, thereby establishing a new upper bound on the number of registers needed to solve the problem, and in comparison to the previous upper bound, its gain is (n-k) registers. We then extend this algorithm into a space-optimal solution for the repeated version of k-set agreement, and an x-obstruction-free solution that employs 0(n-k+x) atomic registers (with 1 <= x <= k < n). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Zohir Bouzid and Michel Raynal and Pierre Sutra 2016 Is Part Of LIPIcs, Volume 46, 19th International Conference on Principles of Distributed Systems (OPODIS 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.OPODIS.2015.18 urn:nbn:de:0030-drops-66092 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.18 eng https://creativecommons.org/licenses/by/3.0/legalcode