agents. Similar algorithms have been studied in the load-balancing literature (see for example [@C89]). Motivated by observed group behavior in biological and dynamical systems, the recent literature in cooperative control has studied similar algorithms and proved convergence results under various assumptions on agent connectivity and information exchange (see [@VCBJCS95], [@OSM04], [@RB05], [@M05], [@LR06]).

In this paper, our goal is to provide tight bounds on the convergence time (defined as the number of iterations required to reduce a suitable Lyapunov function by a constant factor) of a general class of consensus algorithms, as a function of the number $n$ of agents. We focus on algorithms that are designed to solve the averaging problem. We consider both problems where agents have access to exact values and problems where agents only have access to quantized values of the other agents. Our contributions can be summarized as follows.

In the first part of the paper, we consider the case where agents can exchange and store continuous values, which is a widely adopted assumption in the previous literature. We consider a large class of averaging algorithms defined by the condition that the weight matrix is a possibly nonsymmetric, doubly stochastic matrix. For this class of 