Allocate-on-use space complexity of shared-memory algorithms
From MaRDI portal
Publication:5090897
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)
Cites work
- scientific article; zbMATH DE number 5485533 (Why is no real title available?)
- A fast, scalable mutual exclusion algorithm
- A tight space bound for consensus
- Bounds on shared memory for mutual exclusion
- Efficient adaptive collect using randomization
- Fast randomized test-and-set and renaming
- Faster randomized consensus with an oblivious adversary
- Mutual Exclusion with O(log^2 Log n) Amortized Work
- On the time and space complexity of randomized test-and-set
- Randomized abortable mutual exclusion with constant amortized RMR complexity on the CC model
- Randomized mutual exclusion with sub-logarithmic RMR-complexity
- Sublogarithmic test-and-set against a weak adversary
- Tight bounds for adopt-commit objects
- Time and Space Lower Bounds for Nonblocking Implementations
- Universal codeword sets and representations of the integers
- Wait-free algorithms for fast, long-lived renaming
Cited in
(6)- Space-time trade-offs for stack-based algorithms
- Progress-space tradeoffs in single-writer memory implementations
- Space- and time-adaptive nonblocking algorithms
- Shared memory and the Bakery algorithm
- Quantifying and evaluating the space overhead for alternative C++ memory layouts
- Choice-memory tradeoff in allocations
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)
