We're sorry but this page doesn't work properly without JavaScript enabled. Please enable it to continue.
Feedback

Concurrent data structures: Recoverable, Abortable, and Adaptive Mutual Exclusion with Sublogarithmic RMR Complexity

Formal Metadata

Title
Concurrent data structures: Recoverable, Abortable, and Adaptive Mutual Exclusion with Sublogarithmic RMR Complexity
Title of Series
Number of Parts
30
Author
License
CC Attribution 4.0 International:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Identifiers
Publisher
Release Date
Language

Content Metadata

Subject Area
Genre
Abstract
We present the first recoverable mutual exclusion (RME) algorithm that is simultaneously abortable, adaptive to point contention, and with sublogarithmic RMR complexity. Our algorithm has O(min(K,logWN)) RMR passage complexity and O(F+min(K,logWN)) RMR super-passage complexity, where K is the number of concurrent executing processes (point contention), W is the size (in bits) of registers, and F is the number of crashes in a super-passage. Under the standard assumption that W=Θ(logN), these bounds translate to worst-case O(logNloglogN) passage complexity and O(F+logNloglogN) super-passage complexity. Our key building blocks are: A D-process abortable RME algorithm, for D≤W, with O(1) passage complexity and O(1+F) super-passage complexity. We obtain this algorithm by using the Fetch-And-Add (FAA) primitive, unlike prior work on RME that uses Fetch-And-Store (FAS/SWAP). A generic transformation that transforms any abortable RME algorithm with passage complexity of B<W, into an abortable RME lock with passage complexity of O(min(K,B)).