Title: Optimal Gossip Algorithms for Exact and Approximate Quantile Computations,
Abstract: 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 \frac{1}{\epsilon})$ round algorithm to $\epsilon$-approximate
the sum of all values and an $O(\log^2 n)$ round algorithm to compute the exact
$\phi$-quantile, i.e., the the $\lceil \phi n \rceil$ smallest value.
We give an quadratically faster and in fact optimal gossip algorithm for the
exact $\phi$-quantile problem which runs in $O(\log n)$ rounds. We furthermore
show that one can achieve an exponential speedup if one allows for an
$\epsilon$-approximation. We give an $O(\log \log n + \log \frac{1}{\epsilon})$
round gossip algorithm which computes a value of rank between $\phi n$ and
$(\phi+\epsilon)n$ at every node.% for any $0 \leq \phi \leq 1$ and $0 <
\epsilon < 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 \frac{1}{\epsilon})$ lower bound which shows that
our algorithm is optimal for all values of $\epsilon$.