An improved lower bound for the time complexity of mutual exclusion

Abstract

We establish a lower bound of O(log N/log log N) remote memory references for N-process mutual exclusion algorithms based on reads, writes, or comparison primitives. Our bound improves an earlier bound of O(log log N/log log log N) established by Cypher.