Highly Concurrent Objects

这个项目的目标是系统地理解高度并发数据对象的理论和实践。随着技术进步使得多处理器机器随时可用，对这种理解的需求变得越来越迫切。尽管在硬件层面上取得了令人印象深刻的进步，但人们对相互竞争的体系结构的相对优点几乎没有达成一致，而且通常很难实现这些机器的并行性潜力。当应用程序要求包括容错或实时性能时，这些困难就变得更加复杂了。PI先前的工作对高度并发数据结构理论做出了重大贡献，通过利用抽象数据类型理论推导出(1)不可能结果，表明某些类型的并发性根本无法用某些原语实现；(2)对并发对象的行为进行指定和推理的新技术，以及(3)允许以前从未实现过的高度并发的同步算法。由此产生的理论具有丰富的数学结构，产生了许多意想不到的结果，并对算法设计产生了影响，但这些结果的含义却鲜为人知。该项目的一个主要目标是进行实验工作，将理论结果转化为实践。

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.