AF:Small:Tight Topology Dependent bounds on Distributed Communication

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.