Contention Adapting Search Trees

The lock-free contention adapting search tree (LFCA tree) is described in the following publications:

• Kjell Winblad, Bengt Jonsson and Konstantinos Sagonas. Lock-free Contention Adapting Search Trees. ACM Transactions on Parallel Computing, Volume 8, Issue 2, Article No. 10, pages 1–38, June 2021. (publisher's version).

• Kjell Winblad, Bengt Jonsson and Konstantinos Sagonas. Lock-free Contention Adapting Search Trees. 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2018). (see note here, publisher's version, preprint, code)

A comprehensive description of the lock-based contention adapting search tree (CA tree) with support for the operations insert, delete, lookup and range query is given in the journal publication below. This publication contains a detailed description of the data structure including pseudo-code and proofs for the correctness properties (linearizability, deadlock freedom and livelock freedom).

• Konstantinos Sagonas and Kjell Winblad. A contention adapting approach to concurrent ordered sets. Journal of Parallel and Distributed Computing, 2018 (submitted 2016). (publisher's version, preprint, code)

The journal publication above is built upon the following two conference publications. The first of those papers describes CA trees with support for single-element operations (insert, delete, and lookup). This paper contains two experimental evaluations of CA tree optimizations that are not included in the journal paper above. One of these optimzations is for use cases with very high contention. The other one combines a CA tree with hardware lock elision. The second paper evaluates and describes a CA tree extension to support linearizable range operations (range queries and range updates) and bulk operations. The technical report that is referred to in these two papers has been replaced by the journal publication above.

• Konstantinos Sagonas and Kjell Winblad. Contention Adapting Search Trees. In Proceedings of the Fourteenth International Symposium on Parallel and Distributed Computing, Limassol, Cyprus, July 2015. (publisher's version, preprint, code)
• Konstantinos Sagonas and Kjell Winblad. Efficient Support for Range Queries and Range Updates Using Contention Adapting Search Trees. In Proceedings of the 28th International Workshop on Languages and Compilers for Parallel Computing, Raleigh, USA, September 2015. (publisher's version, preprint, code)

The publication below describes an optimization for CA trees that is enabled by using an immutable data structure internally. This optimization is especially beneficial for range queries when contention is high. The experimental results presented in the paper show that the optimized CA tree variant outperform many recently proposed data structures in many scenarios. The benchmark code and the code for the optimized CA tree variant is available here.

• Kjell Winblad. Faster Concurrent Range Queries with Contention Adapting Search Trees Using Immutable Data. In the proceedings of 2017 Imperial College Computing Student Workshop (ICCSW 2017), London, United Kingdom, September 2017. (publisher's version, preprint, code)

The publication below describes how CA trees can be used to improve the scalability of the Erlang Term Storage.

• Konstantinos Sagonas and Kjell Winblad. More Scalable Ordered Set for ETS Using Adaptation. In Proceedings of the Thirteenth ACM SIGPLAN Workshop on Erlang, pages 3-11, Gothenburg, Sweden, September 2014.

The code used to obtain the experimental results included in the CA tree papers can be found by following the links with the text "code" that can be found next to the citations above.