Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [27 references]  Display  Hide  Download
Contributor : George Giakkoupis Connect in order to contact the contributor
Submitted on : Friday, December 19, 2014 - 12:56:11 AM
Last modification on : Thursday, January 20, 2022 - 4:20:00 PM
Long-term archiving on: : Monday, March 23, 2015 - 5:31:24 PM


Files produced by the author(s)


  • HAL Id : hal-01097144, version 1


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⟩



Record views


Files downloads