AF: Small: Embedding Distributed Computations and Flows in Networks

点击翻译按钮获取中文摘要

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.