2021/10/27 by Jamie Haddock, Haddock, Jamie, Benjamin Jarman +3 · 1 citation
Computer Science · Engineering · #Distributed #Distributed Control Multi-Agent Systems #Distributed systems and fault tolerance #FOS: Computer and information sciences #FOS: Electrical engineering #FOS: Mathematics #Modular Robots and Swarm Intelligence #Multiagent Systems (cs.MA) #Optimization and Control (math.OC) #Parallel #Systems and Control (eess.SY) #and Cluster Computing (cs.DC) #electronic engineering #information engineering
paper · pdf · doi:10.48550/arxiv.2110.14609
openalex publication_date 2021/10/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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. 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 networks.