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的法规任务，并被认为是通过基金会的知识优点和广泛的范围来评估的，并且值得通过评估来进行评估。