Quantized Consensus by the ADMM: Probabilistic Versus Deterministic Quantizers

This paper develops efficient algorithms for distributed average consensus with quantized communication using the alternating direction method of multipliers (ADMM). We first study the effects of probabilistic and deterministic quantizations on a distributed ADMM algorithm. With probabilistic quantization, this algorithm yields linear convergence to the desired average in the mean sense with a bounded variance. When deterministic quantization is employed, the distributed ADMM converges to a consensus within 3 + right perpendicularlog(1+delta) Omega left perpendicular iterations where delta > 0 depends on the network topology and Omega is a polynomial fraction depending on the quantization resolution, the agents' data, and the network topology. A tight upper bound on the consensus error is also obtained, which depends only on the quantization resolution and the average degree of the graph. This bound is much preferred in large scale networks over existing algorithms whose consensus errors are increasing in the range of agents' data, the quantization resolution, and the number of agents. We finally propose our algorithm which combines both probabilistic and deterministic quantizations. Simulations show that the consensus error of our algorithm is typically less than one quantization resolution for all connected networks where agents' data can be of arbitrary magnitudes.