AF:Small:Tight Topology Dependent bounds on Distributed Communication

AF：小：分布式通信的紧密拓扑依赖界限

• 批准号: 1717134
• 负责人: Atri Rudra
• 金额: $ 45万
• 依托单位: SUNY at Buffalo
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2017
• 资助国家: 美国
• 起止时间: 2017-09-01 至 2021-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1717134&HistoricalAwards=false
• 关键词: AF; Small; Tight; Topology; Dependent

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.

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

项目成果

Facility Location Problem in Differential Privacy Model Revisited

• 发表时间: 2019-10
• 作者: Yunus Esencayi;Marco Gaboardi;Shi Li;Di Wang

Hypertree Decompositions Revisited for PGMs

• 发表时间: 2018-04
• 期刊: ArXiv
• 作者: A. S. Arun;Sai Vikneshwar Mani Jayaraman;C. Ré;A. Rudra

Topology Dependent Bounds For FAQs

常见问题解答的拓扑相关边界

• DOI: 10.1145/3294052.3319686
• 发表时间: 2019
• 期刊: Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS
• 作者: Langberg, Michael;Li, Shi;Mani Jayaraman, Sai Vikneshwar;Rudra, Atri
• 通讯作者: Rudra, Atri

General strong polarization

• DOI: 10.1145/3188745.3188816
• 发表时间: 2018-02
• 期刊: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing
• 作者: Jarosław Błasiok;V. Guruswami;Preetum Nakkiran;A. Rudra;M. Sudan