RMR-efficient randomized abortable mutual exclusion (extended abstract)

DOI10.1007/978-3-642-33651-5_19zbMATH Open1377.68043arXiv1208.1723OpenAlexW1635884043MaRDI QIDQ4909417FDOQ4909417

Authors: Abhijeet Pareek, Philipp Woelfel 

Publication date: 13 March 2013

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: Recent research on mutual exclusion for shared-memory systems has focused on "local spin" algorithms. Performance is measured using the "remote memory references" (RMRs) metric. As common in recent literature, we consider a standard asynchronous shared memory model with N processes, which allows atomic read, write and compare-and-swap (short: CAS) operations. In such a model, the asymptotically tight upper and lower bound on the number of RMRs per passage through the Critical Section is Theta(log N) for the optimal deterministic algorithms (see Yang and Anderson,1995, and Attiya, Hendler and Woelfel, 2008). Recently, several randomized algorithms have been devised that break the Omega(log N) barrier and need only o(log N) RMRs per passage in expectation (see Hendler and Woelfel, 2010, Hendler and Woelfel, 2011, and Bender and Gilbert, 2011). In this paper we present the first randomized "abortable" mutual exclusion algorithm that achieves a sub-logarithmic expected RMR complexity. More precisely, against a weak adversary (which can make scheduling decisions based on the entire past history, but not the latest coin-flips of each process) every process needs an expected number of O(log N/ log log N) RMRs to enter end exit the critical section. If a process receives an abort-signal, it can abort an attempt to enter the critical section within a finite number of its own steps and by incurring O(log N/ log log N) RMRs.

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

Recommendations

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

zbMATH Keywords

randomizationshared memoryremote memory referencesabortable mutual exclusionRMRsweak adversary

Mathematics Subject Classification ID

Randomized algorithms (68W20) Analysis of algorithms (68W40) Distributed algorithms (68W15) Distributed systems (68M14)

Cited In (12)

• An \(O(1)\)-barriers optimal RMRs mutual exclusion algorithm (extended abstract)
• Randomized mutual exclusion in \(\mathcal{O}(\log N / \log \log N)\) RMRs
• Brief announcement, a tight RMR lower bound for randomized mutual exclusion
• Randomized abortable mutual exclusion with constant amortized RMR complexity on the CC model
• Deterministic abortable mutual exclusion with sublogarithmic adaptive RMR complexity
• Adaptive randomized mutual exclusion in sub-logarithmic expected time
• Randomized mutual exclusion with sub-logarithmic RMR-complexity
• An almost tight RMR lower bound for abortable test-and-set
• Recoverable mutual exclusion with abortability
• Randomized mutual exclusion algorithms revisited
• Abortable Reader-Writer Locks Are No More Complex Than Abortable Mutex Locks
• A tight RMR lower bound for randomized mutual exclusion

This page was built for publication: RMR-efficient randomized abortable mutual exclusion (extended abstract)

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