# A New Perspective on Randomized Gossip Algorithms

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Oct 2016.

## Built on by (most cited first, 4 of 4)

- [Single-Call Stochastic Extragradient Methods for Structured Non-monotone Variational Inequalities: Improved Analysis under Weaker Conditions](https://mlsanity.com/paper/2302.14043/) (2023)
- [Towards a Better Theoretical Understanding of Independent Subnetwork Training](https://mlsanity.com/paper/2306.16484/) (2023)
- [Enabling All In-Edge Deep Learning: A Literature Review](https://mlsanity.com/paper/2204.03326/) (2022)
- [On Gossip Algorithms for Machine Learning with Pairwise Objectives](https://mlsanity.com/paper/2603.24128/) (2026)

## Abstract (arXiv)

In this short note we propose a new approach for the design and analysis of randomized gossip algorithms which can be used to solve the average consensus problem. We show how that Randomized Block Kaczmarz (RBK) method - a method for solving linear systems - works as gossip algorithm when applied to a special system encoding the underlying network. The famous pairwise gossip algorithm arises as a special case. Subsequently, we reveal a hidden duality of randomized gossip algorithms, with the dual iterative process maintaining a set of numbers attached to the edges as opposed to nodes of the network. We prove that RBK obtains a superlinear speedup in the size of the block, and demonstrate this effect through experiments.