E-Locus - Institutional Repository of the University of Crete

Home Collections School/Department School of Sciences and Engineering Department of Computer Science Post-graduate theses

Post-graduate theses

Current Record: 152 of 824

[Add to Basket]

Identifier

000428263

Title

Concurrent lock-free binary search tree implementations with range query support

Alternative Title

Ταυτόχρονα προσπελάσιμες υλοποιήσεις δυαδικών δένδρων αναζήτησης που υποστηρίζουν επερωτήσεις εύρους τιμών

Author

Παπαβασιλείου, Ηλίας Β.

Thesis advisor

Φατούρου, Παναγιώτα

Reviewer

Μαρκάτος, Ευάγγελος
Μαγκούτης, Κώστας

Abstract

In this thesis, we study concurrent binary search tree implementations that support range queries. Specifically, we present BPNB-BST, the first algorithm that supports wait-free range-queries in addition to lock-free Insert, Delete and Find, and has comparable performance to other state-of-the-art algorithms. Moreover, previous implementations provide the weaker progress guarantees of lock-freedom or obstruction freedom for range queries, whereas BPNB-BST guarantees wait-freedom. The distinction between lock-freedom and wait-freedom is important for time consuming operations such as range queries, because without strong progress guarantees such operations may starve. BPNB-BST is linearizable, uses single-word compare-and-swap operations, and tolerates any number of crash failures. Additionally, in BPNB-BST: (1) update operations work in an independent way interfering with one another only if they work on the same neighborhood of the tree, (2) the helping mechanism employed by the algorithm to guarantee its strong progress guarantees is lightweight, and (3) the algorithm works in a dynamic environment where threads may dynamically join or leave the system. We have performed a detailed experimental analysis which shows that BPNB-BST scales best with range query size, compared to other state-of-the-art implementations. Our experimental analysis reveals the performance properties of BPNB-BST, as well as interesting trade-offs between the different algorithms. Our experiments have heavily driven the optimizations we applied to our algorithm to make it exhibit such a good performance.

Language

English

Subject

Concurrency

Data structures

Δένδρα

Δομές δεδομένων

Ταυτόχρονη προσπέλαση

Issue date

2019-07-26

Collection

School/Department--School of Sciences and Engineering--Department of Computer Science--Post-graduate theses