Communication-Efficient Distributed Algorithms for Modern Networks

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.