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.

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

项目成果

Topology Dependent Bounds For FAQs

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

• DOI: 10.1145/3294052.3319686
• 发表时间: 2019-01
• 期刊: 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

Hypertree Decompositions Revisited for PGMs

重新审视 PGM 的超树分解

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

General strong polarization

一般强极化

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

Facility Location Problem in Differential Privacy Model Revisited

再论差分隐私模型中的设施选址问题

• 发表时间: 2019-01
• 期刊: Advances in neural information processing systems
• 作者: Esencayi, Yunus;Gaboardi, Marco;Li, Shi;Wang, Di
• 通讯作者: Wang, Di