#
Storage and search in dynamic peer-to-peer networks

##
John Augustine

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.)