The goal of this research is to make it possible for parallel programs, running on asynchronous shared-memory multiprocessors, to share data flexibly, efficiently, and reliably. Specifically, the research seeks to develop algorithms for building system software that (1) make it easy to implement any shared data structure, (2) ensure that accesses to implemented shared data structures are fast, and (3) ensure that the implemented shared data structures are fault-tolerant. A wait-free implementation of a shared data structure ensures that the data structure remains accessible to correct processes even if some processes in the system crash. A universal construction is an algorithm that makes it easy to design a wait-free implementation of any shared data structure. To realize the goal stated in the previous paragraph, this research seeks a universal construction with low worst-case time complexity and strong parallelism: concurrent operations run in parallel even if they access common parts of the data structure, provided that the commonly accessed parts are only read, and not modified. Universal constructions often require strong synchronization operations, such as compare & swap. Porting these constructions to weaker architectures that do not support such operations is another objective of this research. A final objective is to understand the intrinsic limitations of universal constructions.
