Lock-free Contention Adapting Search Trees
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, Konstantinos Sagonas and Bengt Jonsson. Lock-free Contention Adapting Search Trees
. In Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA'2018. (preprint, publisher's version)
Note
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.
Code
Code that can be used to reproduce the results from the paper can be found here
. A possible more up to date version of the benchmarking code is available here:
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 (kjell.winblad@it.uu.se) if you have any questions.