Discovery through gossip

DOI10.1002/RSA.20621zbMATH Open1338.05253arXiv1202.2092OpenAlexW2302291170MaRDI QIDQ2811164FDOQ2811164

Gopal Pandurangan, David Peleg, Rajmohan Rajaraman, Zhifeng Sun, Bernhard Haeupler

Publication date: 10 June 2016

Published in: Random Structures \& Algorithms (Search for Journal in Brave)

Abstract: We study randomized gossip-based processes in dynamic networks that are motivated by discovery processes in large-scale distributed networks like peer-to-peer or social networks. A well-studied problem in peer-to-peer networks is the resource discovery problem. There, the goal for nodes (hosts with IP addresses) is to discover the IP addresses of all other hosts. In social networks, nodes (people) discover new nodes through exchanging contacts with their neighbors (friends). In both cases the discovery of new nodes changes the underlying network - new edges are added to the network - and the process continues in the changed network. Rigorously analyzing such dynamic (stochastic) processes with a continuously self-changing topology remains a challenging problem with obvious applications. This paper studies and analyzes two natural gossip-based discovery processes. In the push process, each node repeatedly chooses two random neighbors and puts them in contact (i.e., "pushes" their mutual information to each other). In the pull discovery process, each node repeatedly requests or "pulls" a random contact from a random neighbor. Both processes are lightweight, local, and naturally robust due to their randomization. Our main result is an almost-tight analysis of the time taken for these two randomized processes to converge. We show that in any undirected n-node graph both processes take O(n log^2 n) rounds to connect every node to all other nodes with high probability, whereas Omega(n log n) is a lower bound. In the directed case we give an O(n^2 log n) upper bound and an Omega(n^2) lower bound for strongly connected directed graphs. A key technical challenge that we overcome is the analysis of a randomized process that itself results in a constantly changing network which leads to complicated dependencies in every round.

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

Recommendations

• Spatial gossip and resource location protocols
• Spatial gossip and resource location protocols
• Simple, fast and deterministic gossip and rumor spreading
• Simple, fast and deterministic gossip and rumor spreading
• Gossip vs. Markov chains, and randomness-efficient rumor spreading

zbMATH Keywords

social networkdistributed algorithmprobabilistic analysisrandom processresource discoverygossip-based algorithm

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Stochastic network models in operations research (90B15)

Cites Work

• Flooding time in edge-Markovian dynamic graphs
• Title not available (Why is that?)
• Probability and Computing
• Title not available (Why is that?)
• Problems and results in extremal combinatorics. II
• A distributed polylogarithmic time algorithm for self-stabilizing skip graphs
• Social networks spread rumors in sublogarithmic time
• T-Man: Gossip-based fast overlay topology construction
• A stochastic process on the hypercube with applications to peer-to-peer networks
• Spatial gossip and resource location protocols
• Almost tight bounds for rumour spreading with conductance
• Computing separable functions via gossip
• Resource discovery in distributed networks
• Fast byzantine agreement in dynamic networks
• Randomized Rumor Spreading in Dynamic Graphs
• Asynchronous resource discovery
• Fast Distributed Computation in Dynamic Networks via Random Walks
• Almost-optimal gossip-based aggregate computation
• The influence of search engines on preferential attachment
• Self-* properties through gossiping

Cited In (6)

• Self-stabilizing repeated balls-into-bins
• Dynamic gossip
• A deterministic worst-case message complexity optimal solution for resource discovery
• Dynamics of gossip-like information dissemination in complex computer networks
• Title not available (Why is that?)
• A Deterministic Worst-Case Message Complexity Optimal Solution for Resource Discovery

This page was built for publication: Discovery through gossip

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