Grant: Discovery Grants Program - Individual
University of Toronto
$43,000.00
On failure detection, leader election and abstruction-freedom
FY 2007-08
Summary
We will work on failure detection and leader election, and on implementations of shared objects thatare 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-tolerantdistributed computing. We will continue our work on the specification, implementation, and use ofvarious types of failure detectors for solving different problems in asynchronous and partially synchronoussystems, in both the message-passing and shared-memory models of computation. We will initially focus onOmega, 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 environmentsunder weak system assumptions, (b) derive corresponding lower bounds (e.g., determine the weakestassumptions, 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 donein our distributed system lab and the best algorithms will be integrated in a general failure detector servicepackage 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, andwhether 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 wewant 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
Recipient
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
2007
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
1
Nb partie
5
Application title
On failure detection, leader election and abstruction-freedom
Keyword
NA
Application summary
We will work on failure detection and leader election, and on implementations of shared objects thatare 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-tolerantdistributed computing. We will continue our work on the specification, implementation, and use ofvarious types of failure detectors for solving different problems in asynchronous and partially synchronoussystems, in both the message-passing and shared-memory models of computation. We will initially focus onOmega, 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 environmentsunder weak system assumptions, (b) derive corresponding lower bounds (e.g., determine the weakestassumptions, 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 donein our distributed system lab and the best algorithms will be integrated in a general failure detector servicepackage 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, andwhether 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 wewant 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?