2019/01/31 by Balázs Gerencsér, Gerencsér, Balázs, László Gerencsér +1 · 1 citation
Computer Science · Materials Science · Mathematics · #37A25 #68M10 #68W15 #90B18 #93A14 #Distributed #FOS: Computer and information sciences #FOS: Mathematics #Nanocluster Synthesis and Applications #Parallel #Probability (math.PR) #Random Matrices and Applications #Topological and Geometric Data Analysis #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1901.11374
openalex publication_date 2019/01/31 · openalex created_date 2022/07/30 · openalex updated_date 2026/07/28
The problems discussed in this paper are motivated by general ratio consensus\nalgorithms, introduced by Kempe, Dobra, and Gehrke (2003) in a simple form as\nthe push-sum algorithm, later extended by B 'en 'ezit et al. (2010) under the\nname weighted gossip algorithm. We consider a communication protocol described\nby a strictly stationary, ergodic, sequentially primitive sequence of\nnon-negative matrices, applied iteratively to a pair of fixed initial vectors,\nthe components of which are called values and weights defined at the nodes of a\nnetwork. The subject of ratio consensus problems is to study the asymptotic\nproperties of ratios of values and weights at each node, expecting convergence\nto the same limit for all nodes. The main results of the paper provide upper\nbounds for the rate of the almost sure exponential convergence in terms of the\nspectral gap associated with the given sequence of random matrices. It will be\nshown that these upper bounds are sharp. Our results complement previous\nresults of Picci and Taylor (2013) and Iutzeler, Ciblat and Hachem (2013).\n