AF: Small: Relative Fault Tolerance in Network Design

点击翻译按钮获取中文摘要

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.