Tight Lower Bound for the RMR Complexity of Recoverable Mutual Exclusion

DOI10.1145/3465084.3467938arXiv2106.03185OpenAlexW3183901574MaRDI QIDQ6201981FDOQ6201981

Authors: David Yu Cheng Chan, Philipp Woelfel 

Publication date: 26 March 2024

Published in: Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Abstract: We present a tight RMR complexity lower bound for the recoverable mutual exclusion (RME) problem, defined by Golab and Ramaraju cite{GR2019a}. In particular, we show that any $n$-process RME algorithm using only atomic read, write, fetch-and-store, fetch-and-increment, and compare-and-swap operations, has an RMR complexity of $Omega(logn/loglogn)$ on the CC and DSM model. This lower bound covers all realistic synchronization primitives that have been used in RME algorithms and matches the best upper bounds of algorithms employing swap objects (e.g., [5,6,10]). Algorithms with better RMR complexity than that have only been obtained by either (i) assuming that all failures are system-wide [7], (ii) employing fetch-and-add objects of size $(logn{)}^{omega(1)}$ [12], or (iii) using artificially defined synchronization primitives that are not available in actual systems [6,9].

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

zbMATH Keywords

asynchronous systemshared memoryfetch and incrementrecoverable mutual exclusion

Mathematics Subject Classification ID

Distributed algorithms (68W15) Distributed systems (68M14)

This page was built for publication: Tight Lower Bound for the RMR Complexity of Recoverable Mutual Exclusion

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