Szemerédi Levente (ELTE): Convergence rate of ratio consensus algorithms with virtual nodes

In the field of distributed computation, ratio consensus problems are concerned about finding the weighted average of values associated to nodes of the network. The almost sure exponential convergence rate is understood in the case when the communication protocol can be described as a strictly stationary, ergodic, sequentially primitive sequence of nonnegative matrices which are applied iteratively to a pair of initial vectors, the values and the weights at the nodes. However, many communication protocols cannot be described this way. Motivated by a modified version of one of the classical algorithms to be able to handle package loss we started to generalize the class of protocols for which the convergence rate can be identified by weakening the condition of sequentially primitivity.

 

I will talk about the push sum method and its variations, especially the motivating example. Then I will present the results on the convergence rate by Gerencsér and Gerencsér and our generalizations.

 

Joint work with Balázs Gerencsér.