Closing the complexity gap between mutual exclusion and FCFS mutual exclusion
Robert Danek, Wojciech Golab · 2008
We consider the worst-case remote memory reference (RMR) complexity of first-come-first-served (FCFS) mutual exclusion (ME) algorithms for N asynchronous reliable processes that communicate only by reading and writing shared memory. We exhibit an upper bound of O(log N) RMRs for FCFS ME, which is tight, improves on prior results, and matches a lower bound for ME (with or without FCFS).