Grant: Discovery Grants Program - Individual
University of Calgary
$54,000.00
Algorithms and Complexity of Distributed Computation
EF 2016-17
Résumé
Distributed computing systems ranging from simple desktop PCs or even cell phones with multi-core CPUs to high-performance computer clusters and systems ""in-the-cloud"" have to deal with problems that arise from concurrency, asynchrony, and failures. In these settings, the design of time and space efficient algorithms, proof of their correctness, and analysis of their complexity are challenging tasks. Algorithms and data structures for fundamental tasks in distributed systems are critical for the future development of efficient and fault-tolerant software. Lower bounds and impossibility results can guide researchers and software developers in their efforts to build efficient software systems, and can help hardware designers to decide what hardware primitives are needed.
In my research program I will devise new efficient algorithms and data structures for shared memory systems. I will try to find solutions for fundamental problems such as mutual exclusion, consensus, or the efficient and randomized implementation of strong primitives (e.g., compare-and-swap) from weaker ones. I will complement new algorithms with proofs of lower bounds in order to determine the time and space complexity of these problems.
I will also investigate new methods for measuring the quality of randomized and deterministic shared memory algorithms and the complexity of problems. The classical worst-case analysis is often too pessimistic to predict the actual performance of programs in practice, and sometimes leads to complicated algorithms. Therefore, novel ways of theoretically predicting the performance of algorithms need to be developed and evaluated.
Results of this research program will yield a better understanding of the system requirements of synchronization problems. Algorithms resulting from the research can be used as building blocks in software development, and lower bounds can help software and hardware developers making design decisions. Research on novel analytical performance measures for shared memory algorithms will directly and indirectly yield new solutions to synchronization problems, and improve the performance of systems relying on synchronization algorithms.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Alberta, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
RGPIN-2014-04739
Name nom
Woelfel, Philipp
Department département
Computer Science
Organization id
11
Institution établissement
University of Calgary
Province en
Alberta
Province fr
Alberta
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2016
Competition year année de concours
2014
Award amount
54000
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
1207
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Information, computer and communication technologies
Area of application fr
Technologie de l'information, des ordinateurs et des réseaux de communications
Research subject code
2712
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Theory of computation
Research subject fr
Théorie de calcul
Partie
3
Nb partie
5
Application title
Algorithms and Complexity of Distributed Computation
Keyword
NSERC
Application summary
Distributed computing systems ranging from simple desktop PCs or even cell phones with multi-core CPUs to high-performance computer clusters and systems ""in-the-cloud"" have to deal with problems that arise from concurrency, asynchrony, and failures. In these settings, the design of time and space efficient algorithms, proof of their correctness, and analysis of their complexity are challenging tasks. Algorithms and data structures for fundamental tasks in distributed systems are critical for the future development of efficient and fault-tolerant software. Lower bounds and impossibility results can guide researchers and software developers in their efforts to build efficient software systems, and can help hardware designers to decide what hardware primitives are needed.
In my research program I will devise new efficient algorithms and data structures for shared memory systems. I will try to find solutions for fundamental problems such as mutual exclusion, consensus, or the efficient and randomized implementation of strong primitives (e.g., compare-and-swap) from weaker ones. I will complement new algorithms with proofs of lower bounds in order to determine the time and space complexity of these problems.
I will also investigate new methods for measuring the quality of randomized and deterministic shared memory algorithms and the complexity of problems. The classical worst-case analysis is often too pessimistic to predict the actual performance of programs in practice, and sometimes leads to complicated algorithms. Therefore, novel ways of theoretically predicting the performance of algorithms need to be developed and evaluated.
Results of this research program will yield a better understanding of the system requirements of synchronization problems. Algorithms resulting from the research can be used as building blocks in software development, and lower bounds can help software and hardware developers making design decisions. Research on novel analytical performance measures for shared memory algorithms will directly and indirectly yield new solutions to synchronization problems, and improve the performance of systems relying on synchronization algorithms.