Discovery through Gossip

Details Discovery through Gossip Discovery through Gossip

2012-02-09

arxiv.org/abs/1202.2092v1

Computer Science

Distributed, Parallel, and Cluster Computing

19 pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Discovery through Gossip does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Discovery through Gossip, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Discovery through Gossip will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-158640