®®®® SIIA Público

Título del libro: Proceedings Of The Annual Acm Symposium On Principles Of Distributed Computing
Título del capítulo: Brief announcement: There are plenty of tasks weaker than perfect renaming and stronger than set agreement

Autores UNAM:
SERGIO RAJSBAUM GORODEZKY;
Autores externos:

Idioma:

Año de publicación:
2012
Palabras clave:

Decision task; distributed computability; Renaming problem; Symmetry-breaking; task solvability; Computation theory


Resumen:

In the asynchronous wait-free shared memory model, two families of tasks play a central role because of their implications in theory and in practice: k-set agreement and M-renaming. Let n denote the number of processes in the system. Previous research shows that (n-1)-set agreement can solve (2n-2)-renaming, for any value of n, while (2n-2)-renaming cannot solve (n-1)-set agreement, when n is odd. It is also known that, for every n > 3, n-renaming, also called perfect renaming, is strictly stronger than (n-1)-set agreement. This paper shows that when n > 4, there is a family of tasks that are strictly stronger than (n-1)-set agreement and strictly weaker than perfect renaming. This enlarges our view of both the nature and the structure of what are distributed computing tasks. © 2012 Authors.


Entidades citadas de la UNAM: