Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

University of Toronto

$43,000.00

On failure detection, leader election and abstruction-freedom

FY 2010-11

Summary
We will work on failure detection and leader election, and on implementations of shared objects that are wait-free, non-blocking, or obstruction-free, as we briefly explain below. Failure detectors are extensively used by the research community as a fundamental tool for fault-tolerant distributed computing. We will continue our work on the specification, implementation, and use of various types of failure detectors for solving different problems in asynchronous and partially synchronous systems, in both the message-passing and shared-memory models of computation. We will initially focus on Omega, a failure detector that can be considered an (eventual) leader elector. In particular, we will seek to (a) develop algorithms for Omega that are stable, message-efficient, and work in dynamic environments under weak system assumptions, (b) derive corresponding lower bounds (e.g., determine the weakest assumptions, in terms of system synchrony and failures, that support the implementation of Omega), and (c) implement, experimentally evaluate and compare several practical algorithms for Omega; this will be done in our distributed system lab and the best algorithms will be integrated in a general failure detector service package that will be available for public download. In the shared-memory model, we will investigate a relatively recent concept, namely obstruction-freedom, and its relation to two stronger progress requirements, lock-freedom and wait-freedom. As part of this work, we would like to determine the ``weakest'' synchronization primitive that supports obstruction-freedom, and whether obstruction-freedom can be achieved ``arbiter-free''. Our initial investigation shows that obstruction- freedom can be achieved with a register (called abortable register) that is weaker than safe registers, and we want to determine whether abortable registers are in some sense ``minimal'' and whether they are arbiter-free. We also intend to investigate the following question: How ``hard'' is it (in terms of system assumptions) to transform obstruction-free implementations into non-blocking or wait-free ones?
Program
Discovery Grants Program - Individual
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
250468-2007
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
2010
Competition year année de concours
2007
Award amount
43000
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
331
Committee name en
Computing and Information Sciences - B
Committee name fr
Informatique - B
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
Technologie de l'information
Research subject en
Distributed and parallel processing
Research subject fr
Traitement réparti et simultané
Partie
4
Nb partie
5
Application title
On failure detection, leader election and abstruction-freedom
Keyword
NSERC
Application summary
We will work on failure detection and leader election, and on implementations of shared objects that are wait-free, non-blocking, or obstruction-free, as we briefly explain below. Failure detectors are extensively used by the research community as a fundamental tool for fault-tolerant distributed computing. We will continue our work on the specification, implementation, and use of various types of failure detectors for solving different problems in asynchronous and partially synchronous systems, in both the message-passing and shared-memory models of computation. We will initially focus on Omega, a failure detector that can be considered an (eventual) leader elector. In particular, we will seek to (a) develop algorithms for Omega that are stable, message-efficient, and work in dynamic environments under weak system assumptions, (b) derive corresponding lower bounds (e.g., determine the weakest assumptions, in terms of system synchrony and failures, that support the implementation of Omega), and (c) implement, experimentally evaluate and compare several practical algorithms for Omega; this will be done in our distributed system lab and the best algorithms will be integrated in a general failure detector service package that will be available for public download. In the shared-memory model, we will investigate a relatively recent concept, namely obstruction-freedom, and its relation to two stronger progress requirements, lock-freedom and wait-freedom. As part of this work, we would like to determine the ``weakest'' synchronization primitive that supports obstruction-freedom, and whether obstruction-freedom can be achieved ``arbiter-free''. Our initial investigation shows that obstruction- freedom can be achieved with a register (called abortable register) that is weaker than safe registers, and we want to determine whether abortable registers are in some sense ``minimal'' and whether they are arbiter-free. We also intend to investigate the following question: How ``hard'' is it (in terms of system assumptions) to transform obstruction-free implementations into non-blocking or wait-free ones?