  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.
