@inproceedings{4d76081e84d74528a3857117e597bdc8,
title = "A Relaxed Balanced Lock-Free Binary Search Tree",
abstract = "This paper presents a new relaxed balanced concurrent binary search tree using a single word compare and swap primitive, in which all operations are lock-free. Our design separates balancing actions from update operations and includes a lock-free balancing mechanism in addition to the insert, search, and relaxed delete operations. Search in our design is not affected by ongoing concurrent update operations or by the movement of nodes by tree restructuring operations. Our experiments show that our algorithm performs better than other state-of-the-art concurrent BSTs.",
keywords = "Binary search tree, Concurrent data structure, Lock-free",
author = "Manish Singh and Lindsay Groves and Alex Potanin",
note = "{\textcopyright} 2021, Springer Nature Switzerland AG.; 21st International Conference on Parallel and Distributed Computing, Applications, and Technologies, PDCAT 2020 ; Conference date: 28-12-2020 Through 30-12-2020",
year = "2021",
doi = "10.1007/978-3-030-69244-5\_27",
language = "English",
isbn = "978-3-030-69243-8",
series = "Lecture Notes in Computer Science (LNCS)",
publisher = "Springer Science+Business Media B.V.",
pages = "304--317",
editor = "Yong Zhang and Yicheng Xu and Hui Tian",
booktitle = "Parallel and Distributed Computing, Applications and Technologies - 21st International Conference, PDCAT 2020, Proceedings",
address = "Netherlands",
}