Randomized mutual exclusion with sub-logarithmic RMR-complexity

DOI10.1007/S00446-011-0128-6MaRDI QIDQ661045zbMATH OpenOpenAlexFDO

Authors Danny Hendler, Philipp Woelfel

Publication date 6 February 2012

Published in Distributed Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00446-011-0128-6

zbMATH Keywords

mutual exclusionrandomizationremote memory reference (RMR)strong adversary

Mathematics Subject Classification ID

Distributed systems (68M14) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)

Recommendations

• Randomized mutual exclusion in \(\mathcal{O}(\log N / \log \log N)\) RMRs
• A tight RMR lower bound for randomized mutual exclusion
• Deterministic abortable mutual exclusion with sublogarithmic adaptive RMR complexity
• Adaptive randomized mutual exclusion in sub-logarithmic expected time
• RMR-efficient randomized abortable mutual exclusion (extended abstract)
• Randomized mutual exclusion algorithms revisited
• Lower Bounds for Randomized Mutual Exclusion
• Randomized abortable mutual exclusion with constant amortized RMR complexity on the CC model
• Brief announcement, a tight RMR lower bound for randomized mutual exclusion

Cites work

• Adaptive and efficient abortable mutual exclusion
• Closing the complexity gap between FCFS mutual exclusion and mutual exclusion
• Constant-RMR implementations of CAS and other synchronization primitives using read and write operations
• scientific article; zbMATH DE number 1696664 (Why is no real title available?)
• scientific article; zbMATH DE number 5485533 (Why is no real title available?)
• scientific article; zbMATH DE number 2006640 (Why is no real title available?)
• Linearizable implementations do not suffice for randomized distributed computation
• Nonatomic mutual exclusion with local spinning
• SOFSEM 2005: Theory and Practice of Computer Science

Cited in

(22)

• Recoverable mutual exclusion
• A complexity separation between the cache-coherent and distributed shared memory models
• Mutual exclusion algorithms with constant RMR complexity and wait-free exit code
• Lower Bounds for Randomized Mutual Exclusion
• A time complexity lower bound for adaptive mutual exclusion
• RMR-efficient randomized abortable mutual exclusion (extended abstract)
• Allocate-on-use space complexity of shared-memory algorithms
• An almost tight RMR lower bound for abortable test-and-set
• Randomized Concurrent Set Union and Generalized Wake-Up
• Randomized mutual exclusion in \(\mathcal{O}(\log N / \log \log N)\) RMRs
• An \(O(1)\)-barriers optimal RMRs mutual exclusion algorithm (extended abstract)
• Adaptive randomized mutual exclusion in sub-logarithmic expected time
• Constant RMR solutions to reader writer synchronization
• Deterministic abortable mutual exclusion with sublogarithmic adaptive RMR complexity
• Randomized mutual exclusion algorithms revisited
• On the Complexity of Reader-Writer Locks
• Recoverable mutual exclusion in sub-logarithmic time
• Randomized abortable mutual exclusion with constant amortized RMR complexity on the CC model
• An \(O(1)\) RMRs leader election algorithm
• Tight time-space tradeoff for mutual exclusion
• A tight RMR lower bound for randomized mutual exclusion
• Brief announcement, a tight RMR lower bound for randomized mutual exclusion

This page was built for publication: Randomized mutual exclusion with sub-logarithmic RMR-complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q661045)