Collaborative Research: AF: Medium: The Communication Cost of Distributed Computation

点击翻译按钮获取中文摘要

Distributed algorithms underlie the operation of modern communication networks, including the Internet. Designing efficient distributed algorithms is important for the efficient operation of the Internet, peer-to-peer networks (which power applications such as blockchains), and wireless and sensor networks. All of these technologies are crucial to the modern economy. This project focuses on understanding the communication cost of distributed algorithms, a basic measure of the efficiency of such algorithms, with the aim of developing scalable algorithms. These will lead to improvements in distributed applications such as peer-to-peer and ad hoc wireless sensor networks, and “big data” applications. This project will develop distributed algorithms whose communication cost is as small as possible, while also investigating the inherent limits to how small the communication cost can be. A key part of this project will be three annual workshops on foundations and applications of distributed computing, with each of the three investigators organizing one workshop at their respective computer science departments. These workshops will be aimed at undergraduate students from underrepresented groups from three universities: the University of Houston (a minority-serving institution), the University of Iowa, and Augusta University. These workshops will aim to recruit students to their Computer Science programs who are more representative of the diverse pool of students at the investigators’ institutions and cities. The investigators will also incorporate this research into their courses, mentoring graduate students and junior researchers, conducting tutorials and workshops at leading conferences in distributed computing, writing survey articles, and publishing a monograph on distributed algorithms.The overarching goal of this project is to substantially improve our understanding of the message complexity of fundamental problems in distributed computing. These include classical distributed computing problems such maximal independent set, graph coloring, maximal matching, leader election, broadcast, breadth-first search tree, and spanners, as well as fundamental graph optimization problems such as minimum spanning tree, shortest paths, diameter, maximum matching, minimum vertex cover, minimum dominating set, and maximum independent set. Many of these problems have been studied extensively for decades and are widely used primitives in distributed applications. However, a lot of this prior research focuses on understanding the round complexity of these problems. The project has two key research goals: (1) prove strong message complexity upper bounds by designing message-efficient distributed algorithms and (2) prove message complexity lower bounds, thereby identifying barriers to achieving low message complexity. In the process, the investigators aim to substantially enhance the understanding of how message complexity relates to the round complexity of problems and how it relates to the quality of approximation for fundamental graph optimization problems. The project will contribute new algorithmic techniques for proving message complexity upper bounds and new techniques for proving complementary message complexity lower bounds.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.