Wait-free Trees with Asymptotically-Efficient Range Queries

Ilya Kokorin, Dan Alistarh, Vitaly Aksenov

Tree data structures, such as red-black trees, quad trees, treaps, or tries, are fundamental tools in computer science. A classical problem in concurrency is to obtain expressive,…