Evènement pour le groupe Algorithmique Distribuée

Date 2011-11-21  14:00-15:00
TitreThe Complexity of Picking a Name 
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 
Lieus. 076 
OrateurDan Alistarh 

Aucun document lié à cet événement.

Retour à l'index