Anupriya MS Project Defense

Tuesday, May 28, 2019 - 1:00pm to 2:00pm
HFH 1132
Concurrent Lock-free Red Black Tree
Divyakant Agrawal (Chair), Amr El Abbadi


With the proliferation of multi-core, multi-processor systems, concurrent data structures capable of supporting several processes are a growing need. Concurrency is most often managed through locks but such lock-based data structures are vulnerable to problems such as deadlock, synchronization overheads and scheduling anomalies. Non-blocking algorithms avoid drawbacks of locks by using hardware-supported synchronization primitives. In this talk, I intend to present a lock-free algorithm for concurrently accessing a red-black tree in an asynchronous shared memory system that supports search, insert and delete operations using compare-and-swap (CAS) instructions. This algorithm is built upon the sequential implementation of red-black tree with the addition of a "local area" concept and it performs the rebalancing of modified tree in a bottom-up fashion. Based on my implementation and experiment results, this variant of lock-free algorithm significantly outperforms the sequential redblack tree.

Everyone welcome!