Top

Published in:

2017 | OriginalPaper | Chapter

A Concurrency-Optimal Binary Search Tree

Authors : Vitaly Aksenov, Vincent Gramoli, Petr Kuznetsov, Anna Malova, Srivatsan Ravi

Published in: Euro-Par 2017: Parallel Processing

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Efficient Non-blocking Radix Trees

next chapter Scalable Fine-Grained Metric-Based Remeshing Algorithm for Manycore/NUMA Architectures

Herlihy, M.: Wait-free synchronization. ACM Trans. Program. Lang. Syst. 13(1), 123–149 (1991)CrossRef

Gramoli, V., Kuznetsov, P., Ravi, S.: In the search for optimal concurrency. In: Suomela, J. (ed.) SIROCCO 2016. LNCS, vol. 9988, pp. 143–158. Springer, Cham (2016). doi:10.1007/978-3-319-48314-6_10 CrossRef

Papadimitriou, C.H.: The serializability of concurrent database updates. J. ACM 26, 631–653 (1979)MathSciNetCrossRefMATH

Chaudhri, V.K., Hadzilacos, V.: Safe locking policies for dynamic databases. J. Comput. Syst. Sci. 57(3), 260–271 (1998)MathSciNetCrossRefMATH

Sutter, H.: Choose concurrency-friendly data structures. Dr. Dobb’s J. (2008)

Heller, S., Herlihy, M., Luchangco, V., Moir, M., Scherer, W.N., Shavit, N.: A lazy concurrent list-based set algorithm. In: OPODIS, pp. 3–16 (2006)

Herlihy, M., Shavit, N.: On the nature of progress. In: OPODIS, pp. 313–328 (2011)

Guerraoui, R., Henzinger, T.A., Singh, V.: Permissiveness in transactional memories. In: DISC, pp. 305–319 (2008)

Kuznetsov, P., Ravi, S.: On the cost of concurrency in transactional memory. In: International Conference on Principles of Distributed Systems (OPODIS), pp. 112–127 (2011)

10.

Crain, T., Gramoli, V., Raynal, M.: A contention-friendly binary search tree. In: Wolf, F., Mohr, B., Mey, D. (eds.) Euro-Par 2013. LNCS, vol. 8097, pp. 229–240. Springer, Heidelberg (2013). doi:10.1007/978-3-642-40047-6_25 CrossRef

11.

Drachsler, D., Vechev, M., Yahav, E.: Practical concurrent binary search trees via logical ordering. In: Proceedings of 19th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2014, pp. 343–356 (2014)

12.

Bronson, N.G., Casper, J., Chafi, H., Olukotun, K.: A practical concurrent binary search tree. In: PPoPP (2010)

13.

Ellen, F., Fatourou, P., Ruppert, E., van Breugel, F.: Non-blocking binary search trees. In: PODC, pp. 131–140 (2010)

14.

Aksenov, V., Gramoli, V., Kuznetsov, P., Malova, A., Ravi, S.: A concurrency-optimal binary search tree. CoRR abs/1702.04441 (2017)

15.

Natarajan, A., Mittal, N.: Fast concurrent lock-free binary search trees. In: PPoPP, pp. 317–328 (2014)

16.

Gramoli, V.: More than you ever wanted to know about synchronization: Synchrobench, measuring the impact of the synchronization on concurrent algorithms. In: PPoPP, pp. 1–10 (2015)

17.

Gramoli, V., Kuznetsov, P., Ravi, S.: From sequential to concurrent: correctness and relative efficiency (brief announcement). In: Principles of Distributed Computing (PODC), pp. 241–242 (2012)

18.

Gramoli, V., Kuznetsov, P., Ravi, S., Shang, D.: A concurrency-optimal list-based set (brief announcement). In: Distributed Computing - 29th International Symposium, DISC 2015, Tokyo, Japan, 7–9 October 2015

19.

Cao Minh, C., Chung, J., Kozyrakis, C., Olukotun, K.: STAMP: Stanford transactional applications for multi-processing. In: IISWC (2008)

20.

Crain, T., Gramoli, V., Raynal, M.: A speculation-friendly binary search tree. In: PPoPP, pp. 161–170 (2012)

21.

Siakavaras, D., Nikas, K., Goumas, G., Koziris, N.: Performance analysis of concurrent red-black trees on HTM platforms. In: 10th ACM SIGPLAN Workshop on Transactional Computing (Transact) (2015)

22.

Howley, S.V., Jones, J.: A non-blocking internal binary search tree. In: SPAA, pp. 161–171 (2012)

23.

Chatterjee, B., Nguyen, N., Tsigas, P.: Efficient lock-free binary search trees. In: PODC (2014)

Title: A Concurrency-Optimal Binary Search Tree
Authors: Vitaly Aksenov
Vincent Gramoli
Petr Kuznetsov
Anna Malova
Srivatsan Ravi
Publisher: Springer International Publishing
Book: Euro-Par 2017: Parallel Processing
Print ISBN: 978-3-319-64202-4

Electronic ISBN: 978-3-319-64203-1

Copyright Year: 2017
DOI: https://doi.org/10.1007/978-3-319-64203-1_42

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner