CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Efficient lock-free binary search trees

Bapi Chatterjee (Institutionen för data- och informationsteknik, Nätverk och system, Datakommunikation och distribuerade system (Chalmers)) ; Nhan Nguyen Dang (Institutionen för data- och informationsteknik, Nätverk och system (Chalmers) ) ; Philippas Tsigas (Institutionen för data- och informationsteknik, Nätverk och system (Chalmers) )
2014 ACM Symposium on Principles of Distributed Computing, PODC 2014; Paris; France; 15 July 2014 through 18 July 2014 p. 322-331. (2014)
[Konferensbidrag, refereegranskat]

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.

Nyckelord: Amortized analysis , Binary search tree , CAS , Concurrent data-structures , Lock-free , Shared memory



Denna post skapades 2014-08-22.
CPL Pubid: 201838

 

Läs direkt!


Länk till annan sajt (kan kräva inloggning)