Allocate-on-use space complexity of shared-memory algorithms
From MaRDI portal
Publication:5090897
DOI10.4230/LIPICS.DISC.2018.8zbMATH Open1497.68559OpenAlexW2898895592MaRDI QIDQ5090897FDOQ5090897
Authors: James Aspnes, Bernhard Haeupler, Alexander Tong, 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/
Recommendations
- Randomized mutual exclusion in \(\mathcal{O}(\log N / \log \log N)\) RMRs
- Tight time-space tradeoff for mutual exclusion
- Randomized mutual exclusion with sub-logarithmic RMR-complexity
- Adaptive randomized mutual exclusion in sub-logarithmic expected time
- Adaptive and efficient mutual exclusion (extended abstract)
Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Distributed algorithms (68W15) Distributed systems (68M14)
Cites Work
- Universal codeword sets and representations of the integers
- Bounds on shared memory for mutual exclusion
- Time and Space Lower Bounds for Nonblocking Implementations
- Wait-free algorithms for fast, long-lived renaming
- Title not available (Why is that?)
- Randomized mutual exclusion with sub-logarithmic RMR-complexity
- Tight bounds for adopt-commit objects
- Randomized abortable mutual exclusion with constant amortized RMR complexity on the CC model
- A fast, scalable mutual exclusion algorithm
- A tight space bound for consensus
- On the optimal space complexity of consensus for anonymous processes
- Efficient adaptive collect using randomization
- On the time and space complexity of randomized test-and-set
- Sublogarithmic test-and-set against a weak adversary
- Fast randomized test-and-set and renaming
- Mutual Exclusion with O(log^2 Log n) Amortized Work
- Faster randomized consensus with an oblivious adversary
Cited In (6)
- Space- and time-adaptive nonblocking algorithms
- Shared memory and the Bakery algorithm
- Quantifying and evaluating the space overhead for alternative C++ memory layouts
- Space-time trade-offs for stack-based algorithms
- Choice-memory tradeoff in allocations
- Progress-space tradeoffs in single-writer memory implementations
This page was built for publication: Allocate-on-use space complexity of shared-memory algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5090897)
