An almost tight RMR lower bound for abortable test-and-set

DOI10.4230/LIPICS.DISC.2018.21MaRDI QIDQ5090913zbMATH OpenFDO

Authors Aryaz Eghbali, Philipp Woelfel

Publication date 21 July 2022

Full work available at URL https://arxiv.org/abs/1805.04840

zbMATH Keywords

lower boundleader electionRMR complexitycompare-and-swaptest-and-setabortability

Mathematics Subject Classification ID

Randomized algorithms (68W20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distributed algorithms (68W15) Distributed systems (68M14)

Recommendations

• Randomized abortable mutual exclusion with constant amortized RMR complexity on the CC model
• 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
• An \(O(1)\) RMRs leader election algorithm

Cites work

• scientific article; zbMATH DE number 1696664 (Why is no real title available?)
• scientific article; zbMATH DE number 5485533 (Why is no real title available?)
• scientific article; zbMATH DE number 2006640 (Why is no real title available?)
• scientific article; zbMATH DE number 3041944 (Why is no real title available?)
• A tight RMR lower bound for randomized mutual exclusion
• Abortable and query-abortable objects and their efficient implementation
• Adaptive and efficient abortable mutual exclusion
• Adaptive randomized mutual exclusion in sub-logarithmic expected time
• An \(O(1)\) RMRs leader election algorithm
• An improved lower bound for the time complexity of mutual exclusion
• Closing the complexity gap between FCFS mutual exclusion and mutual exclusion
• Constant-RMR implementations of CAS and other synchronization primitives using read and write operations
• Contention in shared memory algorithms
• Efficient synchronization of multiprocessors with shared memory
• Fast randomized test-and-set and renaming
• Impossibility of distributed consensus with one faulty process
• Making objects writable
• Mutual Exclusion with O(log^2 Log n) Amortized Work
• Non-blocking timeout in scalable queue-based spin locks
• Nonatomic mutual exclusion with local spinning
• On the importance of having an identity or, is consensus really universal?
• On the time and space complexity of randomized test-and-set
• Optimal-time adaptive strong renaming, with applications to counting
• RMR-efficient implementations of comparison primitives using read and write operations
• RMR-efficient randomized abortable mutual exclusion (extended abstract)
• Randomized abortable mutual exclusion with constant amortized RMR complexity on the CC model
• Randomized mutual exclusion in \(\mathcal{O}(\log N / \log \log N)\) RMRs
• Randomized mutual exclusion with sub-logarithmic RMR-complexity
• Randomized naming using wait-free shared variables
• SOFSEM 2005: Theory and Practice of Computer Science
• Sublogarithmic test-and-set against a weak adversary
• The Complexity of Renaming
• The complexity of obstruction-free implementations

This page was built for publication: An almost tight RMR lower bound for abortable test-and-set

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