Skip to main content
Department of Information Technology

Lock-free Contention Adapting Search Trees


  • 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).


The SPAA'2018 paper erroneously claims that the lookup operation of the LFCA tree is wait-free, but it is only lock-free. Please contact the authors for more information on this issue and a possible fix.

Tests for Pseudocode

The pseudocde included in the LFCA tree paper have been extracted from runnable C code that has been stress tested and tested with the help of Nidhugg. The C code and the tests can be found in this archive. Please see the readme file inside the archive for information on how to run the tests.

More Information

This page contains information about the lock-based CA tree.

Please, contact Kjell Winblad ( if you have any questions.

Updated  2022-12-12 11:18:18 by Konstantinos Sagonas.