Randomized Mutual Exclusion with Constant Amortized RMR Complexity on the DSM

Abstract : In this paper we settle an open question by determining the remote memory reference (RMR) complexity of randomized mutual exclusion, on the distributed shared memory model (DSM) with atomic registers, in a weak but natural (and stronger than oblivious) adversary model. In particular, we present a mutual exclusion algorithm that has constant expected amortized RMR complexity and is deterministically deadlock free. Prior to this work, no randomized algorithm with o(log n/ log log n) RMR complexity was known for the DSM model. Our algorithm is fairly simple, and compares favorably with one by Bender and Gilbert (FOCS 2011) for the CC model, which has expected amortized RMR complexity O(log^2 log n) and provides only probabilistic deadlock freedom.
Type de document :
Communication dans un congrès
55th IEEE Symposium on Foundations of Computer Science (FOCS), Oct 2014, Philadelphia, PA, United States
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01097144
Contributeur : George Giakkoupis <>
Soumis le : vendredi 19 décembre 2014 - 00:56:11
Dernière modification le : mercredi 16 mai 2018 - 11:23:13
Document(s) archivé(s) le : lundi 23 mars 2015 - 17:31:24

Fichier

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

Identifiants

  • HAL Id : hal-01097144, version 1

Citation

George Giakkoupis, Philipp Woelfel. Randomized Mutual Exclusion with Constant Amortized RMR Complexity on the DSM. 55th IEEE Symposium on Foundations of Computer Science (FOCS), Oct 2014, Philadelphia, PA, United States. 〈hal-01097144〉

Partager

Métriques

Consultations de la notice

385

Téléchargements de fichiers

167