Low complexity convergence rate bounds for the synchronous gossip subclass of push-sum algorithms

Average consensus algorithms have been around for a while [2], [18], with the fundamental goal of computing the average of input values on a network in a distributed manner with only local communication and simple operations. Often some symmetry is imposed on the communication, in terms of the matrix describing the linear update of the vector of values to be either doubly stochastic, or even symmetric. This condition is quite well understood [17], see the survey [16] also for applications, further discussion and references. However, the interest for distributed averaging algorithms capable of handling asynchronous directed communications emerged, naturally driving away the representing update matrix from being doubly stochastic, still with the intent to compute the exact average. As a result, the successful scheme of push-sum was proposed [11], later also investigated under the name ratio consensus [7] and joined by variants such as weighted gossip [1]. The goal of these algorithms is the same, but now using only local, directed communication and without requiring message passing to happen synchronously or consistently across the network. Given the simple objective of the algorithm, it also serves as a building block for more complex tasks, e.g., the spectral analysis of the network [12] or distributed optimization algorithms [13].