RECORD
Persistent Non-Blocking Binary Search Trees Supporting Wait-Free Range Queries
Distributed, Parallel, and Cluster Computing · Submitted 12 May 2018
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim This paper presents the first implementation of a search tree data structure in an asynchronous shared-memory system that provides a wait-free algorithm for executing range queries on the tree, in addition to non-blocking algorithms for Insert, Delete and Find, using single-word Compare-and-Swap (CAS).
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
This paper presents the first implementation of a search tree data structure in an asynchronous shared-memory system that provides a wait-free algorithm for executing range queries on the tree, in addition to non-blocking algorithms for Insert, Delete and Find, using single-word Compare-and-Swap (CAS). The implementation is linearizable and tolerates any number of crash failures. Insert and Delete operations that operate on different parts of the tree run fully in parallel (without any interference with one another). We employ a lightweight helping mechanism, where each Insert, Delete and Find operation helps only update operations that affect the local neighbourhood of the leaf it arrives at. Similarly, a Scan helps only those updates taking place on nodes of the part of the tree it traverses, and therefore Scans operating on different parts of the tree do not interfere with one another. Our implementation works in a dynamic system where the number of processes may change over time. The implementation builds upon the non-blocking binary search tree implementation presented by Ellen et al. (in PODC 2010) by applying a simple mechanism to make the tree persistent.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | This paper presents the first implementation of a search tree data structure in an asynchronous shared-memory system that provides a wait-free algorithm for executing range queries on the tree, in addition to non-blocking algorithms for Insert, Delete and Find, using single-word Compare-and-Swap (CAS). | contribution 1.00 | 0.94 | 0.72 | asserted 1.00 |
| s1 | The implementation is linearizable and tolerates any number of crash failures. | result 0.71 | 0.85 | 0.13 | asserted 1.00 |
| s2 | Insert and Delete operations that operate on different parts of the tree run fully in parallel (without any interference with one another). | result 0.47 | 0.87 | 0.10 | asserted 1.00 |
| s3 | We employ a lightweight helping mechanism, where each Insert, Delete and Find operation helps only update operations that affect the local neighbourhood of the leaf it arrives at. | method 0.98 | 0.92 | 0.05 | asserted 1.00 |
| s4 | Similarly, a Scan helps only those updates taking place on nodes of the part of the tree it traverses, and therefore Scans operating on different parts of the tree do not interfere with one another. | method 0.76 | 0.88 | 0.06 | asserted 1.00 |
| s5 | Our implementation works in a dynamic system where the number of processes may change over time. | contribution 0.85 | 0.81 | 0.04 | asserted 0.92 |
| s6 | The implementation builds upon the non-blocking binary search tree implementation presented by Ellen et al. (in PODC 2010) by applying a simple mechanism to make the tree persistent. | method 0.75 | 0.69 | 0.06 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
This paper presents the first implementation of a search tree data structure in an asynchronous shared-memory system that provides a wait-free algorithm for executing range queries on the tree, in addition to non-blocking algorithms for Insert, Delete and Find, using single-word Compare-and-Swap (CAS). The implementation is linearizable and tolerates any number of crash failures. Insert and Delete operations that operate on different parts of the tree run fully in parallel (without any interference with one another). We employ a lightweight helping mechanism, where each Insert, Delete and Find operation helps only update operations that affect the local neighbourhood of the leaf it arrives at. Similarly, a Scan helps only those updates taking place on nodes of the part of the tree it traverses, and therefore Scans operating on different parts of the tree do not interfere with one another. Our implementation works in a dynamic system where the number of processes may change over time. The implementation builds upon the non-blocking binary search tree implementation presented by Ellen et al. (in PODC 2010) by applying a simple mechanism to make the tree persistent.
Human review
How the literature uses it
2 arXiv papers cite this in 4 sentences
Papers citing it · 1 sentence without a confident label
Cites it as background 2 papers
-
Lock-freedom [ref] is a widely-studied property when designing concurrent trees [ref] and other data structures [ref] .
Parallel and Distributed Data Series Processing on Modern and Emerging Hardware · Discussion · 0.98
-
Lock-freedom [ref] is a widely-studied property when designing concurrent trees [ref] and other data structures [ref] .
FreSh: A Lock-Free Data Series Index · Introduction · 0.99
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.