Optimal gossip algorithms for exact and approximate quantile computations

DOI10.1145/3212734.3212770MaRDI QIDQ5197682zbMATH OpenOpenAlexFDO

Authors Bernhard Haeupler, Jeet Mohapatra, Hsin-Hao Su

Publication date 19 September 2019

Published in Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1711.09258

zbMATH Keywords

fault tolerancegossip algorithmsmedianquantile computationsensor networks

Mathematics Subject Classification ID

Distributed systems (68M14) Reliability, testing and fault tolerance of networks and computer systems (68M15) Wireless sensor networks as related to computer science (68M18) Distributed algorithms (68W15)

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(logn+logfrac1epsilon)$ round algorithm to $epsilon$-approximate the sum of all values and an $O(lo{g}^{2}n)$ round algorithm to compute the exact $phi$-quantile, i.e., the the $lceilphinceil$ smallest value. We give an quadratically faster and in fact optimal gossip algorithm for the exact $phi$-quantile problem which runs in $O(logn)$ rounds. We furthermore show that one can achieve an exponential speedup if one allows for an $epsilon$-approximation. We give an $O(loglogn+logfrac1epsilon)$ round gossip algorithm which computes a value of rank between $phin$ and $(phi+epsilon)n$ at every node.% for any $0leqphileq1$ 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(loglogn+logfrac1epsilon)$ lower bound which shows that our algorithm is optimal for all values of $epsilon$.

Recommendations

• Almost-optimal gossip-based aggregate computation
• Simple, fast and deterministic gossip and rumor spreading
• Simple, fast and deterministic gossip and rumor spreading
• Optimal gossip with direct addressing
• Gossip consensus algorithms via quantized communication

Cited in

(6)

• Almost-optimal gossip-based aggregate computation
• A Generalized Gossip Algorithm on Convex Metric Spaces
• Distributed approximation and tracking using selective gossip
• Quantized Consensus by Means of Gossip Algorithm
• Fast distributed algorithms for LP-type problems of low dimension
• Distributed data summarization in well-connected networks

This page was built for publication: Optimal gossip algorithms for exact and approximate quantile computations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5197682)