Content area
Lock-free data structures may be accessed and updated by multiple processes without the use of locks. This thesis considers the design of new and efficient lock-free data structures for dynamic sets, supporting Insert, Delete, and Search operations. Lock-free data structures can be difficult to analyze because operations may run forever. In an amortized analysis of these data structures, we consider the number of steps taken in an execution consisting of a sequence operations, rather than an individual operation. Depending on how the steps of processes are interleaved, there are many ways that these sequences of operations can be performed. This work considers both upper bounds on the amortized step complexity of particular data structures and lower bounds on the amortized step complexity of classes of data structures.
Our first main result modifies an existing lock-free balanced binary search tree, called a chromatic tree, so that it has good amortized step complexity. The analysis is the first to be performed on a balanced binary search tree.
We next show a lower bound on the amortized step complexity for a large class of lock-free data structures for dynamic sets. The lower bound applies to many lock-free data structures such as linked lists and search trees, including the chromatic tree. This shows that, under certain conditions, the asymptotic amortized step complexity of many known lock-free data structures have matching upper and lower bounds.
Finally, we introduce new algorithmic techniques and use them to implement a lock-free binary trie. It has O(1) worst-case step complexity for Search operations, and additionally supports Min, Max, Predecessor, and Successor operations with good amortized step complexity.