Sub-Logarithmic Test-and-Set Against a Weak Adversary
Alistarh, Dan; Aspnes, James
2011

Fichiers

Résumé

A randomized implementation is given of a test-and-set register with O(log log it) individual step complexity and O(n) total step complexity against an oblivious adversary. The implementation is linearizable and multi-shot, and shows an exponential complexity improvement over previous solutions designed to work against a strong adversary.

Détails

Titre Sub-Logarithmic Test-and-Set Against a Weak Adversary
Auteur(s) Alistarh, Dan ; Aspnes, James
Publié dans Distributed Computing. DISC 2011
Pagination 13
Série Lecture Notes in Computer Science, 6950
Pages 97-109
Présenté à 25th International Symposium, DISC 2011, Rome, Italy, September 20-22, 2011
Date 2011
Editeur Berlin, Springer-Verlag Berlin
ISBN 978-3-642-24099-7
DOI https://doi.org/10.1007/978-3-642-24100-0_7
Autres identifiant(s) Afficher la publication dans Web of Science
Laboratoires DCL
Le document apparaît dans Production scientifique et compétences > I&C - Faculté Informatique & Communications > IINFCOM > DCL - Laboratoire de calcul distribué
Publications validées par des pairs
Papiers de conférence
Travail produit à l'EPFL
Publié
Date de création de la notice 2011-07-14

Actions

Aperçu