Brief Announcement: 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 exclu-sion (ME) algorithms for N asynchronous reliable processes, that communicate only by reading and writing shared mem-ory. We exhibit an upper bound of O(logN) RMRs for FCFS ME, which is tight, improves on prior results, and matches a lower bound for ME (with or without FCFS)