Optimal Gossip Algorithms for Exact and Approximate Quantile Computations

Bernhard Haeupler, Jeet Mohapatra, Hsin-Hao Su

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…