On the space complexity of randomized synchronization

DOI10.1145/290179.290183zbMath1065.68543OpenAlexW2042141409MaRDI QIDQ3158522

Nir Shavit, Maurice P. Herlihy, Faith E. Fich

Publication date: 25 January 2005

Published in: Journal of the ACM (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Related Items

The space complexity of unbounded timestamps ⋮ Lower and upper bounds for single-scanner snapshot implementations ⋮ The space complexity of long-lived and one-shot timestamp implementations ⋮ On the uncontended complexity of anonymous agreement ⋮ RMR-efficient implementations of comparison primitives using read and write operations ⋮ Tight bounds for shared memory systems accessed by Byzantine processes ⋮ Universal constructions that ensure disjoint-access parallelism and wait-freedom ⋮ Hundreds of impossibility results for distributed computing ⋮ Linear space bootstrap communication schemes ⋮ The complexity of updating snapshot objects ⋮ Tight bounds for adopt-commit objects ⋮ A complexity-based classification for multiprocessor synchronization ⋮ On the optimal space complexity of consensus for anonymous processes ⋮ Lower Bounds for Restricted-Use Objects ⋮ Communication-efficient randomized consensus ⋮ A Tight Space Bound for Consensus ⋮ Computing in totally anonymous asynchronous shared memory systems