Master of Science in Computer Science
First Committee Member
Ajoy K. Datta
Second Committee Member
Third Committee Member
Fourth Committee Member
Number of Pages
A red-black tree is a type of self-balancing binary search tree. Some wait-free algorithms have been proposed for concurrently accessing and modifying a red-black tree from multiple threads in shared memory systems. Most algorithms presented utilize the concept of a "window", and are entirely top-down implementations. Top-down algorithms like these have to operate on large portions of the tree, and operations on nodes that would otherwise not overlap at all still have to compete with and help one another.
A wait-free framework is proposed for obtaining ownership of small portions of the tree at a time in a bottom-up manner. This approach allows operations interested in completely disparate portions of the tree to execute entirely uninhibited. Insert and search operations on a red-black tree are shown, and the different use cases explained.
Balanced Tree; Compare and Set; Computer algorithms; Computer multitasking; Concurrency; Decision trees; Java Atomic; Red Black Tree; Wait Free
Computer Sciences | Theory and Algorithms
Kubushyn, Vitaliy, "Concurrent Localized Wait-Free Operations on a Red Black Tree" (2014). UNLV Theses, Dissertations, Professional Papers, and Capstones. 2278.