  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 also describe an algorithm within this
class whose convergence time is the best among currently available averaging
algorithms for time-varying topologies. We then propose and analyze distributed
averaging algorithms under the additional constraint that agents can only store
and communicate quantized information, so that they can only 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.
