Grant: Discovery Grants Program - Individual
Simon Fraser University
$42,000.00
Randomized Algorithms for Distributed Systems
FY 2016-17
Summary
The proposed research concerns itself with the development and analysis of randomised algorithms for distributed computational resources. The distributed resources can be networks of closely or loosely connected computers, ad-hoc networks for disaster response, sensor networks, or simply a set of communicating robots that jointly perform a task, e.g., exploring some terrain.Whilst distributed computing has been around for a very long time it and a few of its relatives have more recently become fashionable also in the public eye. As the main driving forces are to be consideredoff-site storage of data (e.g., Google docs or Dropbox for very mainstream applications), or the now ubiquitous Cloud computing. At present there exist commercial large-scale data centres, large-scalewith respect to storage capacity as well processing power. However, whilst in the olden days many aspects of parallel code execution and data communication in networks, including primitive operationslike load balancing, scheduling and routing, were hand-optimised, under the new paradigms this is clearly not feasible any more.The proposal suggests research in three different areas of distributed computing. The first area is load balancing and here the proposed work is in the area of balls-into-bins games and diffusion load balancing. The second area is random walks. Random walks can be used as a mathematical model for terrain exploration. Here the terrain is modelled by a graph and the robots (random walks) are allowed to movealong the edges of the graph. The third area is communication in networks, and here the proposed research is concerned with information spreading.
Program
Discovery Grants Program - Individual
Recipient
Location
British Columbia, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
250284-2012
Name nom
Berenbrink, Petra
Department département
Computing Science, School of
Organization id
5
Institution établissement
Simon Fraser University
Province en
British Columbia
Province fr
Colombie-Britannique
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2016
Competition year année de concours
2012
Award amount
42000
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
803
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Computer communications
Area of application fr
Téléinformatique
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
Randomized Algorithms for Distributed Systems
Keyword
NSERC
Application summary
The proposed research concerns itself with the development and analysis of randomised algorithms for distributed computational resources. The distributed resources can be networks of closely or loosely connected computers, ad-hoc networks for disaster response, sensor networks, or simply a set of communicating robots that jointly perform a task, e.g., exploring some terrain.Whilst distributed computing has been around for a very long time it and a few of its relatives have more recently become fashionable also in the public eye. As the main driving forces are to be consideredoff-site storage of data (e.g., Google docs or Dropbox for very mainstream applications), or the now ubiquitous Cloud computing. At present there exist commercial large-scale data centres, large-scalewith respect to storage capacity as well processing power. However, whilst in the olden days many aspects of parallel code execution and data communication in networks, including primitive operationslike load balancing, scheduling and routing, were hand-optimised, under the new paradigms this is clearly not feasible any more.The proposal suggests research in three different areas of distributed computing. The first area is load balancing and here the proposed work is in the area of balls-into-bins games and diffusion load balancing. The second area is random walks. Random walks can be used as a mathematical model for terrain exploration. Here the terrain is modelled by a graph and the robots (random walks) are allowed to movealong the edges of the graph. The third area is communication in networks, and here the proposed research is concerned with information spreading.