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

合作研究：AF：媒介：分布式计算的通信成本

• 批准号: 2402837
• 负责人: Gopal Pandurangan
• 金额: $ 33.26万
• 依托单位: University of Houston
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2024
• 资助国家: 美国
• 起止时间: 2024-07-01 至 2028-06-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2402837&HistoricalAwards=false
• 关键词: Collaborative; Research; AF; Medium; Communication

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.

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