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.
|School:||The University of Texas at Dallas|
|School Location:||United States -- Texas|
|Source:||MAI 48/05M, Masters Abstracts International|
Copyright in each Dissertation and Thesis is retained by the author. All Rights Reserved
The supplemental file or files you are about to download were provided to ProQuest by the author as part of a
dissertation or thesis. The supplemental files are provided "AS IS" without warranty. ProQuest is not responsible for the
content, format or impact on the supplemental file(s) on our system. in some cases, the file type may be unknown or
may be a .exe file. We recommend caution as you open such files.
Copyright of the original materials contained in the supplemental file is retained by the author and your access to the
supplemental files is subject to the ProQuest Terms and Conditions of use.
Depending on the size of the file(s) you are downloading, the system may take some time to download them. Please be