Counting bits for distributed function computation
Ola Ayaso, Devavrat Shah, Munther A. Dahleh · 2008
We consider a network of nodes, each having an initial value or measurement, and seeking to acquire an estimate of a given function of all the nodespsila values in the network. Each node may exchange with its neighbors a finite number of bits every time communication is initiated. In this paper, we present an algorithm for computation of separable functions, under the constraint that communicated messages are quantized, so that with some specified probability, all nodes have an estimate of the function value within a desired interval of accuracy. We derive an upper bound on the computation time needed to achieve this goal, and show that the dependence of the computation time on the network topology, via the ldquoconductancerdquo of the graph representing this topology, matches a lower bound derived from Information Theoretic analysis. Hence, the algorithmpsilas running time is optimal with respect to dependence on the graph structure.