Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

York University

$24,000.00

Algorithms and models for distributed systems

EF 2013-14

Résumé
For the past 40 years, computer equipment has been steadily growing smaller and faster. Now, however, we are approaching fundamental physical limits that will prevent these improvements from continuing at the same pace. In the future, the way to obtain more computational power will be increased parallelism: computer code will be executed by many ""threads"" simultaneously and cooperatively to solve a single problem. In 2005, Sutter and Larus announced the ""concurrency revolution."" They wrote that concurrency will start to play a central role in software development in the near future due to the shift in computer architecture from uniprocessors to multicore processors, which are designed specifically to run many threads on a single chip. The hardware industry has started to invest seriously in the development of multicore processors. Machineswith eight 12-core processors (capable of running 192 threads) will soon be available. Unfortunately, most algorithms designed for uniprocessor systems do not perform well in multicore systems. New techniques are required to design distributed algorithms that take full advantage of the system's parallel capabilities. This is one of the central challenges in the field of computer science today. The main goal of my research is to design and study algorithms in multicore systems for manipulating data structures. (Data structures are the abstract objects that computers use to store and manipulate information.) It is particularly challenging to design data structures that can be accessed and updated by many threads simultaneously: it is difficult to read a data structure while other threads are changing it, and it is still more challenging to maintain consistency of the data when multiple threads update the data structure simultaneously. This work will be complemented by some more theoretical work on complexity lower bounds in distributed computing, and on the impact of anonymity in distributed systems (motivated by scenarios where it is difficult to assign unique identifiers to the processes in a distributed system, or where the processes do not wish to reveal their identities for privacy concerns).
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
228091-2011
Name nom
Ruppert, Eric
Department département
Computer Science and Engineering
Organization id
38
Institution établissement
York University
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2013
Competition year année de concours
2011
Award amount
24000
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
Algorithms and models for distributed systems
Keyword
NSERC
Application summary
For the past 40 years, computer equipment has been steadily growing smaller and faster. Now, however, we are approaching fundamental physical limits that will prevent these improvements from continuing at the same pace. In the future, the way to obtain more computational power will be increased parallelism: computer code will be executed by many ""threads"" simultaneously and cooperatively to solve a single problem. In 2005, Sutter and Larus announced the ""concurrency revolution."" They wrote that concurrency will start to play a central role in software development in the near future due to the shift in computer architecture from uniprocessors to multicore processors, which are designed specifically to run many threads on a single chip. The hardware industry has started to invest seriously in the development of multicore processors. Machineswith eight 12-core processors (capable of running 192 threads) will soon be available. Unfortunately, most algorithms designed for uniprocessor systems do not perform well in multicore systems. New techniques are required to design distributed algorithms that take full advantage of the system's parallel capabilities. This is one of the central challenges in the field of computer science today. The main goal of my research is to design and study algorithms in multicore systems for manipulating data structures. (Data structures are the abstract objects that computers use to store and manipulate information.) It is particularly challenging to design data structures that can be accessed and updated by many threads simultaneously: it is difficult to read a data structure while other threads are changing it, and it is still more challenging to maintain consistency of the data when multiple threads update the data structure simultaneously. This work will be complemented by some more theoretical work on complexity lower bounds in distributed computing, and on the impact of anonymity in distributed systems (motivated by scenarios where it is difficult to assign unique identifiers to the processes in a distributed system, or where the processes do not wish to reveal their identities for privacy concerns).