AF: Small: Network Algorithms Under Adversarial and Stochastic Uncertainty

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

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.