Re-implementation of Lock-free Contention Adapting Search Trees Using MRLock

To explore multi-core programming, we re-implement the Lock Free Contention Adapting Search Tree. We follow the structure of the original, using immutable treaps as leaf nodes implemented with an array for better performance with memory caching. The initial re-implementation uses coarse-grained locking with MRLock to provide thread-safety. This will be extended to be lock-free in a future publication.

Content

Author and article information

Journal

Title: ScienceOpen Preprints

Publisher: ScienceOpen

Publication date (Electronic preprint): 23 March 2020

Affiliations

[1 ] University of Central Florida

Author information

Kevin Boyles https://orcid.org/0000-0002-1176-4562

Article

DOI: 10.14293/S2199-1006.1.SOR-.PPIV7TZ.v1

SO-VID: 74675d5c-aeb0-4d11-bc93-797a0c51ee4e

License:

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 .

History

Date received : 23 March 2020

Data availability: The datasets generated during and/or analysed during the current study are available in the repository: https://github.com/kboyles8/lock-free-search-tree

ScienceOpen disciplines: Data structures & Algorithms

Keywords: coarse-grained locking,multi-core programming,lock-free,MRLock,tree