EAGER: A New Communication Measure for Distributed Computations

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

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.