# en fr Anonymous Obstruction-free $n,k$-Set Agreement with $n-k 1$ Atomic Read-Write Registers Accord $k$-ensembliste asynchrone et anonyme avec $n-k 1$ registres atomiques

en fr Anonymous Obstruction-free $n,k$-Set Agreement with $n-k 1$ Atomic Read-Write Registers Accord $k$-ensembliste asynchrone et anonyme avec $n-k 1$ registres atomiques - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 NPA - Networks and Performance Analysis LIP6 - Laboratoire d-Informatique de Paris 6 2 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems Inria Rennes – Bretagne Atlantique , IRISA-D1 - SYSTÈMES LARGE ÉCHELLE 3 Université de Neuchâtel

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 thatit 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 numberof 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 boundsfor 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.

Résumé : Cet article préente un algorithme asynchrone qui résoud l-accord k-ensenbliste dans un système de n processus asynchrones et anonymes communiquant via $n-k+1$ registres atomiques du type lire-écrire, et dans lequel un nombre quelconque d-entre eux peut s-arrêterde façon inopinée crash failure. La propriété de vivacité garantie par l-algorithme est appelée -obstruction-freedom-.

Keywords : Upper bound Repeated k-set agreement Process crash Consensus Bounded number of registers Distributed algorithm Atomic read-write register Asynchronous system Key-words: Anonymous processes Distributed computability k-Set agreement Obstruction-freedom Fault-tolerance

Autor: Zohir Bouzid - Michel Raynal - Pierre Sutra -

Fuente: https://hal.archives-ouvertes.fr/

DESCARGAR PDF