CRII: AF: The Impact of Knowledge on the Performance of Distributed Algorithms

CRII：AF：知识对分布式算法性能的影响

• 批准号: 2348346
• 负责人: Ming Ming Tan
• 金额: $ 17.5万
• 依托单位: AUGUSTA UNIVERSITY RESEARCH INSTITUTE, INC.
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2024
• 资助国家: 美国
• 起止时间: 2024-04-01 至 2026-03-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2348346&HistoricalAwards=false
• 关键词: CRII; AF; Impact; Knowledge; Performance

Modern distributed systems consist of inter-connected processing units that communicate and coordinate their actions by passing messages to one another to achieve a common goal. The protocol running on each computer in such a distributed system is called a distributed algorithm. Designing fast and communication-efficient distributed algorithms to solve fundamental distributed problems is an important challenge with a vast range of applications. For many distributed network problems, the performance of the distributed algorithms depends on the concrete amount of initial knowledge of the underlying network given to the individual computers. For instance, it is a realistic assumption that each computer knows an approximation of the network size and, in some cases, the IP addresses of the computers to which it is directly connected. The overarching goal of this project is to study the extent to which the initial knowledge can be leveraged for designing message-efficient algorithms. This research aims to improve our understanding of the performance of distributed algorithms and illuminate the intrinsic trade-offs between running time, communication, and initial knowledge. While the primary focus of the project is theoretical, the presented algorithmic approaches will serve as a foundation for developing practical algorithms with real-world impact.The project is centered around two main research objectives. The first research objective is to explore the trade-offs between partial-network knowledge and algorithmic performance regarding the construction and verification of fundamental distributed graph structures, assuming that nodes start out with some partial knowledge of their nearby network topology. While there are several known results on the impact of this initial knowledge on the running time of distributed algorithms, the question of how knowledge can be leveraged for designing message-efficient algorithms is still widely unresolved. The distributed graph problems that the project aims to address include approximate breadth-first search tree, single source shortest path tree, vertex coloring, maximal independent set, and maximal matching. The second research objective is to study the minimum amount of knowledge needed for a distributed algorithm to achieve optimal performance. In this context, a novel framework is introduced, where an oracle inspects the node's neighborhood topology up to some radius, and then assigns "advice" (a bit string) to each node as that node's initial knowledge. The study of the minimum required length of the advice assigned to a node under this new framework will allow the investigator to quantify the minimum amount of initial knowledge needed, and also to discover the inherent trade-offs between performance and initial knowledge for fundamental graph problems.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.

现代分布式系统由互连的处理单元组成，这些处理单元通过相互传递消息来通信和协调其操作以实现共同的目标。这种分布式系统中每台计算机上运行的协议称为分布式算法。设计快速且通信高效的分布式算法来解决基本的分布式问题是广泛应用的一个重要挑战。对于许多分布式网络问题，分布式算法的性能取决于给予各个计算机的底层网络初始知识的具体数量。例如，现实的假设是每台计算机都知道网络大小的近似值，并且在某些情况下还知道其直接连接的计算机的 IP 地址。该项目的总体目标是研究在多大程度上可以利用初始知识来设计消息高效的算法。这项研究旨在提高我们对分布式算法性能的理解，并阐明运行时间、通信和初始知识之间的内在权衡。虽然该项目的主要重点是理论，但所提出的算法方法将作为开发具有现实世界影响的实用算法的基础。该项目围绕两个主要研究目标。第一个研究目标是探索关于基本分布式图结构的构建和验证的部分网络知识和算法性能之间的权衡，假设节点一开始对其附近网络拓扑有一些部分了解。虽然关于这种初始知识对分布式算法运行时间的影响有几个已知的结果，但如何利用知识来设计消息高效的算法的问题仍然广泛未得到解决。该项目旨在解决的分布式图问题包括近似广度优先搜索树、单源最短路径树、顶点着色、最大独立集和最大匹配。第二个研究目标是研究分布式算法实现最佳性能所需的最少知识量。在这种情况下，引入了一种新颖的框架，其中预言机检查节点的邻域拓扑达到一定的半径，然后将“建议”（一个位字符串）分配给每个节点作为该节点的初始知识。在这个新框架下研究分配给节点的建议的最小所需长度将使研究人员能够量化所需的最小初始知识量，并发现基本图问题的性能和初始知识之间的固有权衡该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。