Optimal Gossip Algorithms for Exact and Approximate Quantile Computations

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