  The problem of network-constrained averaging is to compute the average of a
set of values distributed throughout a graph G using an algorithm that can pass
messages only along graph edges. We study this problem in the noisy setting, in
which the communication along each link is modeled by an additive white
Gaussian noise channel. We propose a two-phase decentralized algorithm, and we
use stochastic approximation methods in conjunction with the spectral graph
theory to provide concrete (non-asymptotic) bounds on the mean-squared error.
Having found such bounds, we analyze how the number of iterations T_G(n;
\delta) required to achieve mean-squared error \delta\ scales as a function of
the graph topology and the number of nodes n. Previous work provided guarantees
with the number of iterations scaling inversely with the second smallest
eigenvalue of the Laplacian. This paper gives an algorithm that reduces this
graph dependence to the graph diameter, which is the best scaling possible.
