Master of Science in Computer Science
First Committee Member
Ajoy K. Datta
Second Committee Member
Ajoy K. Datta
Third Committee Member
Fourth Committee Member
Fifth Committee Member
Number of Pages
A splay tree is a self-adjusting binary search tree in which recently accessed elements are quick to access again. Splay operation causes the sequential bottleneck at the root of the tree in concurrent environment. The Lazy splaying is to rotate the tree at most one per access so that very frequently accessed item does full splaying. We present the RCU (Read-copy-update) based synchronization mechanism for splay tree operations which allows reads to occur concurrently with updates such as deletion and restructuring by splay rotation. This approach is generalized as relativistic programming. The relativistic programming is the programming technique for concurrent shared-memory architectures which tolerates different threads seeing events occurring in diﬀerent orders, so that events are not necessarily globally ordered, but rather subject to constraints of per-thread ordering.
The main idea of the algorithm is that the update operations are carried out concurrently
with traversals/reads. Each update is carried out for new reads to see the new state, while allowing pre-existing reads to proceed on the old state. Then the update is completed after all pre-existing reads have completed.
Concurrency; Data structures (Computer science); Read -copy-update; Relativistic programming; Splay Tree
Sedai, Jaya Ram, "Concurrent Lazy Splay Tree with Relativistic Programming Approach" (2015). UNLV Theses, Dissertations, Professional Papers, and Capstones. 2424.