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.