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.**