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