Award Date

12-1-2017

Degree Type

Thesis

Degree Name

Master of Science in Computer Science

Department

Computer Science

First Committee Member

Ajoy K. Datta

Second Committee Member

John Minor

Third Committee Member

Wolfgang Bein

Fourth Committee Member

Emma E. Regentova

Fifth Committee Member

Kumud Acharya

Number of Pages

59

Abstract

A binary search tree (BST) is a fundamental data structure for maintaining data in a way to allow fast search. As multi-core processors are widely used nowadays, such data structures require the ability to handle concurrent accesses to exploit the concurrent hardware. There are several algorithms on lock-based as well as lock-free BST with and without self-balancing. On the other hand, only a few reports can be found on lock-based self-adjusting BST. To the best of our knowledge, there are no algorithms for lock-free self-adjusting BST. Lock-free guarantees overall progress even if some processes fail, whereas lock-based algorithms fail to progress in the case of a faulty process. In this study, a lock-free self-adjusting binary search tree is proposed using compare-and-swap (CAS) operations. The algorithm is based on lazy splaying which moves frequently accessed items near the root in a contention friendly manner. The algorithm will include search, delete, insert, and restructuring operations.

Keywords

BST; CAS; Lazy Splay; Non-blocking; Splay Tree

Disciplines

Computer Sciences

File Format

pdf

Degree Grantor

University of Nevada, Las Vegas

Language

English

Rights

IN COPYRIGHT. For more information about this rights statement, please visit http://rightsstatements.org/vocab/InC/1.0/

Download


Share

COinS