Dissertation/Thesis Abstract

Wait-free balanced search trees with fast readers
by Savoie, Lee Hilton, M.S., The University of Texas at Dallas, 2009, 1; 1484464
Abstract (Summary)

Traditional parallel algorithms use mutual exclusion locks to manage contention among multiple processes. More recently, new hardware instructions have been used to produce non-blocking algorithms that do not rely on mutual exclusion to manage contention. Of these, wait-free algorithms provide the strongest guarantees, because every process is guaranteed to complete its operation in finite time, regardless of the progress or even failure of contending processes. However, wait-free data structures are difficult to design, and few wait free algorithms have been published. In this paper, we discuss how many kinds of wait-free balanced search trees can be produced using existing algorithms with an existing framework. In addition, we provide a new reader algorithm for these trees that eliminates contention between readers and other processes and considerably reduces overhead for readers. As a result, our reader algorithm is much faster and much simpler compared to the original design.

Indexing (document details)
Advisor: Mittal, Neeraj
School: The University of Texas at Dallas
School Location: United States -- Texas
Source: MAI 48/05M, Masters Abstracts International
Subjects: Computer science
Publication Number: 1484464
ISBN: 9781109726114