@inproceedings{66193312f5c7445cac2237ecf3b3020b,
title = "A concurrency-optimal binary search tree",
abstract = "The paper presents the first concurrency-optimal implementation of a binary search tree (BST). The implementation, based on a standard sequential implementation of a partially-external tree, ensures that every schedule, i.e., interleaving of steps of the sequential code, is accepted unless linearizability is violated. To ensure this property, we use a novel read-write locking protocol that protects tree edges in addition to its nodes. Our implementation performs comparably to the state-of-the-art BSTs and even outperforms them on few workloads, which suggests that optimizing the set of accepted schedules of the sequential code can be an adequate design principle for efficient concurrent data structures.",
keywords = "Binary search tree, Concurrency optimality, Linearizability",
author = "Vitaly Aksenov and Vincent Gramoli and Petr Kuznetsov and Anna Malova and Srivatsan Ravi",
note = "Publisher Copyright: {\textcopyright} 2017, Springer International Publishing AG.; 23rd International Conference on Parallel and Distributed Computing, Euro-Par 2017 ; Conference date: 28-08-2017 Through 01-09-2017",
year = "2017",
month = jan,
day = "1",
doi = "10.1007/978-3-319-64203-1\_42",
language = "English",
isbn = "9783319642024",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "580--593",
editor = "Rivera, \{Francisco F.\} and Pena, \{Tomas F.\} and Cabaleiro, \{Jose C.\}",
booktitle = "Euro-Par 2017",
}