A time complexity bound for adaptive mutual exclusion (Extended abstract)

DOI10.1007/3-540-45414-4_1MaRDI QIDQ4436036zbMATH OpenFDO

Authors Yong-Jik Kim, James H. Anderson

Publication date 23 November 2003

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2180/21800001.htm

Mathematics Subject Classification ID

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

Recommendations

• A time complexity lower bound for adaptive mutual exclusion
• An improved lower bound for the time complexity of mutual exclusion
• Time bounds for mutual exclusion and related problems
• Adaptive and efficient mutual exclusion (extended abstract)
• Adaptive randomized mutual exclusion in sub-logarithmic expected time

Cited in

(16)

• Efficient adaptive collect using randomization
• Nonatomic mutual exclusion with local spinning
• Adaptive mutual exclusion with local spinning
• Analysis of timing-based mutual exclusion with random times
• An improved lower bound for the time complexity of mutual exclusion
• Time bounds for mutual exclusion and related problems
• A time complexity lower bound for adaptive mutual exclusion
• An almost tight RMR lower bound for abortable test-and-set
• Fast timing-based algorithms
• Adaptive and efficient mutual exclusion
• An improved lower bound for the time complexity of mutual exclusion
• Shared-memory mutual exclusion: major research trends since 1986
• On the Complexity of Reader-Writer Locks
• Closing the complexity gap between FCFS mutual exclusion and mutual exclusion
• Randomized mutual exclusion with sub-logarithmic RMR-complexity
• A tight bound on remote reference time complexity of mutual exclusion in the read-modify-write model

This page was built for publication: A time complexity bound for adaptive mutual exclusion (Extended abstract)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4436036)