# Non asymptotic bounds in asynchronous sum-weight gossip protocols

arXiv: https://arxiv.org/abs/2111.10248 · HTML: https://mlsanity.com/paper/2111.10248/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 3 of its 18 references that are in the map.
- First posted on arXiv 19 Nov 2021.

## Builds on (most cited first, 3 of 3)

- [Gossip Dual Averaging for Decentralized Optimization of Pairwise Functions](https://mlsanity.com/paper/1606.02421/) (2016)
- [Improved Cheeger's Inequality: Analysis of Spectral Partitioning Algorithms through Higher Order Spectral Gap](https://mlsanity.com/paper/1301.5584/) (2013)
- [GoSGD: Distributed Optimization for Deep Learning with Gossip Exchange](https://mlsanity.com/paper/1804.01852/) (2018)

## Abstract (arXiv)

This paper focuses on non-asymptotic diffusion time in asynchronous gossip protocols. Asynchronous gossip protocols are designed to perform distributed computation in a network of nodes by randomly exchanging messages on the associated graph. To achieve consensus among nodes, a minimal number of messages has to be exchanged. We provides a probabilistic bound to such number for the general case. We provide a explicit formula for fully connected graphs depending only on the number of nodes and an approximation for any graph depending on the spectrum of the graph.