An Equivariance Theorem with Applications to Renaming - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2011

An Equivariance Theorem with Applications to Renaming

Résumé

In the renaming problem, each process in a distributed system is issued a unique name from a large name space, and the processes must coordinate with one another to choose unique names from a much smaller name space. We show that lower bounds on the solvability of renaming in an asynchronous distributed system can be formulated as a purely topological question about the existence of an equivariant chain map from a "topological disk" to a "topological annulus". Proving the non-existence of such a map implies the non-existence of a distributed renaming algorithm in several related models of computation.
Ce rapport pr'esente un th'eor'eme d''equivariance avec des applications au renommage.
Fichier principal
Vignette du fichier
PI-1975.pdf (247.69 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00586190 , version 1 (15-04-2011)

Identifiants

  • HAL Id : inria-00586190 , version 1

Citer

Armando Castaneda, Maurice Herlihy, Sergio Rajsbaum. An Equivariance Theorem with Applications to Renaming. [Research Report] PI-1975, 2011, pp.14. ⟨inria-00586190⟩
264 Consultations
250 Téléchargements

Partager

Gmail Facebook X LinkedIn More