Distributed calculation of linear functions in noisy networks via linear iterations

Abstract

Given a fixed network where each node has some given initial value, and under the constraint that each node receives noisy transmissions from its immediate neighbors, we provide a distributed scheme for any node to calculate an unbiased estimate of an arbitrary linear function of the initial values. Our scheme consists of a linear iteration where, at each time-step, each node updates its value to be a weighted average of its own previous value and those of its neighbors. We show that after repeating this process with almost any set of weights for a finite number of time-steps (upper bounded by the size of the network), any node in the network will be able to calculate an unbiased estimate of any linear function by taking a linear combination of the values that it sees over the course of the linear iteration. For a given set of weights, this linear combination can also be optimized to minimize the variance of the unbiased estimate calculated by each node. © 2008 IEEE.