A Concurrency-Optimal Binary Search Tree

Abstract : The paper presents the first \emph{concurrency-optimal} implementation of a binary search tree (BST). The implementation, based on a standard sequential implementation of an internal tree, ensures that every \emph{schedule} is accepted, i.e., interleaving of steps of the sequential code, unless linearizability is violated. To ensure this property, we use a novel read-write locking scheme that protects tree \emph{edges} in addition to nodes. Our implementation outperforms the state-of-the art BSTs on most basic 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.
Type de document :
Communication dans un congrès
23rd International European Conference on Parallel and Distributed Computing - Euro-Par 2017, Aug 2017, Santiago de Compostella, Spain
Liste complète des métadonnées

https://hal.inria.fr/hal-01664898
Contributeur : Vitalii Aksenov <>
Soumis le : vendredi 15 décembre 2017 - 12:23:36
Dernière modification le : jeudi 26 avril 2018 - 10:27:54

Lien texte intégral

Identifiants

  • HAL Id : hal-01664898, version 1
  • ARXIV : 1702.04441

Collections

Citation

Vitalii Aksenov, Vincent Gramoli, Petr Kuznetsov, Anna Malova, Srivatsan Ravi. A Concurrency-Optimal Binary Search Tree. 23rd International European Conference on Parallel and Distributed Computing - Euro-Par 2017, Aug 2017, Santiago de Compostella, Spain. 〈hal-01664898〉

Partager

Métriques

Consultations de la notice

97