Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

University of Victoria

$41,000.00

Algorithms for Graphs and Communication Networks: A Model-Bridging Approach

EF 2024-25

Résumé
Graphs are widely used to model connections between entities. Massive graphs like the web graph or a model of the human brain may contain billions of nodes, making them hard to analyze. This puts a burden on computing resources like processing time, memory, and bandwidth in networks. One approach to reduce time is to recognize that graph problems are typically ongoing, with incremental changes over time. Dynamic graph algorithms reuse information from prior computations so that solutions can be updated as the graph changes. In the streaming model, information about the graph is processed as it streams through the processor using a space much smaller than what would be needed to keep the whole graph. In a parallel system, processors each have partial information about the graph and work simultaneously; they communicate via either a shared memory or via links between processors. A distributed communications network may itself be regarded as a graph over which the nodes know only their neighbors and collectively communicate in order to route information or solve problems. In a large network such as the web, there is also the possibility that some nodes are faulty or self-interested. In this type of scenario, coordination and collective decision-making among the nodes become important and a challenge, even when all nodes link directly to each other. Much recent progress has resulted from a cross-pollination of ideas arising from these models. In particular, the various measures of efficiency for the different models appear to be related: the update time for a dynamic algorithm, the amount of communication needed for a distributed algorithm, the work done by a parallel algorithm and the space needed for a streaming algorithm. Furthermore the methodologies for solving problems in these models are related as well, and insight gained for one model gives insight into another. We have seen that these new insights can lead us not only to better performance in these models, but also faster algorithms for classical sequential computers. Our goal is to use a model-bridging perspective to design more efficient graph algorithms and prove limits on what is possible. Fast, efficient algorithms use less energy and may be able to quickly provide real time solutions to complex problems. Collective decision-making which is fair and effective and does not incur high energy costs is increasingly important in the world of digital currency and influential reputation systems.
Programme
Discovery Grants Program - Individual
Emplacement
British Columbia, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
RGPIN-2022-04518
Name nom
King, Valerie
Department département
Computer Science Department
Organization id
7
Institution établissement
University of Victoria
Province en
British Columbia
Province fr
Colombie-Britannique
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2024
Competition year année de concours
2022
Award amount
41000
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
802
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
Information systems and technology
Area of application fr
Systèmes d'information et technologie de l'information
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 Graphs and Communication Networks: A Model-Bridging Approach
Keywords
graph algorithms; dynamic graph algorithms; data structures; distributed computing; fault tolerance; algorithmic fairness; collective decision-making; byzantine agreement; lower bounds; communication complexity
Application summary
Graphs are widely used to model connections between entities. Massive graphs like the web graph or a model of the human brain may contain billions of nodes, making them hard to analyze. This puts a burden on computing resources like processing time, memory, and bandwidth in networks. One approach to reduce time is to recognize that graph problems are typically ongoing, with incremental changes over time. Dynamic graph algorithms reuse information from prior computations so that solutions can be updated as the graph changes. In the streaming model, information about the graph is processed as it streams through the processor using a space much smaller than what would be needed to keep the whole graph. In a parallel system, processors each have partial information about the graph and work simultaneously; they communicate via either a shared memory or via links between processors. A distributed communications network may itself be regarded as a graph over which the nodes know only their neighbors and collectively communicate in order to route information or solve problems. In a large network such as the web, there is also the possibility that some nodes are faulty or self-interested. In this type of scenario, coordination and collective decision-making among the nodes become important and a challenge, even when all nodes link directly to each other. Much recent progress has resulted from a cross-pollination of ideas arising from these models. In particular, the various measures of efficiency for the different models appear to be related: the update time for a dynamic algorithm, the amount of communication needed for a distributed algorithm, the work done by a parallel algorithm and the space needed for a streaming algorithm. Furthermore the methodologies for solving problems in these models are related as well, and insight gained for one model gives insight into another. We have seen that these new insights can lead us not only to better performance in these models, but also faster algorithms for classical sequential computers. Our goal is to use a model-bridging perspective to design more efficient graph algorithms and prove limits on what is possible. Fast, efficient algorithms use less energy and may be able to quickly provide real time solutions to complex problems. Collective decision-making which is fair and effective and does not incur high energy costs is increasingly important in the world of digital currency and influential reputation systems.