Grant: Discovery Grants Program - Individual
University of Toronto
$29,000.00
Synchronisation and fault tolerance in distributed computing
EF 2017-18
Résumé
Distributed computing is at the forefront of technological developments that are reshaping computing: With the key to greater computing power having shifted from increased processor clock speed to greater parallelism in the form of multicore processors, harnessing that greater computing power depends critically on our ability to solve effectively the problems that lie at the heart of distributed computing, namely synchronisation and fault tolerance. The proposed research will contribute to the solution of these problems. I plan to investigate both of the major approaches to synchronisation: blocking, where processes coordinate access to shared resources by waiting for each other and are therefore vulnerable to failures; and non-blocking, where processes never wait and are therefore amenable to tolerating failures.The efficiency of blocking synchronisation algorithms is often measured in terms of the number of remote-memory references (RMRs), i.e., the number of memory references generated by the algorithm that must traverse the processor-to-memory interconnect. The multiprocessor models on which the RMR measure is currently based, however, do not capture well some features of modern multicore architectures. I plan to develop a model that better captures the relevant characteristics of current multiprocessors, and study the RMR complexity of synchronisation algorithms in this model.In the realm of non-blocking synchronisation, I plan to extend some recent (joint) work on so-called abortable objects. I want to develop ""gracefully degrading"" implementations of such objects --- i.e., ones that are particularly efficient when there is little contention and few failures. In addition, I want to develop a theory of deterministic abortable objects, a stronger version of abortable objects, and to explore their relationship to transactional memory, a popular approach to concurrent programming.
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
903-2011
Name nom
Hadzilacos, Vassos
Department département
Computer and Mathematical Sciences (Scarborough)
Organization id
31
Institution établissement
University of Toronto
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2017
Competition year année de concours
2011
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 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
9999
Area of application group en
Not available
Area of application group fr
Non disponible
Area of application en
Not available
Area of application fr
Non disponible
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
5
Nb partie
5
Application title
Synchronisation and fault tolerance in distributed computing
Keyword
NSERC
Application summary
Distributed computing is at the forefront of technological developments that are reshaping computing: With the key to greater computing power having shifted from increased processor clock speed to greater parallelism in the form of multicore processors, harnessing that greater computing power depends critically on our ability to solve effectively the problems that lie at the heart of distributed computing, namely synchronisation and fault tolerance. The proposed research will contribute to the solution of these problems. I plan to investigate both of the major approaches to synchronisation: blocking, where processes coordinate access to shared resources by waiting for each other and are therefore vulnerable to failures; and non-blocking, where processes never wait and are therefore amenable to tolerating failures.The efficiency of blocking synchronisation algorithms is often measured in terms of the number of remote-memory references (RMRs), i.e., the number of memory references generated by the algorithm that must traverse the processor-to-memory interconnect. The multiprocessor models on which the RMR measure is currently based, however, do not capture well some features of modern multicore architectures. I plan to develop a model that better captures the relevant characteristics of current multiprocessors, and study the RMR complexity of synchronisation algorithms in this model.In the realm of non-blocking synchronisation, I plan to extend some recent (joint) work on so-called abortable objects. I want to develop ""gracefully degrading"" implementations of such objects --- i.e., ones that are particularly efficient when there is little contention and few failures. In addition, I want to develop a theory of deterministic abortable objects, a stronger version of abortable objects, and to explore their relationship to transactional memory, a popular approach to concurrent programming.