A time complexity lower bound for adaptive mutual exclusion

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

zbMATH Keywords

adaptive mutual exclusionalgorithmic lower boundsremote memory referencesshared-memory systems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distributed systems (68M14)

Recommendations

• scientific article; zbMATH DE number 2006640
• An improved lower bound for the time complexity of mutual exclusion
• An improved lower bound for the time complexity of mutual exclusion
• Time bounds for mutual exclusion and related problems
• The price of being adaptive

Cites work

• scientific article; zbMATH DE number 5485533 (Why is no real title available?)
• scientific article; zbMATH DE number 2006640 (Why is no real title available?)
• A complexity separation between the cache-coherent and distributed shared memory models
• A simple local-spin group mutual exclusion algorithm
• Adaptive and efficient abortable mutual exclusion
• Adaptive and efficient mutual exclusion (extended abstract)
• Adaptive mutual exclusion with local spinning
• Adaptive randomized mutual exclusion in sub-logarithmic expected time
• An \(O(1)\) RMRs leader election algorithm
• An \({\Omega}(n\log n)\) lower bound on the cost of mutual exclusion
• Bounds on shared memory for mutual exclusion
• Bounds on the shared memory requirements for long-lived \& adaptive objects (extended abstract)
• Closing the complexity gap between FCFS mutual exclusion and mutual exclusion
• Constant RMR solutions to reader writer synchronization
• Constant-RMR implementations of CAS and other synchronization primitives using read and write operations
• F-arrays, implementation and applications
• Improving fast mutual exclusion
• Local-Spin Group Mutual Exclusion Algorithms
• Randomized mutual exclusion with sub-logarithmic RMR-complexity
• Speeding Lamport's fast mutual exclusion algorithm
• The Black-White Bakery Algorithm and Related Bounded-Space, Adaptive, Local-Spinning and FIFO Algorithms
• The \(k\)-bakery, local-spin \(k\)-exclusion using non-atomic reads and writes
• Time/contention trade-offs for multiprocessor synchronization

Cited in

(13)

• Timing-based mutual exclusion with local spinning. (Extended abstract)
• Tight bounds for asynchronous renaming
• Time bounds for mutual exclusion and related problems
• Lower bounds on the amortized time complexity of shared objects
• 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
• scientific article; zbMATH DE number 2006640 (Why is no real title available?)
• An \({\Omega}(n\log n)\) lower bound on the cost of mutual exclusion
• An improved lower bound for the time complexity of mutual exclusion
• Adaptive and efficient mutual exclusion
• The price of being adaptive
• Lower bounds on the amortized time complexity of shared objects
• Lower Bounds for Randomized 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)