Actualités
  Période
semaine
ou mois
aucune période


  Thèmes:
Thèses
Colloques
Autres
Groupes
Tous les thèmes

   
  Liens:
Voir les thèses

Voir les colloques

Voir les autres événements

Voir la page des groupes

Accéder à l'intranet

Intitulé:   
The Complexity of Picking a Name
du 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 
UrlEPFL 



Aucun document lié à cet événement.

Retour
Retour à l'index