An improved lower bound for the time complexity of mutual exclusion

DOI10.1007/S00446-002-0084-2zbMath1448.68060OpenAlexW2703407771MaRDI QIDQ5138382

Yong-Jik Kim, James H. Anderson

Publication date: 3 December 2020

Published in: Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00446-002-0084-2

zbMATH Keywords

lower boundstime complexityshared memorymutual exclusionatomicitylocal spinning

Mathematics Subject Classification ID

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

Related Items (5)

On the inherent weakness of conditional primitives ⋮ Word-Size RMR Tradeoffs for Recoverable Mutual Exclusion ⋮ Nonatomic mutual exclusion with local spinning ⋮ Recoverable mutual exclusion ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Speeding Lamport's fast mutual exclusion algorithm
• Time/contention trade-offs for multiprocessor synchronization
• Adaptive solutions to the mutual exclusion problem
• Nonatomic mutual exclusion with local spinning
• Adaptive and efficient mutual exclusion (extended abstract)
• Improving fast mutual exclusion

This page was built for publication: An improved lower bound for the time complexity of mutual exclusion