A goal of this project is to develop a systematic understanding of the theory and practice of highly concurrent data objects. The need for such an understanding has become compelling as technological advances have made multiprocessor machines readily available. Despite impressive progress at the hardware level, there is little agreement on the relative merits of competing architectures, and it has often proved difficult to realize these machines' potential for parallelism. These difficulties are compounded when application requirements include fault-tolerance or real-time performance. The PI's prior work had made significant contributions to the theory of highly concurrent data structures by exploiting the theory of abstract data types to derive (1) impossibility results, showing that certain kinds of concurrency simply cannot be achieved with certain primitives; (2) new techniques for specifying and reasoning about the behavior of concurrent objects, and (3) synchronization algorithms permitting high degrees of concurrency never before achieved. The resulting theory has a rich mathematical structure, yielding a number of unexpected results with consequences for algorithm design, implications of these results are poorly understood. A principal objective of this project is to undertake experimental work to translate theoretical results into practice.
