Google Research

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

ACM Symposium on Parallelism in Algorithms and Architectures (2023)


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.

Learn more about how we do research

We maintain a portfolio of research projects, providing individuals and teams the freedom to emphasize specific types of work