An Ω ( n log n ) lower bound on the cost of mutual exclusion

DOI10.1145/1146381.1146423zbMath1314.68143OpenAlexW2131910547MaRDI QIDQ5177289

Rui Fan, Nancy A. Lynch

Publication date: 10 March 2015

Published in: Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1146381.1146423

zbMATH Keywords

time complexitymutual exclusionlower bound techniques

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distributed systems (68M14) Distributed algorithms (68W15)

Related Items (4)

RMR-efficient implementations of comparison primitives using read and write operations ⋮ A time complexity lower bound for adaptive mutual exclusion ⋮ Closing the complexity gap between FCFS mutual exclusion and mutual exclusion ⋮ Recoverable mutual exclusion

This page was built for publication: An Ω ( n log n ) lower bound on the cost of mutual exclusion