English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

The $k$-set agreement problem is a generalization of the consensus problem.Namely, assuming each process proposes a value, each non-faulty process has todecide 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 itcannot be solved in asynchronous systems as soon as $k$ or more processes maycrash. One way to circumvent this impossibility consists in weakening itstermination property, requiring that a process terminates (decides) only if itexecutes alone during a long enough period. This is the well-knownobstruction-freedom progress condition. Considering a system of $n$ {\itanonymous asynchronous} processes, which communicate through atomic {\itread/write registers only}, and where {\it any number of processes may crash},this paper addresses and solves the challenging open problem of designing anobstruction-free $k$-set agreement algorithm with $(n-k+1)$ atomic registersonly. From a shared memory cost point of view, this algorithm is the bestalgorithm known so far, thereby establishing a new upper bound on the number ofregisters needed to solve the problem (its gain is $(n-k)$ with respect to theprevious upper bound). The algorithm is then extended to address the repeatedversion of $(n,k)$-set agreement. As it is optimal in the number of atomicread/write registers, this algorithm closes the gap on previously establishedlower/upper bounds for both the anonymous and non-anonymous versions of therepeated $(n,k)$-set agreement problem. Finally, for $1 \leq x\leq k\textless{} n$, a generalization suited to $x$-obstruction-freedom is alsodescribed, which requires $(n-k+x)$ atomic registers only.

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