Paving the Way for Consensus: Convergence of Block Gossip Algorithms

作     者：Haddock, Jamie Jarman, Benjamin Yap, Chen 

作者机构：Harvey Mudd Coll Dept Math Claremont CA 91711 USA Univ Calif Los Angeles Dept Math Los Angeles CA 90095 USA Planet Labs Inc San Francisco CA 94107 USA 

出 版 物：《IEEE TRANSACTIONS ON INFORMATION THEORY》 (IEEE Trans. Inf. Theory)

年 卷 期：2022年第68卷第11期

页      面：7515-7527页

核心收录：

学科分类：0808[工学-电气工程] 08[工学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：NSF CAREER [DMS 1348721] NSF [DMS 2211318] NSF BIGDATA [DMS 1740325] 

主　　题：Protocols Convergence Linear systems Iterative methods Eigenvalues and eigenfunctions Partitioning algorithms Distributed computing Average consensus randomized block gossip algorithms linear systems stochastic iterative methods randomized block Kaczmarz 

摘      要：Gossip protocols are popular methods for average consensus problems in distributed computing. We prove new convergence guarantees for a variety of such protocols, including path, clique, and synchronous pairwise gossip. These arise by exploiting the connection between these protocols and the block randomized Kaczmarz method for solving linear systems. Moreover, we extend existing convergence results for block randomized Kaczmarz to allow for a more general choice of blocks, rank-deficient systems, and provide a tighter convergence rate guarantee. Previous results for block randomized Kaczmarz assumed blocks formed a paving of the systems;our analysis, contrary to the title of our paper, generalizes to a broader class of blocks that we call coverings. We furthermore apply this analysis to inconsistent consensus models and obtain similar guarantees. An extensive empirical analysis of these methods is provided for a variety of synthetic and real networks.