Time complexity bounds for shared-memory mutual exclusion
Yong-Jik Kim, James Horton Anderson · 2003
The primary goal of my work is to close the gap between lower and upper bounds on the time complexity of the mutual exclusion problem in shared-memory multiprocessor systems. Mutual exclusion algorithms are used to resolve conicting accesses to shared resources by asynchronous, concurrent processes. The problem of designing such an algorithm is widely regarded as the preeminent \\classic" problem in concurrent programming. In this proposal, the time complexity of a mutual exclusion algorithm is dened as the number of remote memory references generated by a process to enter and exit its critical section. Under this measure, constant-time algorithms are known that use primitives such as fetch-and-add and fetch-and-store. However, it has been shown that no such constant-time algorithm is possible that uses reads, writes, and comparison primitives. My dissertation aims to provide optimal time bounds for algorithms based on such primitives. 1