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

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.