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

分布式算法是包括互联网在内的现代通信网络运行的基础。设计高效的分布式算法对于互联网、对等网络(为区块链等应用程序提供动力)以及无线和传感器网络的高效运行非常重要。所有这些技术对现代经济都至关重要。这个项目的重点是了解分布式算法的通信成本，这是衡量此类算法效率的基本指标，目的是开发可伸缩的算法。这些将导致分布式应用的改进，如点对点和临时无线传感器网络，以及“大数据”应用。这个项目将开发通信成本尽可能小的分布式算法，同时也调查通信成本可以多小的内在限制。该项目的一个关键部分将是三个关于分布式计算基础和应用的年度讲习班，三名调查员每人在各自的计算机科学系组织一个讲习班。这些研讨会将面向来自三所大学的未被充分代表的群体的本科生：休斯顿大学(一所为少数族裔服务的机构)、爱荷华大学和奥古斯塔大学。这些研讨会的目的是招收更能代表调查机构和城市多样化学生群体的计算机科学专业的学生。研究人员还将把这项研究纳入他们的课程，指导研究生和初级研究人员，在分布式计算的领先会议上进行教程和研讨会，撰写调查文章，并出版一本关于分布式算法的专著。这个项目的总体目标是大幅提高我们对分布式计算基本问题的消息复杂性的理解。这些问题包括经典的分布式计算问题，如最大独立集、图着色、最大匹配、领袖选举、广播、广度优先搜索树和生成器，以及基本的图优化问题，如最小生成树、最短路径、直径、最大匹配、最小顶点覆盖、最小支配集和最大独立集。其中许多问题已经被广泛研究了几十年，并且是分布式应用中广泛使用的原语。然而，以往的许多研究都侧重于理解这些问题的复杂程度。该项目有两个关键的研究目标：(1)通过设计消息高效的分布式算法来证明强消息复杂度上界；(2)证明消息复杂度下界，从而识别实现低消息复杂度的障碍。在这个过程中，研究人员的目标是大大提高对消息复杂性如何与问题的圆形复杂性相关，以及它如何与基本图优化问题的逼近质量相关的理解。该项目将为证明消息复杂性上限贡献新的算法技术，并为证明补充消息复杂性下界贡献新技术。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.