Skip to Main content Skip to Navigation

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

Abstract : 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$.
Document type :
Complete list of metadata

Cited literature [21 references]  Display  Hide  Download
Contributor : Anne Jaigu <>
Submitted on : Friday, March 31, 2006 - 4:24:43 PM
Last modification on : Thursday, January 7, 2021 - 4:18:14 PM
Long-term archiving on: : Saturday, April 3, 2010 - 11:05:15 PM


  • HAL Id : inria-00001189, version 1


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⟩



Record views


Files downloads