Blog
About

45
views
0
recommends
+1 Recommend
1 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      An Improved Lock-Free Binary Search Tree

      Preprint

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          We investigated the binary search tree data structure proposed in the publication, Efficient Lock-Free Binary Search Trees by Bapi Chatterjee, Nhan Nguyen and Philipas Tsigas. We will explore its correctness, progression factor, and the linearizability of its operations and report our findings. With a lock-free algorithm, software engineers will be able to use a thread-safe binary search tree that is capable of the many different operations that are normally available on a binary search tree. This includes the basic, primitive operations of Add(), Contains(), and Remove(), without the performance loss of using a binary search tree that uses object locking. An implementation of a binary search tree that uses locks to promote thread-safety takes a performance loss due to the threads waiting when another thread holds the lock and causing contention. The approach outlined in the aforementioned paper claims to have several key fundamental improvements over existing lock-free binary search tree algorithms. This implementation of the binary search tree eliminates contention in Contains() operations where, if a node was modified while a Contains() operation took place, the program would restart any current operation from the root of the tree. This happens because the thread can no longer reliably confide in the traversal of the tree and must restart its search. This is taxing to the performance of a binary search tree and an inefficient design can underperform a sequential implementation. Among other improvements, the authors of this paper claim that their algorithm is linearizable and has improved disjoint-access parallelism compared to similar existing algorithms.

          Related collections

          Author and article information

          Journal
          ScienceOpen Preprints
          ScienceOpen
          30 May 2019
          Affiliations
          [1 ] University of Central Florida
          Article
          10.14293/S2199-1006.1.SOR-.PP8OYVU.v1

          This work has been published open access under Creative Commons Attribution License CC BY 4.0 , which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. Conditions, terms of use and publishing policy can be found at www.scienceopen.com .

          The datasets generated during and/or analysed during the current study are available from the corresponding author on reasonable request.

          Data structures & Algorithms

          binary search tree, Lock-Free Binary Search Trees

          Comments

          Comment on this article