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

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

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.