A time complexity lower bound for adaptive mutual exclusion
From MaRDI portal
Publication:424906
DOI10.1007/s00446-011-0152-6zbMath1291.68178OpenAlexW2070595838MaRDI QIDQ424906
Yong-Jik Kim, James H. Anderson
Publication date: 7 June 2012
Published in: Distributed Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00446-011-0152-6
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distributed systems (68M14)
Related Items (2)
Cites Work
- Unnamed Item
- Unnamed Item
- Closing the complexity gap between FCFS mutual exclusion and mutual exclusion
- Randomized mutual exclusion with sub-logarithmic RMR-complexity
- Speeding Lamport's fast mutual exclusion algorithm
- Bounds on shared memory for mutual exclusion
- Time/contention trade-offs for multiprocessor synchronization
- Adaptive mutual exclusion with local spinning
- A simple local-spin group mutual exclusion algorithm
- A complexity separation between the cache-coherent and distributed shared memory models
- Adaptive and efficient abortable mutual exclusion
- f -arrays
- The k -bakery
- Adaptive randomized mutual exclusion in sub-logarithmic expected time
- Constant RMR solutions to reader writer synchronization
- Bounds on the shared memory requirements for long-lived & adaptive objects (extended abstract)
- Adaptive and efficient mutual exclusion (extended abstract)
- An Ω ( n log n ) lower bound on the cost of mutual exclusion
- Improving fast mutual exclusion
- An $O(1)$ RMRs Leader Election Algorithm
- Constant-RMR implementations of CAS and other synchronization primitives using read and write operations
- The Black-White Bakery Algorithm and Related Bounded-Space, Adaptive, Local-Spinning and FIFO Algorithms
- Local-Spin Group Mutual Exclusion Algorithms
This page was built for publication: A time complexity lower bound for adaptive mutual exclusion
