Please note: This master’s thesis presentation will be given online.
William
Sigouin, Master’s
candidate
David
R.
Cheriton
School
of
Computer
Science
To maximize the performance of concurrent data structures, researchers have turned to highly complex fine-grained techniques. Resulting algorithms are often extremely difficult to understand and prove correct, allowing for highly cited works to contain correctness bugs that go undetected for long periods of time. This complexity is perceived as a necessary sacrifice: simpler, more general techniques simply cannot attain competitive performance with these fine-grained implementations.
To challenge this perception, we present three data structures created using multi-word compare-and-swap (KCAS), version numbering, and double-collect searches that showcase the power of using a more coarse-grained approach. First, we present the first (to the best of our knowledge) lock-free binary search tree (BST) that is both fully-internal and balanced, which is able to achieve competitive performance with the state-of-the-art fine-grained concurrent BSTs while being significantly simpler. Next, we present the first concurrent implementation of an Euler tour data structure, solving fully-dynamic graph connectivity. Finally, we outline a modified implementation of an (a,b)-tree to use our methodology, which shows significant performance improvements in certain workloads when compared to the original.