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.