Closing the complexity gap between FCFS mutual exclusion and mutual exclusion

DOI10.1007/S00446-010-0096-2zbMath1231.68168OpenAlexW1987584238MaRDI QIDQ660999

Wojciech Golab, Robert Danek

Publication date: 6 February 2012

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

Full work available at URL: https://doi.org/10.1007/s00446-010-0096-2

zbMATH Keywords

complexityasynchronous shared memory modelFirst-come-first-served (FCFS) mutual exclusion (ME)remote memory references (RMRs)RMR complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (4)

RMR-efficient implementations of comparison primitives using read and write operations ⋮ A time complexity lower bound for adaptive mutual exclusion ⋮ Randomized mutual exclusion with sub-logarithmic RMR-complexity ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Adaptive mutual exclusion with local spinning
• A new solution of Dijkstra's concurrent programming problem
• f -arrays
• Adaptive and efficient mutual exclusion (extended abstract)
• An Ω ( n log n ) lower bound on the cost of mutual exclusion
• Improving fast mutual exclusion
• Constant-RMR implementations of CAS and other synchronization primitives using read and write operations
• The Black-White Bakery Algorithm and Related Bounded-Space, Adaptive, Local-Spinning and FIFO Algorithms

This page was built for publication: Closing the complexity gap between FCFS mutual exclusion and mutual exclusion