Grant: Discovery Grants Program - Individual
University of Toronto
$29,000.00
On Principles of Distributed Computing for Message-Passing, Shared-Memory, and Hybrid Systems
EF 2022-23
Résumé
The long term objective of this research is to study fundamental problems in distributed computing, the area of computer science addressing the problems that arise when a set of communicating processes cooperate to carry out jointly a computational task. As in our previous work, our research will focus on the two central concerns of distributed computing: synchronization, which ensures that processes do not impede each other as they access shared resources, and fault-tolerance, which ensures that the system continues to work correctly even if some of its components fail. The proposed research will encompass message-passing systems, where processes communicate by exchanging messages, shared-memory systems, where processes communicate by accessing shared objects, and also hybrid systems where processes can both exchange messages and share memory. This research is primarily theoretical but it is motivated by practical problems and considerations. Some anticipated results are expected to have direct applications. As part of this research, we plan to investigate new liveness and fairness requirements for shared objects. Intuitively, liveness guarantees that (some or all) processes that access a shared object get a response from the object within a bounded time, and fairness ensures that the number of operations that each process is able to complete on a shared object is proportional to its relative speed. In particular, we will explore a new parametrized liveness property which ensures that, for every object operation type T, at least k processes accessing an object by applying operations of type T are guaranteed to make progress. The goal is to derive algorithms for implementing objects that satisfy this property and are also fair. We also plan to explore the use of highly synchronized external clocks (e.g., GPS clocks) to solve problems efficiently in systems that are otherwise partially asynchronous. Our starting point is an efficient algorithm that uses such clocks to maintain highly-consistent object replicas (such as data stores) in geographically distributed message-passing systems that are prone to failures. We will investigate how the clock-based techniques that we used in this algorithm can be applied to solve other problems efficiently. We also want to understand the limitation of such clock-equipped systems by deriving performance lower bounds. Motivated by technological advances, we also aim to solve problems and obtain performance lower bounds for hybrid systems where processes can both exchange messages and share memory. To do so we plan to extend our recent work where we solved some fundamental problems, including consensus, in such systems. These solutions are optimal in the sense that they tolerate the maximum number of process crashes possible. Our goal is to increase the fault-tolerance of our solutions by tolerating additional types of process failures, and also by tolerating failures of the shared objects they access.
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-2022-03304
Name nom
Toueg, Sam
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
2022
Competition year année de concours
2022
Award amount
29000
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
2700
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Information technology
Research subject fr
Technologie de l'information
Installment
inst:1
Partie
1
Nb partie
5
Application title
On Principles of Distributed Computing for Message-Passing, Shared-Memory, and Hybrid Systems
Application summary
The long term objective of this research is to study fundamental problems in distributed computing, the area of computer science addressing the problems that arise when a set of communicating processes cooperate to carry out jointly a computational task. As in our previous work, our research will focus on the two central concerns of distributed computing: synchronization, which ensures that processes do not impede each other as they access shared resources, and fault-tolerance, which ensures that the system continues to work correctly even if some of its components fail. The proposed research will encompass message-passing systems, where processes communicate by exchanging messages, shared-memory systems, where processes communicate by accessing shared objects, and also hybrid systems where processes can both exchange messages and share memory. This research is primarily theoretical but it is motivated by practical problems and considerations. Some anticipated results are expected to have direct applications. As part of this research, we plan to investigate new liveness and fairness requirements for shared objects. Intuitively, liveness guarantees that (some or all) processes that access a shared object get a response from the object within a bounded time, and fairness ensures that the number of operations that each process is able to complete on a shared object is proportional to its relative speed. In particular, we will explore a new parametrized liveness property which ensures that, for every object operation type T, at least k processes accessing an object by applying operations of type T are guaranteed to make progress. The goal is to derive algorithms for implementing objects that satisfy this property and are also fair. We also plan to explore the use of highly synchronized external clocks (e.g., GPS clocks) to solve problems efficiently in systems that are otherwise partially asynchronous. Our starting point is an efficient algorithm that uses such clocks to maintain highly-consistent object replicas (such as data stores) in geographically distributed message-passing systems that are prone to failures. We will investigate how the clock-based techniques that we used in this algorithm can be applied to solve other problems efficiently. We also want to understand the limitation of such clock-equipped systems by deriving performance lower bounds. Motivated by technological advances, we also aim to solve problems and obtain performance lower bounds for hybrid systems where processes can both exchange messages and share memory. To do so we plan to extend our recent work where we solved some fundamental problems, including consensus, in such systems. These solutions are optimal in the sense that they tolerate the maximum number of process crashes possible. Our goal is to increase the fault-tolerance of our solutions by tolerating additional types of process failures, and also by tolerating failures of the shared objects they access.