On the time and space complexity of randomized test-and-set

DOI10.1145/2332432.2332436zbMath1301.68254OpenAlexW2012971222MaRDI QIDQ2933773

Philipp Woelfel, George Giakkoupis

Publication date: 5 December 2014

Published in: Proceedings of the 2012 ACM symposium on Principles of distributed computing (Search for Journal in Brave)

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

zbMATH Keywords

randomizationshared memoryleader electiontest-and-settime/space complexitystrong/weak adversary

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) Randomized algorithms (68W20) Distributed algorithms (68W15)

Related Items (7)

Game-theoretic fairness meets multi-party protocols: the case of leader election ⋮ Efficient randomized test-and-set implementations ⋮ Unnamed Item ⋮ Faster randomized consensus with an oblivious adversary ⋮ Allocate-On-Use Space Complexity of Shared-Memory Algorithms ⋮ Concurrent Use of Write-Once Memory ⋮ A Tight Space Bound for Consensus

This page was built for publication: On the time and space complexity of randomized test-and-set