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

DOI10.4230/LIPICS.DISC.2018.21zbMATH Open1497.68043arXiv1805.04840MaRDI QIDQ5090913FDOQ5090913

Authors: Aryaz Eghbali, Philipp Woelfel 

Publication date: 21 July 2022

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

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

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)

Cites Work

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

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)