Concurrent Search Data Structures Can Be Blocking and Practically Wait-Free

We argue that there is virtually no practical situation in which one should seek a "theoretically wait-free" algorithm at the expense of a state-of-the-art blocking algorithm in the case of search data structures: blocking algorithms are simple, fast, and can be made "practically wait-free". We draw this conclusion based on the most exhaustive study of blocking search data structures to date. We consider (a) different search data structures of different sizes, (b) numerous uniform and non-uniform workloads, representative of a wide range of practical scenarios, with different percentages of update operations, (c) with and without delayed threads, (d) on different hardware technologies, including processors providing HTM instructions. We explain our claim that blocking search data structures are practically wait-free through an analogy with the birthday paradox, revealing that, in state-of-the-art algorithms implementing such data structures, the probability of conflicts is extremely small. When conflicts occur as a result of context switches and interrupts, we show that HTM-based locks enable blocking algorithms to cope with them

Published in:
Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures, 337-348
Presented at:
28th ACM Symposium on Parallelism in Algorithms and Architectures, Pacific Grove, California, USA, SPAA’16, July 11–13, 2016

 Record created 2016-09-08, last modified 2018-01-28

External link:
Download fulltext
Publisher's version
Rate this document:

Rate this document:
(Not yet reviewed)