Grant: Discovery Grants Program - Individual
University of Toronto
$128,000.00
Impossibility Results for Distributed Computing
EF 2024-25
Résumé
Distributed computing is concerned with processors that communicate with one another, either by passing messages to one another or by accessing shared memory. Processes may run at different speeds and some of them may fail. This makes it difficult to design distributed algorithms and prove them correct.
My research is concerned with showing that certain fundamental problems in distributed computing cannot be solved or require large amounts of resources (such as steps or shared memory locations) to be solved. An example of such a problem is consensus, where each process has a possibly different input value and the processes must agree on one of these values. It is impossible to solve deterministically if every process (that does not fail) must decide within a finite number of reads and writes of shared memory. With randomization, there are algorithms in which processes decide within an expected finite number of reads and writes, but they must use at least as many shared memory locations as processes. I recently proved, using a new technique, that no randomized algorithm for consensus can use fewer memory locations, closing a problem that had been open for more than 25 years. Using this technique, I also proved bounds on the number of memory locations needed for solving more general problems and using some more powerful operations than read and write. However, there are no known algorithms which achieve these bounds. I intend to refine my new technique or design other techniques to get better bounds, matching what existing algorithms can do. Such bounds can be used to classify the computational power of different operations.
The proof that there is no deterministic algorithm solving consensus with only reads and writes uses a simple and elegant technique called a valency argument. In contrast, the same result for a related problem, set agreement, was proved using sophisticated techniques from combinatorial topology. I recently proved that there is no proof of this result based on simpler techniques such as valency arguments. I plan to extend this work to show the limitations of these techniques for proving the impossibility of solving other problems and in other models. I also want to prove that standard techniques for proving bounds on the number of shared memory locations are not sufficient for problems such as set agreement.
Finally, I intend to study how the size of shared memory locations affects the number of shared memory locations needed to solve certain distributed computing problems.
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-2020-04178
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
2024
Competition year année de concours
2020
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
1200
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Advancement of knowledge
Area of application fr
Avancement des connaissances
Research subject code
2703
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Complexity
Research subject fr
Complexité
Field of research list names en
Not available
Field of research list names fr
Non disponible
Socioeconomic objective list names en
Not available
Socioeconomic objective list names fr
Non disponible
Application title
Impossibility Results for Distributed Computing
Keywords
asynchronous shared memory models; impossibility results; space complexity; randomized wait-freedom; obstruction-freedom; combinatorial topology
Application summary
Distributed computing is concerned with processors that communicate with one another, either by passing messages to one another or by accessing shared memory. Processes may run at different speeds and some of them may fail. This makes it difficult to design distributed algorithms and prove them correct.
My research is concerned with showing that certain fundamental problems in distributed computing cannot be solved or require large amounts of resources (such as steps or shared memory locations) to be solved. An example of such a problem is consensus, where each process has a possibly different input value and the processes must agree on one of these values. It is impossible to solve deterministically if every process (that does not fail) must decide within a finite number of reads and writes of shared memory. With randomization, there are algorithms in which processes decide within an expected finite number of reads and writes, but they must use at least as many shared memory locations as processes. I recently proved, using a new technique, that no randomized algorithm for consensus can use fewer memory locations, closing a problem that had been open for more than 25 years. Using this technique, I also proved bounds on the number of memory locations needed for solving more general problems and using some more powerful operations than read and write. However, there are no known algorithms which achieve these bounds. I intend to refine my new technique or design other techniques to get better bounds, matching what existing algorithms can do. Such bounds can be used to classify the computational power of different operations.
The proof that there is no deterministic algorithm solving consensus with only reads and writes uses a simple and elegant technique called a valency argument. In contrast, the same result for a related problem, set agreement, was proved using sophisticated techniques from combinatorial topology. I recently proved that there is no proof of this result based on simpler techniques such as valency arguments. I plan to extend this work to show the limitations of these techniques for proving the impossibility of solving other problems and in other models. I also want to prove that standard techniques for proving bounds on the number of shared memory locations are not sufficient for problems such as set agreement.
Finally, I intend to study how the size of shared memory locations affects the number of shared memory locations needed to solve certain distributed computing problems.