Skip to Main content Skip to Navigation

The Renaming Problem in Shared Memory Systems: an Introduction

Abstract : Exploring the power of shared memory communication objects and models, and the limits of distributed computability are among the most exciting research areas of distributed computing. In that spirit, this paper focuses on a problem that has received considerable interest since its introduction in 1987, namely the renaming problem. It was the rst non-trivial problem known to be solvable in an asynchronous distributed system despite process failures. Many algorithms for renaming and variants of renaming have been proposed, and sophisticated lower bounds have been proved, that have been a source of new ideas of general interest to distributed computing. It has consequently acquired a paradigm status in distributed fault-tolerant computing. In the renaming problem, processes start with unique initial names taken from a large name space and decide new names such that no two processes decide the same new name and the new names are from a name space as small as possible. This paper presents an introduction to the renaming problem in shared memory systems, for non-expert readers. It describes both algorithms and lower bounds. Also, it discusses strong connections relating renaming and other important distributed problems such as set agreement and symmetry breaking.
Document type :
Complete list of metadata

Cited literature [51 references]  Display  Hide  Download
Contributor : Ist Rennes Connect in order to contact the contributor
Submitted on : Friday, November 19, 2010 - 4:29:22 PM
Last modification on : Monday, August 8, 2022 - 5:38:05 PM
Long-term archiving on: : Sunday, February 20, 2011 - 3:00:08 AM


Files produced by the author(s)


  • HAL Id : inria-00537914, version 1


Armando Castañeda, Sergio Rajsbaum, Michel Raynal. The Renaming Problem in Shared Memory Systems: an Introduction. [Research Report] PI-1960, 2010, pp.29. ⟨inria-00537914⟩



Record views


Files downloads