Efficient lock-free binary search trees

DOI10.1145/2611462.2611500MaRDI QIDQ2943632zbMATH OpenOpenAlexFDO

Authors Bapi Chatterjee, Nhan Nguyen, Philippas Tsigas

Publication date 3 September 2015

Published in Proceedings of the 2014 ACM symposium on Principles of distributed computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1404.3272

zbMATH Keywords

amortized analysisbinary search treeconcurrent data structureslock-freeshared memory

Mathematics Subject Classification ID

Data structures (68P05) Distributed algorithms (68W15)

Abstract: In this paper we present a novel algorithm for concurrent lock-free internal binary search trees (BST) and implement a Set abstract data type (ADT) based on that. We show that in the presented lock-free BST algorithm the amortized step complexity of each set operation - {sc Add}, {sc Remove} and {sc Contains} - is $O(H(n)+c)$, where, $H(n)$ is the height of BST with $n$ number of nodes and $c$ is the contention during the execution. Our algorithm adapts to contention measures according to read-write load. If the situation is read-heavy, the operations avoid helping pending concurrent {sc Remove} operations during traversal, and, adapt to interval contention. However, for write-heavy situations we let an operation help pending {sc Remove}, even though it is not obstructed, and so adapt to tighter point contention. It uses single-word compare-and-swap ( exttt{CAS}) operations. We show that our algorithm has improved disjoint-access-parallelism compared to similar existing algorithms. We prove that the presented algorithm is linearizable. To the best of our knowledge this is the first algorithm for any concurrent tree data structure in which the modify operations are performed with an additive term of contention measure.

Recommendations

• A fast contention-friendly binary search tree
• Lock-free concurrent binomial heaps
• The amortized complexity of non-blocking binary search trees
• scientific article; zbMATH DE number 2033285
• CBTree: a practical concurrent self-adjusting search tree

Cited in

(13)

• Unsafe operations in B-trees
• Lock-free concurrent binomial heaps
• Non-blocking Patricia tries with replace operations
• Concurrent linearizable nearest neighbour search in LockFree-kD-tree
• In the search for optimal concurrency
• The amortized complexity of non-blocking binary search trees
• Adaptive lock-free maps: purely-functional to scalable
• A fast contention-friendly binary search tree
• CBTree: a practical concurrent self-adjusting search tree
• The amortized analysis of a non-blocking chromatic tree
• Lock-free search data structures: throughput modeling with Poisson processes
• The SkipTrie, low-depth concurrent search without rebalancing
• A template for implementing fast lock-free trees using HTM

This page was built for publication: Efficient lock-free binary search trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2943632)