Skip to Main content Skip to Navigation
Reports

An Equivariance Theorem with Applications to Renaming

Abstract : 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.
Document type :
Reports
Complete list of metadata

Cited literature [11 references]  Display  Hide  Download

https://hal.inria.fr/inria-00586190
Contributor : Ist Rennes Connect in order to contact the contributor
Submitted on : Friday, April 15, 2011 - 11:15:06 AM
Last modification on : Thursday, January 20, 2022 - 4:20:30 PM
Long-term archiving on: : Thursday, November 8, 2012 - 4:36:20 PM

File

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

Identifiers

  • HAL Id : inria-00586190, version 1

Citation

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

Share

Metrics

Record views

251

Files downloads

225