Nonatomic mutual exclusion with local spinning

Abstract

We present an N-process local-spin mutual exclusion algorithm, based on nonatomic reads and writes, in which each process performs Θ(log N) remote memory references to enter and exit its critical section. No atomic read/write algorithm with better asymptotic worst-case time complexity is currently known. This suggests that atomic memory is not fundamentally required if one is interested in worst-case time complexity. The same cannot be said if one is interested in fast-path or adaptive algorithms. We show that such algorithms fundamentally require memory accesses to be atomic. In particular, we show that for any N-process nonatomic algorithm, there exists a single-process execution in which the lone competing process executes Ω(log N/log log N) remote operations to enter its critical section. Moreover, these operations must access Ω(√log N/log log N) distinct variables.