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

DOI10.1145/2332432.2332436MaRDI QIDQ2933773zbMATH OpenOpenAlexFDO

Authors George Giakkoupis, Philipp Woelfel

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

leader electionrandomizationshared memorystrong/weak adversarytest-and-settime/space complexity

Mathematics Subject Classification ID

Distributed systems (68M14) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) 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

• Efficient randomized test-and-set implementations
• Sublogarithmic test-and-set against a weak adversary
• Randomized two-process wait-free test-and-set
• Fast randomized test-and-set and renaming
• Test-and-set in optimal space

Cited in

(11)

• Efficient randomized test-and-set implementations
• Game-theoretic fairness meets multi-party protocols: the case of leader election
• Concurrent use of write-once memory
• Test-and-set in optimal space
• Sublogarithmic test-and-set against a weak adversary
• Randomness-efficient low degree tests and short PCPs via epsilon-biased sets
• A tight space bound for consensus
• Allocate-on-use space complexity of shared-memory algorithms
• An almost tight RMR lower bound for abortable test-and-set
• Randomized two-process wait-free test-and-set
• Faster randomized consensus with an oblivious adversary

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

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