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）有向无环图的通信感知嵌入的近似算法。第二个组件是关于嵌入流和它们的泛化（称为coflows）的，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

HaPPY-Mine: Designing a Mining RewardFunction

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

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