Notes on Linear Gossip Algorithms:Potentials and Challenges  

作　　者：GERENCSER Balazs GERENCSER Laszlo 

机构地区：[1]HUN-REN Alfred Renyi Institute of Mathematics,Budapest 1052,Hungary and Eotvos Lorand University,Department of Probability and Statistics,Budapest 1518,Hungary [2]HUN-REN SZTAKI,Institute for Computer Science and Control,Budapest 1111,Hungary

出　　处：《Journal of Systems Science & Complexity》2025年第1期98-128,共31页系统科学与复杂性学报(英文版)

基　　金：supported by the Ministry of Innovation and Technology,NRDI(National Research,Development and Innovation Office)under Grant No.KKP 137490;its Autonomous Systems National Laboratory Program(ARNL)。

摘　　要：The authors consider the problem of reaching consensus over a communication network via asynchronous interaction between pairs of agents.A well-known method is the linear gossip algorithm due to Tsitsiklis(1984).Extension of this,allowing the selection of a strictly stationary sequence of communicating pairs,was given in Picci and Taylor(2013).Extension of the linear gossip algorithm to directed communication networks,retaining the linear dynamics,was proposed by Cai and Ishii(2012),later extended by Silvestre,et al.(2018).A definite novelty of these algorithms is that L2-convergence with exponential rate can be established.The authors attend the above issues,extending the result of Picci and Taylor(2013)motivated by features of algorithms for directed networks.The authors present and discuss the algorithm of Silvestre,et al.(2018),together with systematic simulation results based on 5M randomly chosen parameter settings.The core of the proposed mathematical technology is a set of simple observations,presented with a tutorial aspect,by which the authors can conveniently establish various results on the almost sure convergence of products of strictly stationary sequences of matrices to a rank-1 matrix.

关 键 词：CONSENSUS gossip algorithms Lyapunov-exponents spectral gap 

分 类 号：O175[理学—数学] TP301.6[理学—基础数学]