Tight Lower Bound for the RMR Complexity of Recoverable Mutual Exclusion
David Chan, Philipp Woelfel · 2021
We present a tight RMR complexity lower bound for the recoverable mutual exclusion (RME) problem, defined by Golab and Ramaraju [9]. 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 Ω(log n/log log n) 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.,[6,7,11]).