1Information Theoretic Bounds for Distributed Computation

Abstract—A network of nodes communicate via noisy channels. Each node has some real-valued initial measure-ment or message. The goal of each of the nodes is to acquire an estimate of a given function of all the initial measurements in the network. As the main contribution of this paper, we obtain a lower bound on computation time that must be satisfied by any algorithm used by the nodes to communicate and compute, so that the mean square error in the nodes ’ estimate is within a given interval around zero. This utilizes information theoretic inequalities reminiscent of those used in rate distortion theory along with a novel ‘perturbation ’ techniques so as to be broadly applicable. To understand the tightness of the bound, we consider a specific scenario where nodes are required to learn a linear combination of the initial values in the network while communicating over erasure channels. We develop a distributed quantized algorithm whose computation time essentially scales as that implied by the lower bound. In particular, the computation time depends reciprocally on ”conductance”, which is a property of the network that captures the information-flow bottleneck. As a by product, this leads to a quantized algorithm for computing separable function in a network with minimal computation time. I