HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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 Connect in order to contact the contributor
Submitted on : Friday, March 31, 2006 - 4:24:43 PM
Last modification on : Tuesday, June 15, 2021 - 4:14:21 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