Hsin-Hao Su
Optimal Gossip Algorithms for Exact and Approximate Quantile
Computations
Abstract: 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
(1/eps)) round algorithm to eps-approximate the sum of all values and
an O(log^2 n) round algorithm to compute the exact phi-quantile, i.e.,
the [phi n] smallest value.
We give a 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 eps-approximation. We give an O(log log n + log(1/eps) )
round gossip algorithm which computes a value of rank between phi n
and (phi+eps)n at every node. 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 logn+log(1/eps) ) lower
bound which shows that our algorithm is optimal for all values of eps.
Joint work with Bernhard Haeupler and Jeet Mohapatra