Adam Alon: Deterministic Abortable Mutual Exclusion with Sublogarithmic Adaptive RMR Complexity

Abstract: We present a deterministic abortable mutual exclusion algorithm for a cache-coherent (CC) model with read, write, Fetch-And-Add (F&A), and CAS primitives, whose RMR complexity is O(log_W N) , where W is the size of the F&A registers. Under the standard assumption of W=Θ(log N), our algorithm's RMR complexity is Olog N/log log N); if W=Θ(N^ε), for 0 < ε <1 (as is the case in real multiprocessor machines), the RMR complexity is O(1). Our algorithm is adaptive to the number of processes that abort. In particular, if no process aborts during a passage, its RMR cost is O(1).

Paper: https://dl.acm.org/citation.cfm?id=3212759