Résumé | Renaming is a fundamental problem in distributed computing,
in which a set of processes need to pick new names from a small
namespace.
In this talk, we present a new connection between renaming and the
classic mutual exclusion problem. We exploit this connection to get
new linear time complexity lower bounds for deterministic renaming,
queue, stack, and fetch-and-increment implementations. On the other
hand, we use it to obtain fast mutual exclusion algorithms based on
sorting networks.
Joint work with James Aspnes, Seth Gilbert, and Rachid Guerraoui.
A full version of these results appeared in the Proceedings of FOCS
2011, and is available at http://people.epfl.ch/dan.alistarh
Orateur: Dan Alistarh |