Exploring Gafni's reduction land: from $\Omega^k$ to wait-free adaptive $(2p-\lceil\frac{p}{k}\rceil)$-renaming via $k$-set agreement

The adaptive renaming problem consists in designing an algorithm that allows $p$ processes (in a set of $n$ processes) to obtain new names despite asynchrony and process crashes, in such a way that the size of the new renaming space $M$ be as small as possible. It has been shown that $M=2p-1$ is a lower bound for that problem in asynchronous atomic read/write register systems. This paper is an attempt to circumvent that lower bound. To that end, considering first that the system is provided with a $k$-set object, the paper presents a surprisingly simple adaptive $M$-renaming wait-free algorithm where $M=2p-\lceil\frac{p}{k}\rceil$. To attain this goal, the paper visits what we call Gafni's reduction land, namely, a set of reductions from one object to another object as advocated and investigated by Gafni. Then, the paper shows how a $k$-set object can be implemented from a leader oracle (failure detector) of the class $\Omega^k$. To our knowledge, this is the first time that the failure detector approach is investigated to circumvent the $M=2p-1$ lower bound associated with the adaptive renaming problem. In that sense, the paper establishes a connection between renaming and failure detectors. \\ Ce rapport présente un protocole qui permet de renommer les processus en présence de fautes dans un espace de $M= (2p-\lceil\frac{p}{k}\rceil)$ noms (où $p$ est le nombre de processus qui participent à l'algorithme). Ce protocole est fondé sur un détecteur de fautes de la classe $\Omega^k$