Anonymous obstruction-free (n,k)-set agreement with n−k+1 atomic read/write registers
Résumé
The k-set agreement problem is a generalization of the consensus problem. Namely, assuming that each pro- cess proposes a value, every non-faulty process must decide one of the proposed values, under the constraint that at most k different values are decided. This is a hard problem in the sense that it cannot be solved in a pure read/write asyn- chronous system, in which k or more processes may crash. One way to sidestep this impossibility result consists in weak- ening the termination property, requiring only that a process decides 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 reg- isters, and such that any number of them may crash. This paper addresses and solves the challenging open problem of designing an obstruction-free k-set agreement algorithm with only (n −k +1) atomic registers. From a shared memory cost point of view, our algorithm is the best algorithm known to date, thereby establishing a new upper bound on the number of registers needed to solve this problem. For the consensus case (k = 1), the proposed algorithm is up to an additive factor of 1 close to the best known lower bound. Further, the paper extends this algorithm to obtain an x-obstruction- free solution to the k-set agreement problem that employs (n − k + x) atomic registers (with 1 ≤ x ≤ k < n), as well as a space-optimal solution for the repeated ver- sion of k-set agreement. Using this last extension, we prove that n registers are enough for every colorless task that is obstruction-free solvable with identifiers and any number of registers
Origine : Fichiers produits par l'(les) auteur(s)
Loading...