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.
Origine : Fichiers produits par l'(les) auteur(s)
Loading...