One of the challenges in the design of concurrent data structures is choosing the best liveness property to implement: there is often a tradeoff between the strength of the progress guarantees and the efficiency and simplicity of the algorithm.
We discuss two well-known liveness properties -- wait-freedom and lock-freedom -- and then propose a new liveness property that offers a balance between the two traditional ones. Wait-freedom guarantees that all processes in the system make progress, but often yields complicated and inefficient algorithms. Lock-freedom, on the other hand, permits simpler and more efficient algorithms, but it only guarantees that a single process will make progress. Furthermore, under high contention, processes may get stuck forever in a lock-free object. We propose a parametrized liveness property, called k-abortability, that spans the range between wait-freedom and lock-freedom and does not allow processes to get stuck.
The definition is simple and natural: intuitively, an operation on a k-abortable object can abort only if k operations from distinct processes succeed during the execution of the aborted operation. We show that k-abortable objects can be more efficient than their wait-free counterparts, by giving an efficient universal construction for k-abortable objects shared by n processes that takes only O(k) steps per operation. For k = o(log n), this beats the well-known lower bound of Ω(log n) steps per operation for universal constructions of wait-free objects. Finally, we give an Ω(log k)-steps lower bound for universal constructions of k-abortable objects.
Based on joint work with David Yu Cheng Chan, Vassos Hadzilacos and Sam Toueg.
BIO:Naama Ben-David is a first-year PhD student at Carnegie Mellon University, advised by Guy Blelloch. Before coming to CMU, she completed her BSc in Computer Science at the University of Toronto. Her research interests lie in parallel and distributed algorithms.