Grant: Discovery Grants Program - Individual
University of Calgary
$128,000.00
Design and Complexity of Distributed Algorithms
FY 2023-24
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 data structures such as concurrent dictionaries, and new implementations of strong synchronization primitives, e.g., multi-word compare-and-swap and snapshot objects. 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 algorithm design and analysis methods. The classical approach to allow no room for error may limit algorithm design, and can lead to inefficiencies. I will study concurrent Monte Carlo algorithms that may produce errors or faults in very rare cases, but perform better than their error-free counterparts. Related to that will be my study of the recently defined allocate-on-access space requirements of shared memory algorithms: Many fundamental problems are known to require a large amount of (memory or disk) space in the worst-case. But these worst-case scenarios may be very improbable. The significance of the worst-case space complexity is justified by an assumption that any space that is used in some execution must be allocated for all executions. This assumption is not consistent with the storage allocation mechanisms of actual practical systems. The allocate-on-access measure is a more realistic approach to measuring actual space usage on modern storage systems without being overly pessimistic. 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 Monte Carlo algorithms and the allocate-on-access space complexity will directly and indirectly yield new solutions to synchronization problems, and improve the performance of systems relying on such algorithms.
Program
Discovery Grants Program - Individual
Recipient
Location
Alberta, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2019-04852
Name nom
Woelfel, Philipp
Department département
Computer Science - 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
2023
Competition year année de concours
2019
Award amount
128000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR 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
2704
Research subject group en
Information technology
Research subject group fr
Distributed and parallel processing
Research subject en
Technologie de l'information
Research subject fr
Traitement réparti et simultané
Application title
Design and Complexity of Distributed Algorithms
Keyword
Asynchrony; Concurrency; Hashing; Monte Carlo algorithms; Randomized algorithms; Shared memory; Space complexity; Synchronization primitives
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 data structures such as concurrent dictionaries, and new implementations of strong synchronization primitives, e.g., multi-word compare-and-swap and snapshot objects. 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 algorithm design and analysis methods. The classical approach to allow no room for error may limit algorithm design, and can lead to inefficiencies. I will study concurrent Monte Carlo algorithms that may produce errors or faults in very rare cases, but perform better than their error-free counterparts. Related to that will be my study of the recently defined allocate-on-access space requirements of shared memory algorithms: Many fundamental problems are known to require a large amount of (memory or disk) space in the worst-case. But these worst-case scenarios may be very improbable. The significance of the worst-case space complexity is justified by an assumption that any space that is used in some execution must be allocated for all executions. This assumption is not consistent with the storage allocation mechanisms of actual practical systems. The allocate-on-access measure is a more realistic approach to measuring actual space usage on modern storage systems without being overly pessimistic. 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 Monte Carlo algorithms and the allocate-on-access space complexity will directly and indirectly yield new solutions to synchronization problems, and improve the performance of systems relying on such algorithms.