RMR-efficient randomized abortable mutual exclusion (extended abstract)

DOI10.1007/978-3-642-33651-5_19MaRDI QIDQ4909417zbMATH OpenOpenAlexFDO

Authors Abhijeet Pareek, Philipp Woelfel

Publication date 13 March 2013

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

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

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)

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.

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

Cited in

(12)

• A tight RMR lower bound for randomized mutual exclusion
• Randomized mutual exclusion algorithms revisited
• An almost tight RMR lower bound for abortable test-and-set
• 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
• Abortable Reader-Writer Locks Are No More Complex Than Abortable Mutex Locks
• Randomized abortable mutual exclusion with constant amortized RMR complexity on the CC model
• Adaptive randomized mutual exclusion in sub-logarithmic expected time
• Recoverable mutual exclusion with abortability
• Randomized mutual exclusion with sub-logarithmic RMR-complexity
• Deterministic abortable mutual exclusion with sublogarithmic adaptive RMR complexity

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)