Using Delays to Improve RMR Time Complexity in Mutual Exclusion Algorithms (Extended Abstract)

We consider the time complexity of shared-memory mutual exclusion algorithms under the remote-memory-reference (RMR) time measure. In particular, algorithms based on reads, writes, and comparison primitives are considered. For such algorithms, a lower bound of \Omega(log N/ log log N) RMRs per critical-section entry has been established in previous work, where N is the number of processes. Also, algorithms with O(log N) time complexity are known. Thus, for algorithms in this class, logarithmic or near-logarithmic RMR time complexity is fundamentally required. In this paper, we consider..