Grant: Discovery Grants Program - Individual
University of Toronto
$50,000.00
Efficient Concurrent Data Structures
EF 2017-18
Résumé
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.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
RGPIN-2015-05080
Name nom
Ellen, Faith
Department département
Computer Science (St. George Campus) - Computer Science (St. George Campus)
Organization id
31
Institution établissement
University of Toronto
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2017
Competition year année de concours
2015
Award amount
50000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
801
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Computer software
Area of application fr
Logiciel
Research subject code
2704
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Distributed and parallel processing
Research subject fr
Traitement réparti et simultané
Partie
3
Nb partie
5
Application title
Efficient Concurrent Data Structures
Keyword
NSERC
Application summary
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.