Tight Bounds on the Convergence Rate of Generalized Ratio Consensus Algorithms

• 成果类型: Article
• 署名作者: Gerencser, Balazs; Gerencser, Laszlo
• 署名单位: HUN-REN; HUN-REN Alfred Renyi Institute of Mathematics; Eotvos Lorand University; HUN-REN; HUN-REN Institute for Computer Science & Control
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2021.3067629
• 发表日期: 2022
• 页码: 1669-1684
• 关键词: convergence; Upper bound; Consensus algorithm; Symmetric matrices; Heuristic algorithms; Technological innovation; Protocols; Asynchronous communication; CONVERGENCE; communication networks; distributed computing; estimation; Iterative algorithms; multiagent systems; Random processes; spectral gap

摘要

The problems discussed in this article are motivated by general ratio consensus algorithms, introduced by Kempe et al. in 2003 in a simple form as the push-sum algorithm, later extended by Benezit et al. in 2010 under the name weighted gossip algorithm. We consider a communication protocol described by a strictly stationary, ergodic, sequentially primitive sequence of nonnegative matrices, applied iteratively to a pair of fixed initial vectors, the components of which are called values and weights defined at the nodes of a network. The subject of ratio consensus problems is to study the asymptotic properties of ratios of values and weights at each node, expecting convergence to the same limit for all nodes. The main results of this article provide upper bounds for the rate of the almost sure exponential convergence in terms of the spectral gap associated with the given sequence of random matrices. It will be shown that these upper bounds are sharp. Our results complement previous results of Picci and Taylor in 2013 and Iutzeler et al. in 2013.