权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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将在传统的集中式计算模型以及分布式和并行模型中为主要问题及其变体设计有效的近似算法。为了做到这一点，将有必要开发新的算法技术，这些技术基于但超越了已用于相关问题的技术（可生存网络设计的迭代舍入，spatial的随机舍入）。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

期刊论文数量（13）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Faster Matchings via Learned Duals

DOI：
发表时间：
2021-07
期刊：
ArXiv
影响因子：
0
作者：
M. Dinitz;Sungjin Im;Thomas Lavastida;Benjamin Moseley;Sergei Vassilvitskii
通讯作者：
M. Dinitz;Sungjin Im;Thomas Lavastida;Benjamin Moseley;Sergei Vassilvitskii

Partially Optimal Edge Fault-Tolerant Spanners

部分最优边缘容错扳手