Constant RMR System-wide Failure Resilient Durable Locks with Dynamic Joining

Anup Joshi
Prasad Jayanti
ACM Symposium on Parallelism in Algorithms and Architectures (2023)

Abstract

We design a Recoverable Mutual Exclusion (RME) algorithm for the system-wide failure model. Our algorithm requires only O(1) space per process, and achieves O(1) worst-case RMR complexity in both the CC and DSM models. Furthermore, in contrast to existing RME algorithms which can only support a pre-declared set of n threads with names from 1 to n, our algorithm can be accessed by arbitrarily many dynamically allocated threads of arbitrary names.