Accessing the convergence rate of push-sum algorithms

Distributed average consensus is a process designed to compute the average of inputs on vertices using only communication along the edges of a graph. Such setups have an apparent applied motivation, as such this drives the questions and problem setups studied.

We currently analyze average consensus schemes based on one such popular protocol, push-sum (or ratio consensus), and our goal is to understand their almost sure exponential convergence rate. We present multiple ways to address this problem. One by identifying the exact convergence rate, however based on asymptotic quantities. It is then possible to construct multiple upper bounds for more restricted cases, balancing precision and scalability.

Joint work with L. Gerencsér, M. Kornyik.