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.
Type de document :
[Research Report] PI-1960, 2010, pp.29
Liste complète des métadonnées

Littérature citée [51 références]  Voir  Masquer  Télécharger
Contributeur : Ist Rennes <>
Soumis le : vendredi 19 novembre 2010 - 16:29:22
Dernière modification le : mercredi 16 mai 2018 - 11:23:13
Document(s) archivé(s) le : dimanche 20 février 2011 - 03:00:08


Fichiers produits par l'(les) auteur(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〉



Consultations de la notice


Téléchargements de fichiers