AF:Small:Tight Topology Dependent bounds on Distributed Communication

社会对云计算的依赖性不断增加，导致人们重新关注解决数据中心分布式计算任务所产生的技术问题。该项目将解决数据中心分布式计算的基本理论挑战，这些数据中心具有日益复杂和流畅的互连，可管理日益雄心勃勃的计算任务。解决的挑战来自云计算的社会使用，以执行当前和未来的个人和机构日常计算任务的重要部分;以及对能源和时间高效的数据中心的需求来处理这些任务。 该项目旨在确定在所述挑战下分布式云计算背景下通信的基本限制（通常占所花费的大部分时间和精力）。该项目将汇集来自不同领域的研究人员。PI将参与K-12外展活动，此外还将吸引本科生参与研究，特别是那些来自代表性不足的群体。该项目将考虑一个一般场景，其中底层拓扑由图G =（V，E）给出。V中的每个节点都有一个处理器，并且k个处理器的子集（称为终端）具有输入。终端想要在V中的所有处理器协作的设置中计算k个输入上的函数f。E中的每条边e对应于一个专用点对点通信信道，所有通信都必须发生在其中一条边上。一般目标是计算f，同时最小化总轮数或总通信量。该项目将研究计算f所需的轮数和总通信量的上下界。将特别关注在实践中从数据库查询以及流计算中产生的函数f。该项目有可能增加通信复杂性，分布式计算，网络设计算法，网络编码和数据库研究人员之间的合作。

The ever increasing dependence of society on cloud computing has resulted in a renewed focus on technical problems that arise from solving distributed computational tasks in data centers. The project will address fundamental theoretical challenges in distributed computation in data centers with increasingly complex and fluid interconnections that manage increasingly ambitious computational tasks. The challenges addressed follow from the societal use of cloud computing to perform significant portions of the current and future, personal and institutional day to day computational tasks; and the need for energy and time efficient data centers to process such tasks. The project will aim to determine the fundamental limitations on communication (which typically accounts for bulk of time and energy expended) in the context of distributed cloud computing under the outlined challenges. This project will bring together researchers from disparate fields. The PIs will participate in K-12 outreach activities and in addition will engage undergraduates in research, especially those from under-represented groups.The project will consider a general scenario where the underlying topology is given by a graph G = (V,E). Each node in V has a processor, and a subset of k processors (called terminals) have inputs. The terminals want to compute a function f on the k inputs in a setting where all the processors in V cooperate. Each edge e in E corresponds to a private point-to-point communication channel and all communication has to happen on one of these edges. The general goal is to compute f while minimizing the total number of rounds or total communication. The project will study lower and upper bounds on both the number of rounds and total communication needed to compute f. Special focus will be given to functions f that arise in practice from database queries as well as streaming computation. The project has the potential of increasing collaboration between researchers in communication complexity, distributed computing, network design algorithms, network coding and databases.