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

https://hal.inria.fr/hal-01097144
Contributor : George Giakkoupis <>
Submitted on : Friday, December 19, 2014 - 12:56:11 AM
Last modification on : Thursday, January 7, 2021 - 4:33:36 PM
Long-term archiving on: : Monday, March 23, 2015 - 5:31:24 PM

File

focs14_mutexobl.pdf
Files produced by the author(s)

Identifiers

  • 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⟩

Share

Metrics

Record views

457

Files downloads

332