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.

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

项目成果

Improved Bounds for Scheduling Flows under Endpoint Capacity Constraints

改进了端点容量约束下的调度流界限

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

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

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

• 发表时间: 2023-11
• 期刊: IEEE Symposium on Foundations of Computer Science
• 作者: Costas Busch; Da Qi
• 通讯作者: Da Qi

Competitive Data-Structure Dynamization

竞争数据结构动态化

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

Online Paging with Heterogeneous Cache Slots

异构缓存槽在线分页

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

HaPPY-Mine: Designing a Mining RewardFunction

HaPPY-Mine：设计挖矿奖励函数

• DOI: 10.1007/978-3-662-64331-0_13
• 发表时间: 2021-01
• 期刊: Financial Cryptography
• 作者: Kiffer; Lucianna and
• 通讯作者: Lucianna and