AF: Small: Embedding Distributed Computations and Flows in Networks

这个项目的动机是在企业和基础设施系统底层的网络中出现的基本问题。该项目涵盖的各种应用程序包括云计算、数据中心、区块链技术和移动设备网络。映射异构服务器云中的通信进程集合的最佳算法是什么？大型人工智能计算应该如何嵌入到计算机网络中？底层数据中心网络如何有效地支持分布式系统的数据流需求？高度动态的网络能否支持快速可靠的通信？这个项目的重点是开发一个严谨的算法框架来研究这些问题，并为相关问题设计有效的算法。PI努力将这些问题的算法基础的进步转化为应用程序中的切实利益。该项目的综合教育部分包括实验和测量研究，几个具体的论文研究方向，以及一门新课程“现代网络系统的算法”。作为扩大计算机科学基金会参与的努力的一部分，PI计划在波士顿地区学校参加的初中和高中教师的暑期研讨班上讲授图表及其应用。最终目标是吸引来自这些学校的年轻学生，并向多元化的社区提出CS可能的学术和职业未来。该项目的技术核心包括三类算法问题。第一部分是在任意网络拓扑中嵌入分布式计算，重点是在计算任务和网络机器中建模异构性。预期的研究贡献包括(a)解决最小拉伸图-收缩问题的复杂性，这是经典度量嵌入的自然变体，以及(b)有向无环图的通信感知嵌入的近似算法。第二个部分是关于嵌入流及其泛化（称为coflows），它捕获共享共同性能目标的流集合。这里的目的是最小化与流的响应时间相关的目标，对于一般网络。第一个和第二个组件都假定底层网络不随时间变化。该项目的第三个组成部分涉及嵌入动态网络。它寻求高度动态网络中信息流的分布式算法，并解决具有已知动态的网络的几个时间优化问题。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

This project is motivated by fundamental problems arising in networks underlying enterprise and infrastructure systems. The diverse applications spanned in this project include cloud computing, datacenters, blockchain technologies, and networks of mobile devices. What is the best algorithm to map a collection of communicating processes in a cloud of heterogeneous servers? How should a large AI computation be embedded in a network of computers? How can the data-flow needs of a distributed system be effectively supported by the underlying datacenter network? Can a highly dynamic network support fast and reliable communication? The focus of this project is on developing a rigorous algorithmic framework for studying these questions and designing efficient algorithms for the relevant problems.The PI endeavors to translate the advances in algorithmic foundations of these problems to tangible benefits in the applications. The integrated educational component of the project includes experimental and measurement studies, several concrete directions for dissertation research, and a new course on "Algorithms for Modern Networked Systems". As part of an effort to broaden participation in computer-science foundations, the PI plans to lecture on graphs and their applications at a summer institute for participating middle- and high-school teachers from Boston-area schools. The ultimate goal is to engage young students from these schools and suggest a possible academic and professional future in CS to a diverse community.The technical core of the project comprises three categories of algorithmic problems. The first component is on embedding distributed computations in arbitrary network topologies, with an emphasis on modeling heterogeneity in both the computational tasks and the network machines. The expected research contributions include (a) resolving the complexity of the minimum-stretch graph-retraction problem, which is a natural variant of classic metric embeddings, and (b) approximation algorithms for the communication-aware embedding of directed acyclic graphs. The second component is on embedding flows and their generalizations called coflows, which capture flow collections sharing a common performance goal. The aim here is to minimize objectives related to the response times of the flows, for general networks. Both the first and second components assume that the underlying network does not change with time. The third component of this project concerns embedding in dynamic networks. It seeks distributed algorithms for information flows in highly dynamic networks, and solutions to several temporal optimization problems for networks with known dynamics.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.