Efficient Concurrent Data Structures

数据结构是一种在计算机中组织特定信息的方法，以及访问和更新该信息的方法。并发数据结构是可由多个进程同时访问的数据结构。并发数据结构库使并发软件的设计变得非常容易。*这项研究关注的是高效、可证明正确的并发数据结构的设计，特别是那些即使进程在访问它们时崩溃也能继续正确工作的数据结构。一些数据结构是标准顺序数据结构的并发版本，例如搜索树。另一些则被定义为帮助进程彼此同步。例如，原子快照对象允许进程更新数组的一个条目或同时拍摄其所有条目的快照。*这项研究的一个方面是开发使正确和高效的并发数据结构的设计变得更容易的方法。我们已经开发了一种创建一大类并发的基于树的数据结构的技术，并证明了使用该技术创建的任何数据结构都是自动正确和容错的。我们正在努力将其扩展到其他类的并发数据结构。并发数据结构的一个大问题是如何回收不再使用的空间。我们正在研究改进现有机制的方法，并正在开发新的机制，这些机制可以很好地处理使用我们的技术设计的并发数据结构。*这项研究的另一个方面是证明特定并发数据结构所需的资源量(如时间或空间)的下界。这使我们能够确定数据结构何时是最佳的。它还可以帮助我们找到提高性能的创新方法。**

A data structure is a way to organize certain information in a computer, together with methods for accessing and updating that information. Concurrent data structures are data structures that can be accessed by many processes at the same time. Libraries of concurrent data structures make the design of concurrent software substantially easier.******This research is concerned with the design of efficient, provably correct, concurrent data structures, especially ones that continue to work correctly even if processes crash while accessing them. Some of the data structures are concurrent versions of standard sequential data structures, such as search trees. Others have been defined to help processes synchronize with one another. For example, an atomic snapshot object allows a process to update one entry of an array or take a snapshot of all its entries at the same time. ******One aspect of this research is to develop ways to make the design of correct and efficient concurrent data structures easier. We have developed a technique for creating a large class of concurrent tree-based data structures and proved that any data structure created using this technique is automatically correct and fault-tolerant. We are working on extending it to other classes of concurrent data structures. A big issue for concurrent data structures is how to reclaim space that is no longer being used. We are studying ways of improving existing mechanisms and are developing new mechanisms that work well with concurrent data structures designed using our technique.******Another aspect of this research is to prove lower bounds on the amount of a resource (such as time or space) needed for specific concurrent data structures. This enables us to determine when a data structure is optimal. It can also help us find innovative ways to improve performance.**