Timing-based mutual exclusion with local spinning

Abstract. We consider the time complexity of shared-memory mutual exclusionalgorithms based on reads, writes, and comparison primitives under the remotememory-reference (RMR) time measure. For asynchronous systems, a lower boundof \Omega (log N / log log N) RMRs per critical-section entry has been established inprevious work, where N is the number of processes. In this paper, we show thatlower RMR time complexity is attainable in semi-synchronous systems in which processes may execute delay statements. When assessing the time complexity ofdelay-based algorithms, the question of whether delays should be counted arises. We consider both possibilities. Also of relevance is whether delay durations areupper-bounded. (They are lower-bounded by de#nition.) Again, we consider both possibilities. For each of these possibilities, we present an algorithm with either \Theta (1) or \Theta (log log N) time complexity. For the cases in which a \Theta (log log N)algorithm is given, we establish matchin