A tight RMR lower bound for randomized mutual exclusion

Abstract : The Cache Coherent (CC) and the Distributed Shared Memory (DSM) models are standard shared memory models, and the Remote Memory Reference (RMR) complexity is considered to accurately predict the actual performance of mutual exclusion algorithms in shared memory systems. In this paper we prove a tight lower bound for the RMR complexity of deadlock-free randomized mutual exclusion algorithms in both the CC and the DSM model with atomic registers and compare\&swap objects and an adaptive adversary. Our lower bound establishes that an adaptive adversary can schedule $n$ processes in such a way that each enters the critical section once, and the total number of RMRs is $\Omega(n \log n/\log\log n)$ in expectation. This matches an upper bound of Hendler and Woelfel (2011).
Type de document :
Communication dans un congrès
STOC - 44th ACM Symposium on Theory of Computing, May 2012, New York, United States. 2012
Liste complète des métadonnées

Littérature citée [25 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00722940
Contributeur : George Giakkoupis <>
Soumis le : lundi 6 août 2012 - 16:55:31
Dernière modification le : mercredi 16 mai 2018 - 11:23:13
Document(s) archivé(s) le : mercredi 7 novembre 2012 - 03:22:42

Fichier

stoc12_mutex.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00722940, version 1

Citation

George Giakkoupis, Philipp Woelfel. A tight RMR lower bound for randomized mutual exclusion. STOC - 44th ACM Symposium on Theory of Computing, May 2012, New York, United States. 2012. 〈hal-00722940〉

Partager

Métriques

Consultations de la notice

410

Téléchargements de fichiers

194