AF: Small: Relative Fault Tolerance in Network Design

AF：小：网络设计中的相对容错性

基本信息

批准号：
1909111
负责人：
Michael Dinitz
金额：
$ 30万
依托单位：
Johns Hopkins University
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2019
资助国家：
美国
起止时间：
2019-10-01 至 2024-09-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1909111&HistoricalAwards=false
关键词：
AF Small Relative Fault Tolerance

项目摘要

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.

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

项目成果

期刊论文数量（13）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Scheduling for Weighted Flow and Completion Times in Reconfigurable Networks

可重构网络中加权流量和完成时间的调度

DOI：
10.1109/infocom41043.2020.9155537
发表时间：
2020-07
期刊：
IEEE INFOCOM 2020 - IEEE Conference on Computer Communications
影响因子：
0
作者：
Dinitz, Michael;Moseley, Benjamin
通讯作者：
Moseley, Benjamin

Partially Optimal Edge Fault-Tolerant Spanners

部分最优边缘容错扳手

DOI：
10.1137/1.9781611977073.129
发表时间：
2022-01
期刊：
Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms
影响因子：
0
作者：
Bodwin, Greg;Dinitz, Michael;Robelle, Caleb
通讯作者：
Robelle, Caleb

Efficient and Simple Algorithms for Fault-Tolerant Spanners

容错 Spanner 的高效且简单的算法

DOI：
10.1145/3382734.3405735
发表时间：
2020-07
期刊：
PODC '20: Proceedings of the 39th Symposium on Principles of Distributed Computing
影响因子：
0
作者：
Dinitz, Michael;Robelle, Caleb
通讯作者：
Robelle, Caleb

Massively Parallel Approximate Distance Sketches

大规模并行近似距离草图

DOI：
10.4230/lipics.opodis.2019.35
发表时间：
2019-01
期刊：
23rd International Conference on Principles of Distributed Systems (OPODIS 2019
影响因子：
0
作者：
Dinitz, Michael;Nazari, Yasamin
通讯作者：
Nazari, Yasamin

Controlling Epidemic Spread using Probabilistic Diffusion Models on Networks

使用网络上的概率扩散模型控制流行病传播

DOI：
发表时间：
2022-01
期刊：
Proceedings of The 25th International Conference on Artificial Intelligence and Statistics
影响因子：
0
作者：
Babay, Amy;Dinitz, Michael;Srinivasan, Aravind;Tsepenekas, Leonidas;Vullikanti, Anil
通讯作者：
Vullikanti, Anil