AF: Small: Relative Fault Tolerance in Network Design

容错对于每个计算机系统都至关重要，尤其是在网络和分布式系统中，计算和通信组件可能会出现故障。每个网络(例如，互联网、电网、移动电话或交通/关闭的道路网络)都需要对组件故障或故障具有恢复能力。在可能出现许多故障的灾难性事件中保持服务质量至关重要。这个项目是关于相对于一些底层系统/网络的容错的新概念，它允许比传统定义更精细和更强大的保证。PI将发展相对容错理论，从根本上提高对这些新定义的能力和局限性的认识，并导致改善联网系统的可靠性。该项目包括在这项工作的更多应用方面指导和包括未被充分代表的本科生和高中生，以及通过现有的基于数学的课程延伸到巴尔的摩的中学。该项目的重点将是网络设计问题，其中系统是一个应该在故障后保持连接的网络，或者应该既保持连接又在故障后保持网络距离。传统的容错概念是绝对的：如果一个网络能够承受一定数量的故障，它就是容错的。但如果我们在现有系统的基础上构建，这种观念是有限的；如果底层系统的容错性不是很强，那么我们的系统就不能很容错。为了绕过这个限制，PI将研究设计具有相对容错能力的网络和系统的算法，其中要求系统对底层系统也具有健壮性的故障具有健壮性。更正式地说，网络是f-容错的，不是如果它能承受f个故障(传统定义)，而是如果它在f个故障后具有与底层系统相同的行为。这个项目中的两个主要问题类型如下。-可生存网络设计，其中目标是找到给定网络的子图，其中故障后的子图的连通分量与故障后全网络的连通分量相同。-图生成器，其中目标是找到给定网络的子图，其中故障后的子图中的成对距离是故障后全图中成对距离的良好近似值。对于这两种类型的问题，PI将为主要问题及其变体设计有效的近似算法，无论是在传统的集中式计算模型中还是在分布式和并行模型中。为了做到这一点，有必要开发新的算法技术，这些技术基于但超过了用于相关问题的技术(可生存网络设计的迭代舍入，扳手的随机舍入)。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Fault tolerance is crucial for every computer system, particularly networked and distributed systems where computational and communication components can fail. Every network (e.g., internet, electric power grid, mobile phones or road networks with traffic/closures) needs to be resilient to component failures or malfunctions. It is crucial that quality of service is maintained in catastrophic events where there can be many failures. This project is about a new notion of fault-tolerance that is relative to some underlying system/network, which allows for more refined and powerful guarantees than traditional definitions. The PI will develop the theory of relative fault-tolerance, fundamentally improving knowledge of the capabilities and limitations of these new definitions and leading to improved reliability of networked systems. This project incorporates mentoring and including underrepresented undergraduates and high school students in the more applied aspects of this work, as well as outreach to middle schools in Baltimore through existing mathematics-based programs.The focus of the project will be on network-design problems, where the system is a network which is either supposed to stay connected after faults or is supposed to both stay connected and preserve distances in the network after faults. The traditional notion of fault-tolerance is absolute: a network is fault tolerant if it can withstand some number of failures. But this notion is limiting if we are building on top of an already existing system; if the underlying system is not very fault-tolerant, then our system cannot be very fault-tolerant. To get around this limitation, the PI will study algorithms for designing networks and systems with relative fault tolerance, where the requirement is that the system be robust to faults which the underlying system is also robust to. More formally, a network is f-fault tolerant not if it can withstand f faults (the traditional definition), but if it has the same behavior after f faults as the underlying system. The two main problem types in this project are the following.- Survivable Network Design, where the goal is to find a subgraph of a given network where the connected components of the subgraph after faults are the same as the connected components of the full network after faults.- Graph Spanners, where the goal is to find a subgraph of a given network where the pairwise distances in the subgraph after faults are a good approximation of the pairwise distances in the full graph after faults.For both of these types of problems, the PI will design efficient approximation algorithms for the main problems and their variants, in the traditional centralized model of computation as well as in distributed and parallel models. In order to do this, it will be necessary to develop new algorithmic techniques that are based on but go beyond the techniques that have been used for related problems (iterative rounding for survivable network design, randomized rounding for spanners).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.