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

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

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.