Peer-to-Peer (P2P) networks are highly dynamic decentralized networks that experience heavy node churn, i.e., nodes join and leave the network continuously over time. We model such P2P systems as synchronous dynamic networks. In each round, an adversary can add and remove a large number of nodes, and also rewire the network subject to some connectivity constraints. We are interested in solving the problem of storing and searching data items despite such high churn rate and network dynamism. In the course of solving this problem, we develop a random walks based sampling technique to sample nodes uniformly at random from the network. While it is well known that random walks are useful for sampling, their application in our context is nontrivial because the churn and network dynamism can potentially bias them or even destroy them. Furthermore, we believe that this sampling technique may prove to be useful in a variety of other applications.
(From joint work with Anisur Molla, Ehab Morsy, Gopal Pandurangan, Peter Robinson, and Eli Upfal, presented at SPAA 2013.)