EAGER: A New Communication Measure for Distributed Computations

EAGER：一种新的分布式计算通信手段

• 批准号: 1738058
• 负责人: Balasubramania Kalyanasundaram
• 金额: $ 22.5万
• 依托单位: Georgetown University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2017
• 资助国家: 美国
• 起止时间: 2017-09-01 至 2021-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1738058&HistoricalAwards=false
• 关键词: EAGER; New; Communication; Measure; Distributed

Distributed computations will play a huge role in the future of computer systems that range from a general purpose machine to a special purpose sensor network. Wild-life, infrastructure and environment monitoring as well as other smart-city projects will benefit from advances in such computational models. As a result any fundamental advances in these new models will have significant broader impacts. The investigator plans to involve students ranging from graduate school to local high schools such as Thomas Jefferson High School for Science and Technology. A distributed computation is typically viewed as a collection of local decisions to solve a problem. Unlike a single processor system where all the information necessary to compute the target function is available to the processor, in a distributed computation, each component of the system has limited knowledge/information. In addition, the flow of information from one component to another may be restricted by the system's inter-component communication capacities. In light of the limitations of each component's communication capacity, two natural questions arise: How should information flow among the components in order to compute the function efficiently, and How much information, in terms of bits, must be transmitted to each component at minimum. Communication complexity has proved to be very useful in obtaining bounds on the complexity of various problems ranging from circuit complexity to streaming algorithms. This project considers a variety of communication models to capture the essence of necessary data convergence to compute a function. A new measure of communication complexity is pursued and this measure captures an important component of what it means to be a distributive computation.

分布式计算将在未来的计算机系统中发挥巨大作用，从通用机器到专用传感器网络。野生动物、基础设施和环境监测以及其他智能城市项目将受益于此类计算模型的进步。因此，这些新模式的任何根本性进展都将产生更广泛的影响。 调查人员计划涉及从研究生院到当地高中的学生，如托马斯杰斐逊科技高中。分布式计算通常被视为解决问题的本地决策的集合。与其中计算目标函数所需的所有信息可用于处理器的单处理器系统不同，在分布式计算中，系统的每个组件具有有限的知识/信息。此外，从一个组件到另一个组件的信息流可能受到系统的组件间通信能力的限制。鉴于每个组件的通信能力的限制，出现了两个自然的问题：为了有效地计算函数，信息应该如何在组件之间流动，以及必须至少向每个组件传输多少信息（以比特为单位）。通信复杂性已被证明是非常有用的，在获得各种问题的复杂性范围从电路复杂性流算法的界限。该项目考虑了各种通信模型，以捕获计算函数所需的数据收敛的本质。一个新的通信复杂性的措施，追求和这种措施抓住了一个重要组成部分，这意味着什么是一个分布式计算。