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.
翻译:Gosip 协议是分布式计算中平均共识问题的流行方法。 我们证明对各种此类协议有新的趋同保障,包括路径、分级和同步对对对对流八卦。这些保证是通过利用这些协议与块状随机卡茨马尔兹解决线性系统的方法之间的联系产生的。此外,我们扩展了块块随机卡茨马尔兹的现有趋同结果,以允许对区块进行更普遍的选择、等级不完善的系统,并提供更严格的趋同率保证。我们进一步将这一分析运用于不一致的共识模型并获得类似的保证。我们为各种合成网络提供了对这些方法的广泛经验分析。