2015/07/02 by Zohir Bouzid, Bouzid, Zohir, Michel Raynal +3
Computer Science · Psychology · #Distributed systems and fault tolerance #Optimization and Search Problems #Cognitive Functions and Memory
paper · pdf · doi:10.48550/arxiv.1507.00474
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 ≤ x≤ k \textless n, a generalization suited to x-obstruction-freedom is also described, which requires (n-k+x) atomic registers only.