Randomized abortable mutual exclusion with constant amortized RMR complexity on the CC model

DOI10.1145/3087801.3087837MaRDI QIDQ5368967zbMATH OpenOpenAlexFDO

Authors George Giakkoupis, Philipp Woelfel

Publication date 11 October 2017

Published in Proceedings of the ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Full work available at URL https://hal.inria.fr/hal-01635734/file/podc2017mutex.pdf

zbMATH Keywords

shared memorymutual exclusionRMR complexityoblivious adversaryCC model

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Distributed algorithms (68W15)

Recommendations

• Deterministic abortable mutual exclusion with sublogarithmic adaptive RMR complexity
• RMR-efficient randomized abortable mutual exclusion (extended abstract)
• A tight RMR lower bound for randomized mutual exclusion
• Randomized mutual exclusion with sub-logarithmic RMR-complexity
• Randomized mutual exclusion in \(\mathcal{O}(\log N / \log \log N)\) RMRs

Cited in

(6)

• Allocate-on-use space complexity of shared-memory algorithms
• Deterministic abortable mutual exclusion with sublogarithmic adaptive RMR complexity
• Recoverable mutual exclusion
• Randomized mutual exclusion with sub-logarithmic RMR-complexity
• An almost tight RMR lower bound for abortable test-and-set
• Recoverable mutual exclusion with abortability

This page was built for publication: Randomized abortable mutual exclusion with constant amortized RMR complexity on the CC model

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