Discovery through gossip
From MaRDI portal
Publication:2811164
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 5454133 (Why is no real title available?)
- A distributed polylogarithmic time algorithm for self-stabilizing skip graphs
- A stochastic process on the hypercube with applications to peer-to-peer networks
- Almost tight bounds for rumour spreading with conductance
- Almost-optimal gossip-based aggregate computation
- Asynchronous resource discovery
- Complex social networks.
- Computing separable functions via gossip
- Fast Byzantine agreement in dynamic networks
- Fast distributed computation in dynamic networks via random walks
- Flooding time in edge-Markovian dynamic graphs
- Probability and Computing
- Problems and results in extremal combinatorics. II
- Randomized Rumor Spreading in Dynamic Graphs
- Resource discovery in distributed networks
- Self-* properties through gossiping
- Social networks spread rumors in sublogarithmic time
- Spatial gossip and resource location protocols
- T-Man: Gossip-based fast overlay topology construction
- The influence of search engines on preferential attachment
Cited in
(9)- Self-stabilizing repeated balls-into-bins
- Dynamic gossip
- A deterministic worst-case message complexity optimal solution for resource discovery
- Spatial gossip and resource location protocols
- Topology discovery of sparse random graphs with few participants
- Dynamics of gossip-like information dissemination in complex computer networks
- Spatial gossip and resource location protocols
- scientific article; zbMATH DE number 6747860 (Why is no real title available?)
- 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)
