Lock-Free Augmented Trees (Abstract)
Panagiota Fatourou, Eric Ruppert · 2025
In sequential search trees, nodes can be augmented with additional information to support a wide range of additional operations, such as order-statistic queries. We describe a general technique for augmenting concurrent implementations of search trees, yielding lock-free, linearizable analogues of classical augmented tree data structures. The technique can be applied, for example, to existing lock-free binary search trees without affecting the asymptotic amortized step complexity of updates. Queries are wait-free and are performed by executing the same code as would be used in a sequential implementation on a snapshot of the tree.