scientific article; zbMATH DE number 7561273

DOI10.4230/LIPIcs.DISC.2018.21zbMath1497.68043arXiv1805.04840MaRDI QIDQ5090913

Aryaz Eghbali, Philipp Woelfel

Publication date: 21 July 2022

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

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Closing the complexity gap between FCFS mutual exclusion and mutual exclusion
• Randomized mutual exclusion with sub-logarithmic RMR-complexity
• RMR-efficient implementations of comparison primitives using read and write operations
• On the importance of having an identity or, is consensus really universal?
• Nonatomic mutual exclusion with local spinning
• On the time and space complexity of randomized test-and-set
• Optimal-time adaptive strong renaming, with applications to counting
• Making objects writable
• Adaptive and efficient abortable mutual exclusion
• Sub-logarithmic Test-and-Set against a Weak Adversary
• The complexity of obstruction-free implementations
• Fast Randomized Test-and-Set and Renaming
• Impossibility of distributed consensus with one faulty process
• Efficient synchronization of multiprocessors with shared memory
• Contention in shared memory algorithms
• RMR-Efficient Randomized Abortable Mutual Exclusion
• An improved lower bound for the time complexity of mutual exclusion
• Randomized mutual exclusion in O(log N / log log N) RMRs
• Non-blocking timeout in scalable queue-based spin locks
• Adaptive randomized mutual exclusion in sub-logarithmic expected time
• Randomized Abortable Mutual Exclusion with Constant Amortized RMR Complexity on the CC Model
• An $O(1)$ RMRs Leader Election Algorithm
• Constant-RMR implementations of CAS and other synchronization primitives using read and write operations
• Abortable and query-abortable objects and their efficient implementation
• A tight RMR lower bound for randomized mutual exclusion
• The Complexity of Renaming
• Mutual Exclusion with O(log^2 Log n) Amortized Work
• SOFSEM 2005: Theory and Practice of Computer Science

This page was built for publication: