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将研究关键资源的失败放置，并使用偶然受限的优化技术在随机失败下开发流量和剪切算法。耐对抗和随机不确定性的算法将在未来的大规模异构信息网络中发挥关键作用。更广泛的影响包括学生培训和课程发展。