A time complexity lower bound for adaptive mutual exclusion
From MaRDI portal
Publication:424906
DOI10.1007/S00446-011-0152-6zbMATH Open1291.68178OpenAlexW2070595838MaRDI QIDQ424906FDOQ424906
Authors: 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
Recommendations
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, implementation and applications
- The \(k\)-bakery, local-spin \(k\)-exclusion using non-atomic reads and writes
- 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 \({\Omega}(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 (13)
- The price of being adaptive
- Title not available (Why is that?)
- An improved lower bound for the time complexity of mutual exclusion
- A tight bound on remote reference time complexity of mutual exclusion in the read-modify-write model
- Time bounds for mutual exclusion and related problems
- An \({\Omega}(n\log n)\) lower bound on the cost of mutual exclusion
- Lower bounds on the amortized time complexity of shared objects
- Lower Bounds for Randomized Mutual Exclusion
- Tight bounds for asynchronous renaming
- Timing-based mutual exclusion with local spinning. (Extended abstract)
- Lower bounds on the amortized time complexity of shared objects
- Adaptive and efficient mutual exclusion
- An improved lower bound for the time complexity of mutual exclusion
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)
