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.

分布式算法是包括互联网在内的现代通信网络的运营。设计有效的分布式算法对于Internet，对等网络（电源应用程序，例如区块链）以及无线和传感器网络的有效运行至关重要。所有这些技术对现代经济至关重要。该项目着重于理解分布式算法的通信成本，这是对此类算法效率的基本测量，目的是开发可扩展算法。这些将导致改进分布式应用程序，例如点对点和临时无线传感器网络以及“大数据”应用程序。该项目将开发分布式算法的沟通成本尽可能小，同时还研究了对通信成本的较小的继承限制。该项目的关键部分是关于分布式计算的基础和应用的三个年度研讨会，三位调查人员中的每一个都在其各自的计算机科学部门组织一个研讨会。这些讲习班将针对来自三所大学的代表性不足小组的本科生：休斯敦大学（少数派服务机构），爱荷华大学和奥古斯塔大学。这些研讨会将旨在招募学生参加其计算机科学计划，这些计划更代表调查人员机构和城市的学生库。调查人员还将将这项研究纳入他们的课程，心理研究生和初级研究人员，在分布式计算，撰写调查文章以及发表有关分布式算法的专着的主题上，进行教程和讲习班。该项目的总体目标是实质上提高我们对分布式计算问题的信息的理解。其中包括经典的分布式计算问题，例如最大独立集，图形着色，最大匹配，领导者选举，广播，广泛的优先搜索树和跨度，以及基本的图表优化问题，例如最小跨越树，最短路径，直径，最大匹配，最大匹配，最小值顶点盖，最小顶点覆盖，最小的统治设置和最大独立集合。这些问题中的许多已被广泛研究了数十年，并且是分布式应用中广泛使用的原始方法。但是，许多先前的研究都集中在理解这些问题的复杂性上。该项目具有两个关键的研究目标：（1）通过设计消息效率的分布式算法来证明强烈的消息复杂性上限，并且（2）证明了消息复杂性下限，从而确定了达到低信息复杂性的障碍。在此过程中，调查人员的目的是大大增强对信息复杂性如何与问题的复杂性相关的理解，以及与基本图优化问题的近似质量相关的关系。该项目将贡献新的算法技术，以证明消息复杂性上限和新技术以证明互补消息复杂性下限。该奖项反映了NSF的法定任务，并被认为是通过基金会的知识分子优点和更广泛的影响审查标准来评估来获得的支持。