closing the complexity gap between mutual exclusion and fcfs mutual exclusion
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).
mutual exclusion first-come-first-served (fcfs) shared memory rmr complexity