A time complexity lower bound for adaptive mutual exclusion
From MaRDI portal
Publication:424906
DOI10.1007/S00446-011-0152-6zbMATH Open1291.68178OpenAlexW2070595838MaRDI QIDQ424906FDOQ424906
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)
Cites Work
- Bounds on shared memory for mutual exclusion
- Speeding Lamport's fast mutual exclusion algorithm
- Time/contention trade-offs for multiprocessor synchronization
- The Black-White Bakery Algorithm and Related Bounded-Space, Adaptive, Local-Spinning and FIFO Algorithms
- 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
- Title not available (Why is that?)
- Title not available (Why is that?)
- 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
- Local-Spin Group Mutual Exclusion Algorithms
- Closing the complexity gap between FCFS mutual exclusion and mutual exclusion
- Randomized mutual exclusion with sub-logarithmic RMR-complexity
Cited In (7)
- Title not available (Why is that?)
- An improved lower bound for the time complexity of mutual exclusion
- Title not available (Why is that?)
- Lower bounds on the amortized time complexity of shared objects
- Lower Bounds for Randomized Mutual Exclusion
- Tight Bounds for Asynchronous Renaming
- Adaptive and efficient mutual exclusion
Recommendations
This page was built for publication: A time complexity lower bound for adaptive mutual exclusion
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q424906)
