Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

University of Toronto

$39,000.00

Algorithms, abstractions and models for distributed computing.

FY 2016-17

Summary
We plan to work on fundamental problems, abstractions and models in distributed computing. This research will encompass both message-passing models (which are suited to geographically distributed systems such as peer-to-peer, mobile, or cloud systems) and shared-memory models (which are suited to multicore systems). One goal is to derive better algorithms and abstractions that simplify the design or improve the performance of distributed systems. Another goal is to compare, and where possible unify, some of the many models and related results in this area. We now briefly summarize some of the proposed work towards these goals. Linearizable wait-free shared objects are a powerful abstraction for building asynchronous shared-memory distributed systems: they behave as if they are accessed sequentially, and every non-faulty process that invokes an operation on a wait-free object is guaranteed to get a response even if other processes are slow or crash. Implementing such objects, however, can be difficult and inefficient, and this has led to the study of objects that have weaker (though still useful) semantics but have easier and more efficient implementations. In this vein, we propose to continue our work on abortable objects, i.e., objects where operations that interfere with each other may abort without taking effect. This is reminiscent of the simple and attractive behaviour of transactional memory, database transactions, and abortable mutual exclusion --- techniques in which a process can, under contention, ``bail out'' of the computation without leaving a trace. Our preliminary work on abortable objects showed that abortable objects are inherently different from ordinary ones and need to be studied on their own. We propose to continue this work to better understand abortable objects, and to compare them to ordinary (i.e., non-abortable) objects in terms of power and implementation efficiency. Several fundamental problems that cannot be solved in fully asynchronous systems with failures can be solved in systems with additional properties, such as partial synchrony, failure detection, and fair schedulers. Recent research suggests that many of these systems are closely related (e.g., several failure detectors have been shown to be equivalent to fair schedulers) but considerable work remains to be done to better understand their similarities and differences. We will continue to investigate and compare these systems in an effort to unify and better understand the many models and results in the area. In many distributed systems, some strong assumptions, e.g., that processes are synchronous and do not crash, can hold for relatively long periods of time. Furthermore, algorithms that make such strong assumptions can be very efficient, but they may fail in the relatively rare cases when these assumptions are violated. To take advantage of this, one can first run a ``primary'' algorithm that is very efficient because it relies on strong assumptions, and then, in the rare cases when the primary algorithm fails, fall back on a less efficient ``backup'' algorithm that relies on weaker assumptions; this is the basic idea of ``speculative computing''. In preliminary work based on this approach, we derived speculative algorithms for the fundamental problem of consensus in systems with process crash failures. We propose to extend and generalize this initial work in several directions, for example to solve problems other than consensus, to tolerate more than just crash failures, and to investigate the efficient implementation of shared objects based on speculative computing.
Program
Discovery Grants Program - Individual
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
RGPIN-2014-05296
Name nom
Toueg, Sam
Department département
Computer Science
Organization id
31
Institution établissement
University of Toronto
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2016
Competition year année de concours
2014
Award amount
39000
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
2713
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Algorithms
Research subject fr
Algorithmes
Partie
3
Nb partie
5
Application title
Algorithms, abstractions and models for distributed computing.
Keyword
NSERC
Application summary
We plan to work on fundamental problems, abstractions and models in distributed computing. This research will encompass both message-passing models (which are suited to geographically distributed systems such as peer-to-peer, mobile, or cloud systems) and shared-memory models (which are suited to multicore systems). One goal is to derive better algorithms and abstractions that simplify the design or improve the performance of distributed systems. Another goal is to compare, and where possible unify, some of the many models and related results in this area. We now briefly summarize some of the proposed work towards these goals. Linearizable wait-free shared objects are a powerful abstraction for building asynchronous shared-memory distributed systems: they behave as if they are accessed sequentially, and every non-faulty process that invokes an operation on a wait-free object is guaranteed to get a response even if other processes are slow or crash. Implementing such objects, however, can be difficult and inefficient, and this has led to the study of objects that have weaker (though still useful) semantics but have easier and more efficient implementations. In this vein, we propose to continue our work on abortable objects, i.e., objects where operations that interfere with each other may abort without taking effect. This is reminiscent of the simple and attractive behaviour of transactional memory, database transactions, and abortable mutual exclusion --- techniques in which a process can, under contention, ``bail out'' of the computation without leaving a trace. Our preliminary work on abortable objects showed that abortable objects are inherently different from ordinary ones and need to be studied on their own. We propose to continue this work to better understand abortable objects, and to compare them to ordinary (i.e., non-abortable) objects in terms of power and implementation efficiency. Several fundamental problems that cannot be solved in fully asynchronous systems with failures can be solved in systems with additional properties, such as partial synchrony, failure detection, and fair schedulers. Recent research suggests that many of these systems are closely related (e.g., several failure detectors have been shown to be equivalent to fair schedulers) but considerable work remains to be done to better understand their similarities and differences. We will continue to investigate and compare these systems in an effort to unify and better understand the many models and results in the area. In many distributed systems, some strong assumptions, e.g., that processes are synchronous and do not crash, can hold for relatively long periods of time. Furthermore, algorithms that make such strong assumptions can be very efficient, but they may fail in the relatively rare cases when these assumptions are violated. To take advantage of this, one can first run a ``primary'' algorithm that is very efficient because it relies on strong assumptions, and then, in the rare cases when the primary algorithm fails, fall back on a less efficient ``backup'' algorithm that relies on weaker assumptions; this is the basic idea of ``speculative computing''. In preliminary work based on this approach, we derived speculative algorithms for the fundamental problem of consensus in systems with process crash failures. We propose to extend and generalize this initial work in several directions, for example to solve problems other than consensus, to tolerate more than just crash failures, and to investigate the efficient implementation of shared objects based on speculative computing.