Allocate-On-Use Space Complexity of Shared-Memory Algorithms
From MaRDI portal
Publication:5090897
DOI10.4230/LIPICS.DISC.2018.8zbMath1497.68559OpenAlexW2898895592MaRDI QIDQ5090897
Alexander Tong, James Aspnes, Bernhard Haeupler, Philipp Woelfel
Publication date: 21 July 2022
Full work available at URL: http://drops.dagstuhl.de/opus/volltexte/2018/9797/pdf/LIPIcs-DISC-2018-8.pdf/
Analysis of algorithms and problem complexity (68Q25) Distributed systems (68M14) Randomized algorithms (68W20) Distributed algorithms (68W15)
Cites Work
- Unnamed Item
- Tight bounds for adopt-commit objects
- Randomized mutual exclusion with sub-logarithmic RMR-complexity
- Bounds on shared memory for mutual exclusion
- Wait-free algorithms for fast, long-lived renaming
- Efficient adaptive collect using randomization
- On the time and space complexity of randomized test-and-set
- Sub-logarithmic Test-and-Set against a Weak Adversary
- Fast Randomized Test-and-Set and Renaming
- Universal codeword sets and representations of the integers
- Time and Space Lower Bounds for Nonblocking Implementations
- A fast, scalable mutual exclusion algorithm
- A tight space bound for consensus
- Randomized Abortable Mutual Exclusion with Constant Amortized RMR Complexity on the CC Model
- Mutual Exclusion with O(log^2 Log n) Amortized Work
- Faster randomized consensus with an oblivious adversary
- On the optimal space complexity of consensus for anonymous processes
This page was built for publication: Allocate-On-Use Space Complexity of Shared-Memory Algorithms
