AF: Small: Network Algorithms Under Adversarial and Stochastic Uncertainty

AF：小：对抗性和随机不确定性下的网络算法

• 批准号: 1422715
• 负责人: Rajmohan Rajaraman
• 金额: $ 38.2万
• 依托单位: Northeastern University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-09-01 至 2017-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1422715&HistoricalAwards=false
• 关键词: AF; Small; Network; Algorithms; Under

Modern information networks are composed of heterogeneous nodes and links, whose capacities and capabilities change unexpectedly due to mobility, failures, maintenance, and adversarial attacks.  User demands and critical infrastructure needs, however, require that basic primitives including access to information and services be always efficient and reliable.  This project studies the design of highly robust networked systems that are resilient to extreme failures and rapid dynamics, and provide optimal performance under a wide spectrum of scenarios with varying levels of predictability.The focus of this project will be on two problem domains, which together address adversarial network dynamics and stochastic network failures.  The first component is a comprehensive theory of information spreading in dynamic networks.  The PI will develop an algorithmic toolkit for dynamic networks, including local gossip-style protocols, network coding, random walks, and other diffusion processes.  The second component of the project concerns failure-aware network algorithms that provide high availability in the presence of unexpected and correlated failures.  The PI will study failure-aware placement of critical resources, and develop flow and cut algorithms under stochastic failures using techniques from chance-constrained optimization.  Algorithms tolerant to adversarial and stochastic uncertainty will play a critical role in large-scale heterogeneous information networks of the future. Broader impacts include student training and curriculum development.

现代信息网络由异构节点和链路组成，其容量和功能由于移动性、故障、维护和对抗性攻击而发生意外变化​然而，用户需求和关键基础设施需求要求包括信息和服务访问在内的基本原语。该项目研究高度稳健的网络系统的设计，这些系统能够抵御极端故障和快速动态，并在具有不同可预测性水平的各种场景下提供最佳性能。该项目的重点将放在两个方面问题领域，共同解决对抗性网络动态和随机网络故障​第一个组成部分是动态网络中信息传播的综合理论。​PI 将开发动态网络的算法工具包，包括本地八卦式协议、网络编码、随机游走和其他扩散过程。该项目的第二个组成部分涉及故障感知网络算法，该算法在出现意外和相关故障时提供高可用性。PI 将研究关键资源的故障感知布局，并开发流程和使用机会约束优化技术在随机故障下削减算法 容忍对抗性和随机不确定性的算法将在未来的大规模异构信息网络中发挥关键作用，包括学生培训和课程开发。