AF: Small: Embedding Distributed Computations and Flows in Networks

AF：小型：在网络中嵌入分布式计算和流程

• 批准号: 1909363
• 负责人: Rajmohan Rajaraman
• 金额: $ 40万
• 依托单位: Northeastern University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-10-01 至 2023-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1909363&HistoricalAwards=false
• 关键词: AF; Small; Embedding; Distributed; Computations

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.

该项目是由企业和基础架构系统的网络中引起的基本问题所激发的。该项目跨越的不同应用程序包括云计算，数据中心，区块链技术和移动设备网络。在异质服务器云中绘制传达过程集合的最佳算法是什么？如何将大型AI计算嵌入到计算机网络中？基础数据中心网络如何有效支持分布式系统的数据流需求？高度动态的网络可以快速，可靠的通信吗？ 该项目的重点是开发一个严格的算法框架，用于研究这些问题并为相关问题设计有效的算法。PI努力将这些问题的算法基础的进步转化为在应用中有形优势的算法基础。该项目的综合教育组成部分包括实验和测量研究，多个用于论文研究的具体方向以及有关“现代网络系统算法”的新课程。作为扩大计算机科学基础的努力的一部分，PI计划在夏季研究所在夏季学院进行演讲及其应用程序，以参加来自波士顿地区学校的中学和高中老师。最终的目标是吸引这些学校的年轻学生，并向CS中的学术和专业未来展示到一个多元化的社区。该项目的技术核心包括三类算法问题。第一个组件是在任意网络拓扑中嵌入分布式计算，重点是在计算任务和网络计算机中建模异质性。预期的研究贡献包括（a）解决最小拉伸图形回分问题的复杂性，这是经典度量嵌入式的自然变体，以及（b）定向acyclic图的通信感知嵌入的近似算法。第二个组件是嵌入流及其概括称为coflows的组件，该流量捕获了共享共同性能目标的流量收集。此处的目的是最大程度地减少与一般网络相关的目标的目标。第一组件和第二个组件都假定基础网络不会随着时间而变化。该项目的第三个组成部分涉及将动态网络嵌入。它寻求分布式的算法来用于高度动态网络中的信息流，并为具有已知动态的网络的几个时间优化问题解决方案。该奖项反映了NSF的法定任务，并且认为值得通过基金会的知识分子优点和更广泛的影响评估标准通过评估来获得支持。

项目成果

Improved Bounds for Scheduling Flows under Endpoint Capacity Constraints

• DOI: 10.1137/1.9781611977059.1
• 发表时间: 2021-11
• 作者: Searidang Pa;R. Rajaraman;David Stalfa

Competitive Data-Structure Dynamization

• DOI: 10.1145/3672614
• 发表时间: 2020-11
• 期刊: Proceedings of the Platform for Advanced Scientific Computing Conference
• 作者: Claire Mathieu;R. Rajaraman;N. Young;A. Yousefi

One Tree to Rule Them All: Poly-Logarithmic Universal Steiner Tree

一棵树统治一切：多对数通用斯坦纳树

• 发表时间: 2023
• 期刊: IEEE Symposium on Foundations of Computer Science
• 作者: Costas Busch, Da Qi

Scheduling Precedence-Constrained Jobs on Related Machines with Communication Delay

在具有通信延迟的相关机器上调度优先级受限的作业

• DOI: 10.1109/focs46700.2020.00082
• 发表时间: 2020
• 期刊: 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS
• 作者: Maiti, Biswaroop;Rajaraman, Rajmohan;Stalfa, David;Svitkina, Zoya;Vijayaraghavan, Aravindan
• 通讯作者: Vijayaraghavan, Aravindan

Online Paging with Heterogeneous Cache Slots

• DOI: 10.48550/arxiv.2206.05579
• 发表时间: 2022-06
• 期刊: ArXiv
• 作者: M. Chrobak;Samuel Haney;Mehraneh Liaee;Debmalya Panigrahi;R. Rajaraman;Ravi Sundaram;N. Young