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将研究关键资源的故障感知放置，并利用机会约束优化技术发展了随机故障下的流算法和割算法，容忍对抗性和随机不确定性的算法将在未来的大规模异构信息网络中发挥关键作用。 更广泛的影响包括学生培训和课程开发。