Grant: Discovery Grants Program - Individual
McMaster University
$11,258.00
Communication-Efficient Distributed Algorithms for Modern Networks
EF 2019-20
Résumé
The overarching goal of this program of research is to significantly advance the state of the art in the algorithmic foundations of communication-efficient distributed computing. The ubiquity of mobile phones and the emergence of ""smart"" networked day-to-day objects have resulted in the creation of large decentralized (mobile) networks. Due to their ad hoc nature, these networks are inherently resource-constrained and very dynamic, as the network topology and the set of participating nodes might change over time. Distributed algorithms for resource-restricted devices must be communication-efficient by sending few and short messages, as the available communication bandwidth typically scales only logarithmically with the network size. Communication-efficiency is also crucial for optimizing battery-usage of devices, since the energy consumption of mobile nodes is directly related to radio transceiver usage (c.f. Chang et al: The Energy Complexity of Broadcast, 2017).******Modern networks are often ""permissionless"", in the sense that any node can join the network, which requires distributed algorithms to be resilient against malicious agents in the network. Motivated by these challenges, one goal of this research is the design of fault-tolerant and communication-efficient algorithms that achieve distributed consensus in ad hoc network models, which requires the nodes in a network to output a common value when each node starts out with some input value. A related objective is the development of methods for maintaining the network connectivity properties against adversarial attacks and in the presence of malicious peers. ******Communication-efficiency is also crucial for performing distributed graph computations in large-scale networks. Obtaining efficient distributed algorithms for massive graphs is another goal of this program of research with many application domains (e.g., biological networks). Moreover, certain graph structures can serve as sparse communication backbones for information dissemination, which makes them a prerequisite for solving problems such as consensus efficiently. To broaden the impact of the theoretical results, a third aim of this research program is the experimental evaluation of the developed distributed algorithms.******The outcomes of this research can enable the development of resilient and communication-efficient distributed software systems. The potential applications to emergent technologies are numerous; ranging from improved digital ledgers and crypto-currencies suitable for large networks of resource-restricted devices to providing more secure distributed computation in the context of the Internet of Things. The graph algorithms designed in this research can also lead to more efficient distributed computation on massive graph data sets, which has the potential to improve big data analytics and lead to better data-driven policy making.
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
RGPIN-2018-06322
Name nom
Robinson, Peter
Department département
Computing and Software
Organization id
27
Institution établissement
McMaster University
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2019
Competition year année de concours
2018
Award amount
11258
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
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
2704
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Distributed and parallel processing
Research subject fr
Traitement réparti et simultané
Installment
NA
Partie
0
Nb partie
NA
Application title
Communication-Efficient Distributed Algorithms for Modern Networks
Keyword
NSERC
Application summary
The overarching goal of this program of research is to significantly advance the state of the art in the algorithmic foundations of communication-efficient distributed computing. The ubiquity of mobile phones and the emergence of ""smart"" networked day-to-day objects have resulted in the creation of large decentralized (mobile) networks. Due to their ad hoc nature, these networks are inherently resource-constrained and very dynamic, as the network topology and the set of participating nodes might change over time. Distributed algorithms for resource-restricted devices must be communication-efficient by sending few and short messages, as the available communication bandwidth typically scales only logarithmically with the network size. Communication-efficiency is also crucial for optimizing battery-usage of devices, since the energy consumption of mobile nodes is directly related to radio transceiver usage (c.f. Chang et al: The Energy Complexity of Broadcast, 2017).******Modern networks are often ""permissionless"", in the sense that any node can join the network, which requires distributed algorithms to be resilient against malicious agents in the network. Motivated by these challenges, one goal of this research is the design of fault-tolerant and communication-efficient algorithms that achieve distributed consensus in ad hoc network models, which requires the nodes in a network to output a common value when each node starts out with some input value. A related objective is the development of methods for maintaining the network connectivity properties against adversarial attacks and in the presence of malicious peers. ******Communication-efficiency is also crucial for performing distributed graph computations in large-scale networks. Obtaining efficient distributed algorithms for massive graphs is another goal of this program of research with many application domains (e.g., biological networks). Moreover, certain graph structures can serve as sparse communication backbones for information dissemination, which makes them a prerequisite for solving problems such as consensus efficiently. To broaden the impact of the theoretical results, a third aim of this research program is the experimental evaluation of the developed distributed algorithms.******The outcomes of this research can enable the development of resilient and communication-efficient distributed software systems. The potential applications to emergent technologies are numerous; ranging from improved digital ledgers and crypto-currencies suitable for large networks of resource-restricted devices to providing more secure distributed computation in the context of the Internet of Things. The graph algorithms designed in this research can also lead to more efficient distributed computation on massive graph data sets, which has the potential to improve big data analytics and lead to better data-driven policy making.