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

Achour Mostefaoui (1) , Michel Raynal (1) , Corentin Travers (1)

1 IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires

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$.

Mots clés: Adaptive algorithm; Asynchronous system; Atomic register; Consensus; Divide and conquer; Leader oracle; Renaming; Set agreement; Shared object; Wait-free algorithm \\ Algorithme adaptatif; Algorithme sans attente; Registre atomique; Renommage; Tolérance aux fautes; Accord ensembliste; Crash de processus; Détecteur de fautes; Leader; Réduction

Domaines: Performance et fiabilité [cs.PF]

Achour Mostefaoui, Michel Raynal, Corentin Travers. Exploring Gafni's reduction land: from $\Omega^k$ to wait-free adaptive $(2p-\lceil\frac{p}{k}\rceil)$-renaming via $k$-set agreement. [Research Report] PI 1794, 2006, pp.19. ⟨inria-00001189⟩