Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

University of Manitoba

$40,000.00

The Effects of Locality on Efficient Distributed Computation

FY 2022-23

Summary
We live in an era of increasing connectivity. The days where computation happens at a single machine are coming to an end, and now our systems often comprise of a set of independent devices that have to interact to accomplish a goal without a central coordinator. This shift has introduced many new challenges and has forced us to think about algorithms and computation in a different way. One central issue that is unique to distributed algorithm design is that of "locality", a term that means that each device might have very limited information about the entire system, or can only view and communicate with other nearby devices. Our goal in this research is to better understand how different degrees of locality affect how efficient distributed algorithms can be. We consider the notion of efficiency in a broad sense, since different applications have different priorities with respect to resource consumption. Three important measures of efficiency are: time (how fast is the algorithm), cost (how much money or fuel does it take to run the algorithm), and communication (what are the network bandwidth requirements). Our main contributions will be to formally and precisely analyze the tradeoff between the efficiency of algorithms (with respect to the three measures listed above) and locality constraints. More specifically, this involves producing two kinds of results: (1) describing efficient algorithms when information and/or device capabilities are restricted, and, (2) proving impossibility results that give the best efficiency bounds that we can hope for under such restrictions. We have identified four application areas where we will focus our efforts in producing these kinds of results: (Area 1) Static Networks with Synchronous Communication(Area 2) Networks of Mobile Nodes with Wireless Radio Communication(Area 3) Autonomous Robots in Unknown Environments(Area 4) Routing Packets in Networks with Bounded BuffersIn the next 5 years, I plan to complete the following projects within each of the above application areas:(Area 1) Determining the optimal leader election algorithms under all possible ranges of information locality.(Area 2) Determining the optimal neighbour discovery algorithms for vehicles traveling on simple road networks, both under information restrictions and communication/sensing restrictions.(Area 3) Determining the optimal rendezvous algorithms for autonomous robots in an unknown environment with limited communication and vision.(Area 4) Determining the best strategy for forwarding packets in a network where each router has a small memory buffer and limited information about the rest of the network.I plan to directly train 8-10 HQP in the next 5 years, and I will be indirectly involved in the training of other HQP in our newly-formed collaborative research lab.
Program
Discovery Grants Program - Individual
Location
Manitoba, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
RGPIN-2017-05936
Name nom
Miller, Avery
Department département
Computer Science - Computer Science
Organization id
19
Institution établissement
University of Manitoba
Province en
Manitoba
Province fr
Manitoba
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2022
Competition year année de concours
2017
Award amount
40000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR 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
2700
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Information technology
Research subject fr
Technologie de l'information
Installment
inst:6;7
Partie
2
Nb partie
7
Application title
The Effects of Locality on Efficient Distributed Computation
Application summary
We live in an era of increasing connectivity. The days where computation happens at a single machine are coming to an end, and now our systems often comprise of a set of independent devices that have to interact to accomplish a goal without a central coordinator. This shift has introduced many new challenges and has forced us to think about algorithms and computation in a different way. One central issue that is unique to distributed algorithm design is that of "locality", a term that means that each device might have very limited information about the entire system, or can only view and communicate with other nearby devices. Our goal in this research is to better understand how different degrees of locality affect how efficient distributed algorithms can be. We consider the notion of efficiency in a broad sense, since different applications have different priorities with respect to resource consumption. Three important measures of efficiency are: time (how fast is the algorithm), cost (how much money or fuel does it take to run the algorithm), and communication (what are the network bandwidth requirements). Our main contributions will be to formally and precisely analyze the tradeoff between the efficiency of algorithms (with respect to the three measures listed above) and locality constraints. More specifically, this involves producing two kinds of results: (1) describing efficient algorithms when information and/or device capabilities are restricted, and, (2) proving impossibility results that give the best efficiency bounds that we can hope for under such restrictions. We have identified four application areas where we will focus our efforts in producing these kinds of results: (Area 1) Static Networks with Synchronous Communication(Area 2) Networks of Mobile Nodes with Wireless Radio Communication(Area 3) Autonomous Robots in Unknown Environments(Area 4) Routing Packets in Networks with Bounded BuffersIn the next 5 years, I plan to complete the following projects within each of the above application areas:(Area 1) Determining the optimal leader election algorithms under all possible ranges of information locality.(Area 2) Determining the optimal neighbour discovery algorithms for vehicles traveling on simple road networks, both under information restrictions and communication/sensing restrictions.(Area 3) Determining the optimal rendezvous algorithms for autonomous robots in an unknown environment with limited communication and vision.(Area 4) Determining the best strategy for forwarding packets in a network where each router has a small memory buffer and limited information about the rest of the network.I plan to directly train 8-10 HQP in the next 5 years, and I will be indirectly involved in the training of other HQP in our newly-formed collaborative research lab.