Skip to Main content Skip to Navigation
Reports

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 :
Reports
Complete list of metadata

Cited literature [51 references]  Display  Hide  Download

https://hal.inria.fr/inria-00537914
Contributor : Ist Rennes <>
Submitted on : Friday, November 19, 2010 - 4:29:22 PM
Last modification on : Tuesday, June 15, 2021 - 4:27:42 PM
Long-term archiving on: : Sunday, February 20, 2011 - 3:00:08 AM

File

PI-1960.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00537914, version 1

Citation

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⟩

Share

Metrics

Record views

810

Files downloads

1785