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é:   
Tight Bounds for Anonymous Conflict Detectors
du groupe Algorithmique Distribuée

Date 2011-12-12  14:00-15:00
TitreTight Bounds for Anonymous Conflict Detectors  
RésuméMost known distributed algorithms for randomized consensus from multi-writer registers proceed in rounds, each of which performs two tasks. The first is to ensure agreement with some nonzero probability. The second is to detect whether agreement has been reached. We give matching upper and lower bounds of min{log m / log log m, n}, to within constant factors, for the individual step complexity of a wait-free m-valued conflict detector for n anonymous processes implemented from multi-writer registers. The upper bound is deterministic, but the lower bound also holds for randomized implementations. It follows that the same lower bound holds on the individual step complexity of m-valued wait-free anonymous consensus, even for randomized algorithms with global coins against an oblivious adversary. The upper bound can also be used to slightly improve a previous upper bound on the cost of randomized consensus. This work is joint with James Aspnes and appeared at SPAA 2011. Orateur: Faith Ellen 
Lieus. 076 
OrateurFaith Ellen 
UrlUniversity of Toronto 



Aucun document lié à cet événement.

Retour
Retour à l'index