Sökning: id:"swepub:oai:research.chalmers.se:38028b4d-3c44-44d9-b291-5f3558cf7846" >
Efficient lock-free...
Efficient lock-free binary search trees
-
- Chatterjee, Bapi, 1982 (författare)
- Chalmers tekniska högskola,Chalmers University of Technology
-
- Nguyen, Dang Nhan, 1983 (författare)
- Chalmers tekniska högskola,Chalmers University of Technology
-
- Tsigas, Philippas, 1967 (författare)
- Chalmers tekniska högskola,Chalmers University of Technology
-
(creator_code:org_t)
- 2014-07-15
- 2014
- Engelska.
-
Ingår i: 2014 ACM Symposium on Principles of Distributed Computing, PODC 2014; Paris; France; 15 July 2014 through 18 July 2014. - New York, NY, USA : ACM. - 9781450329446 ; , s. 322-331
- Relaterad länk:
-
http://dx.doi.org/10...
-
visa fler...
-
http://arxiv.org/pdf...
-
https://research.cha...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- In this paper we present a novel algorithm for concurrent lock-free internal binary search trees (BST) and implement a Set abstract data type (ADT) based on that. We show that in the presented lock-free BST algorithm the amortized step complexity of each set operation - ADD, REMOVE and CONTAINS - is O(H(n) + c), where H(n) is the height of the BST with n number of nodes and c is the contention during the execution. Our algorithm adapts to contention measures according to read-write load. If the situation is read-heavy, the operations avoid helping the concurrent REMOVE operations during traversal, and adapt to interval contention. However, for the write-heavy situations we let an operation help a concurrent REMOVE, even though it is not obstructed. In that case, an operation adapts to point contention. It uses single-word compare-and-swap (CAS) operations. We show that our algorithm has improved disjoint-access-parallelism compared to similar existing algorithms. We prove that the presented algorithm is linearizable. To the best of our knowledge, this is the first algorithm for any concurrent tree datastructure in which the modify operations are performed with an additive term of contention measure.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Nyckelord
- Lock-free
- Amortized analysis
- Binary search tree
- Concurrent data-structures
- CAS
- Shared memory
Publikations- och innehållstyp
- kon (ämneskategori)
- ref (ämneskategori)
Hitta via bibliotek
Till lärosätets databas