# Optimal Gossip Algorithms for Exact and Approximate Quantile Computations

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Nov 2017.

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

- [Robust Distributed Estimation: Extending Gossip Algorithms to Ranking and Trimmed Means](https://mlsanity.com/paper/2505.17836/) (2025)
- [Fast networked data selection via distributed smoothed quantile estimation](https://mlsanity.com/paper/2406.01929/) (2024)

## Abstract (arXiv)

This paper gives drastically faster gossip algorithms to compute exact and approximate quantiles. Gossip algorithms, which allow each node to contact a uniformly random other node in each round, have been intensely studied and been adopted in many applications due to their fast convergence and their robustness to failures. Kempe et al. [FOCS'03] gave gossip algorithms to compute important aggregate statistics if every node is given a value. In particular, they gave a beautiful O(log n + log frac1ε) round algorithm to ε-approximate the sum of all values and an O(log2 n) round algorithm to compute the exact φ-quantile, i.e., the the lceil φ n rceil smallest value. We give an quadratically faster and in fact optimal gossip algorithm for the exact φ-quantile problem which runs in O(log n) rounds. We furthermore show that one can achieve an exponential speedup if one allows for an ε-approximation. We give an O(log log n + log frac1ε) round gossip algorithm which computes a value of rank between φ n and (φ+ε)n at every node.% for any 0 ≤ φ ≤ 1 and 0 < ε < 1. Our algorithms are extremely simple and very robust - they can be operated with the same running times even if every transmission fails with a, potentially different, constant probability. We also give a matching Omega(log log n + log frac1ε) lower bound which shows that our algorithm is optimal for all values of ε.