Optimal gossip with direct addressing

DOI10.1145/2611462.2611489zbMATH Open1321.68468arXiv1402.2701OpenAlexW2071202952MaRDI QIDQ2943620FDOQ2943620

Authors: Bernhard Haeupler, Dahlia Malkhi 

Publication date: 3 September 2015

Published in: Proceedings of the 2014 ACM symposium on Principles of distributed computing (Search for Journal in Brave)

Abstract: Gossip algorithms spread information by having nodes repeatedly forward information to a few random contacts. By their very nature, gossip algorithms tend to be distributed and fault tolerant. If done right, they can also be fast and message-efficient. A common model for gossip communication is the random phone call model, in which in each synchronous round each node can PUSH or PULL information to or from a random other node. For example, Karp et al. [FOCS 2000] gave algorithms in this model that spread a message to all nodes in $Theta(logn)$ rounds while sending only $O(loglogn)$ messages per node on average. Recently, Avin and Els"asser [DISC 2013], studied the random phone call model with the natural and commonly used assumption of direct addressing. Direct addressing allows nodes to directly contact nodes whose ID (e.g., IP address) was learned before. They show that in this setting, one can "break the $logn$ barrier" and achieve a gossip algorithm running in $O(sqrtlogn)$ rounds, albeit while using $O(sqrtlogn)$ messages per node. We study the same model and give a simple gossip algorithm which spreads a message in only $O(loglogn)$ rounds. We also prove a matching $Omega(loglogn)$ lower bound which shows that this running time is best possible. In particular we show that any gossip algorithm takes with high probability at least $0.99loglogn$ rounds to terminate. Lastly, our algorithm can be tweaked to send only $O(1)$ messages per node on average with only $O(logn)$ bits per message. Our algorithm therefore simultaneously achieves the optimal round-, message-, and bit-complexity for this setting. As all prior gossip algorithms, our algorithm is also robust against failures. In particular, if in the beginning an oblivious adversary fails any $F$ nodes our algorithm still, with high probability, informs all but $o(F)$ surviving nodes.

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

Recommendations

• scientific article; zbMATH DE number 2061800
• scientific article; zbMATH DE number 2114510
• On optimal solutions to the problem of gossiping in minimum time
• Optimal gossiping in paths and cycles
• Optimal sequential gossiping by short messages
• Optimal odd gossiping
• Gossiping for communication-efficient broadcast
• Almost-optimal gossip-based aggregate computation
• Efficient gossip and robust distributed computation
• Efficient gossip and robust distributed computation

zbMATH Keywords

information disseminationrumor spreadingpeer-to-peer (P2P)gossippointer jumpingdirect addressing

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Distributed algorithms (68W15) Communication networks in operations research (90B18) Distributed systems (68M14)

Cited In (6)

• How efficient can gossip be? (On the cost of resilient information exchange)
• Gossip in a smartphone peer-to-peer network
• Brief announcement: Optimal address-oblivious epidemic dissemination
• Breathe before speaking: efficient information dissemination despite noisy, limited and anonymous communication
• Breaking the \(\log n\) barrier on rumor spreading
• Optimal gossip algorithms for exact and approximate quantile computations

This page was built for publication: Optimal gossip with direct addressing

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