  Motivated by decentralized sensing and policy evaluation problems, we
consider a particular type of distributed stochastic optimization problem over
a network, called the online stochastic distributed averaging problem. We
design a dual-based method for this distributed consensus problem with
Polyak--Ruppert averaging and analyze its behavior. We show that the proposed
algorithm attains an accelerated deterministic error depending optimally on the
condition number of the network, and also that it has an order-optimal
stochastic error. This improves on the guarantees of state-of-the-art
distributed stochastic optimization algorithms when specialized to this
setting, and yields -- among other things -- corollaries for decentralized
policy evaluation. Our proofs rely on explicitly studying the evolution of
several relevant linear systems, and may be of independent interest. Numerical
experiments are provided, which validate our theoretical results and
demonstrate that our approach outperforms existing methods in finite-sample
scenarios on several natural network topologies.
