---
abstract: 'We consider distributed iterative algorithms for the averaging problem over time-varying topologies. Our focus is on the convergence time of such algorithms when complete (unquantized) information is available, and on the degradation of performance when only quantized information is available. We study a large and natural class of averaging algorithms, which includes the vast majority of algorithms proposed to date, and provide tight polynomial bounds on their convergence time. We then propose and analyze distributed averaging algorithms under the additional constraint that agents can only store and communicate quantized information, converge to the average of the initial values of the agents within some error. We establish bounds on the error and tight bounds on the convergence time, as a function of the number of quantization levels.'
author:
- 'Angelia Nedić[^1], Alex Olshevsky, Asuman Ozdaglar, and John N. Tsitsiklis[^2]'
bibliography:
- 'distributed\_alex.bib'
title: ' **On Distributed Averaging Algorithms and Quantization Effects[^3]**'
---

Introduction
============

There has been much recent interest in distributed control and coordination of networks consisting of multiple, potentially mobile, agents. This is motivated mainly by the emergence of large scale networks, characterized by the lack of centralized access to information and time-varying connectivity. Control and optimization 