Siddhartha Jayanti: An Optimal Amortized Algorithm for Abortable Mutual Exclusion

The abortable mutual exclusion problem was introduced by Scott and Scherer to meet a need that arises in database and real-time systems, where processes sometimes have to abandon their attempt to acquire a mutual exclusion lock to initiate recovery from a potential deadlock or to avoid overshooting a deadline. Algorithms of O(1) RMR complexity have been known for the standard mutual exclusion problem for both the Cache-Coherent (CC) and Distributed Shared Memory (DSM) models of mutiprocessors, but whether O(1) RMR complexity is also achievable for abortable mutual exclusion has remained open for the 18 years that this problem has been investigated.

 

Jayanti gave a Theta(log n) worst case RMR complexity solution for the CC and DSM models, where n is the maximum number of processes that execute the algorithm concurrently. Lee's dissertation presented the first algorithm of O(1) RMR complexity (this bound is on the amortized RMR complexity), but Lee's algorithm has several limitations: aborts take long to complete (a process performs Theta(n) steps in the worst case to abort), the algorithm requires support for both CAS and Fetch&Store instructions, and it works only for the CC model (the amortized complexity is unbounded for the DSM model). Giakouppis and Woelfel's algorithm, presented at PODC last year, has O(1) amortized complexity, but it works only for the CC model, uses randomization, and the O(1) amortized bound holds only in expectation and is proven for the weak oblivious adversary model.

 

I will present a new algorithm that is free of these limitations: our algorithm is deterministic, supports fast aborts (a process completes an abort in O(1) steps), has a small space complexity of O(n), requires hardware support for only the Fetch&Store instruction, and most importantly, has O(1) amortized RMR complexity for both the CC and DSM models. Our algorithm is short and practical with fewer than a dozen lines of code, and is accompanied by a rigorous proof of mutual exclusion through invariants and of starvation-freedom and complexity analysis through potential functions. Thus, modulo amortization, our result answers affirmatively the long-standing open question described above.

 

(This is joint work, done with Professor Prasad Jayanti of Dartmouth College)