algorithms, we prove that the convergence time is $O(n^2/\eta)$, where $n$ is the number of agents and $\eta$ is a lower bound on the nonzero weights used in the algorithm. To the best of our knowledge, [*this is the best polynomial-time bound on the convergence time of such algorithms*]{}. We also show that this bound is tight. Since this result implies an $O(n^3)$ bound on convergence time. In Section \[matrixpicking\], we present a distributed algorithm that selects the weights dynamically, using three-hop neighborhood information. Under the assumption that the underlying connectivity graph at each iteration is undirected, we establish an improved $O(n^2)$ upper bound on convergence time. This matches the best available convergence time guarantee for the much simpler case of static connectivity graphs .

In the second part of the paper, we impose the additional constraint that agents can only store and transmit quantized values. This model provides a good approximation for communication networks that are subject to communication bandwidth constraints. We focus on a particular quantization rule, which rounds down the values to the nearest quantization level. We propose a distributed algorithm that uses quantized values and, using a slightly different Lyapunov function, we show that the algorithm 