Grant: Discovery Grants Program - Individual
University of Manitoba
$48,000.00
Algorithms for Graph-Based Models of Distributed Computation
EF 2024-25
Résumé
Our research goal is to use mathematical tools to design useful algorithms for modern distributed systems and formally prove their correctness and efficiency. We will also formally prove impossibility results, i.e., demonstrate that no algorithmic approach, now or in the future, will solve a certain task efficiently (or at all). From a practical perspective, this allows us to design and test algorithmic solutions for very large systems, which would be otherwise costly to do. Further, we can also study potential ideas for technologies that do not exist yet, which could help practitioners determine which kinds of systems they should be trying to build.
We focus on three different types of scenarios:
1) Anonymous communication networks. Anonymous networks can be useful when security and privacy is necessary. It is known that certain tasks are impossible to solve anonymously, but, this is often only true in networks whose topology is completely symmetric. Most networks are not symmetric, so our research will determine whether or not the asymmetries in a network topology can be used in algorithms as a replacement for using device addresses or personal/identifying information.
2) Wireless communication networks. The wireless medium introduces challenges involving interference due to simultaneous communication in the same geographic area. Some approaches to deal with this issue use each device's unique identifier/address to coordinate transmissions. However, with an increasing number of wireless devices, larger identifiers are needed to ensure uniqueness, which leads to a higher cost with regards to algorithmic efficiency. Rather than each device having one large permanent identifier, our research will investigate an approach where all of the devices in one geographic area can be assigned new smaller identifiers while they are in that area. Our research will determine how small these new identifiers can be, and how to assign them in a way that allows for very efficient communication algorithms.
3) Autonomous mobile entities. Consider a team of robots that act independently to accomplish a collective goal, such as meeting at the same location to share information, or quickly spreading out to perform search-and-rescue. Our research will focus on solving these kinds of tasks when there is no central entity controlling all of the robots, there is limited communication between the robots, and there is limited location information available. We will also devise solutions that work when some of the robots are faulty or have been hacked by a malicious party.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Manitoba, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
RGPIN-2024-06411
Name nom
Miller, Avery
Department département
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
2024
Competition year année de concours
2024
Award amount
48000
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
2713
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Algorithms
Research subject fr
Algorithmes
Field of research list names en
Not available
Field of research list names fr
Non disponible
Socioeconomic objective list names en
Not available
Socioeconomic objective list names fr
Non disponible
Application title
Algorithms for Graph-Based Models of Distributed Computation
Keywords
algorithm design; lower bounds; impossibility results; message-passing models; anonymous networks; wireless networks; mobile devices; graph theory
Application summary
Our research goal is to use mathematical tools to design useful algorithms for modern distributed systems and formally prove their correctness and efficiency. We will also formally prove impossibility results, i.e., demonstrate that no algorithmic approach, now or in the future, will solve a certain task efficiently (or at all). From a practical perspective, this allows us to design and test algorithmic solutions for very large systems, which would be otherwise costly to do. Further, we can also study potential ideas for technologies that do not exist yet, which could help practitioners determine which kinds of systems they should be trying to build.
We focus on three different types of scenarios:
1) Anonymous communication networks. Anonymous networks can be useful when security and privacy is necessary. It is known that certain tasks are impossible to solve anonymously, but, this is often only true in networks whose topology is completely symmetric. Most networks are not symmetric, so our research will determine whether or not the asymmetries in a network topology can be used in algorithms as a replacement for using device addresses or personal/identifying information.
2) Wireless communication networks. The wireless medium introduces challenges involving interference due to simultaneous communication in the same geographic area. Some approaches to deal with this issue use each device's unique identifier/address to coordinate transmissions. However, with an increasing number of wireless devices, larger identifiers are needed to ensure uniqueness, which leads to a higher cost with regards to algorithmic efficiency. Rather than each device having one large permanent identifier, our research will investigate an approach where all of the devices in one geographic area can be assigned new smaller identifiers while they are in that area. Our research will determine how small these new identifiers can be, and how to assign them in a way that allows for very efficient communication algorithms.
3) Autonomous mobile entities. Consider a team of robots that act independently to accomplish a collective goal, such as meeting at the same location to share information, or quickly spreading out to perform search-and-rescue. Our research will focus on solving these kinds of tasks when there is no central entity controlling all of the robots, there is limited communication between the robots, and there is limited location information available. We will also devise solutions that work when some of the robots are faulty or have been hacked by a malicious party.