Optimal Replication in Random Search Networks
<P>
Edith Cohen
(AT&T Labs-Research)

<P>
Peer-to-peer (P2P) systems, almost unheard of two years ago, are now
one of the most popular Internet applications and a very significant
source of Internet traffic.  Despite their growing importance, the
performance of P2P systems is not yet well understood.
<P>

Decentralized and unstructured Peer-to-Peer systems (P2P), such as
Gnutella, can be modeled as {\em random search networks} where
searching is done by probing a series of randomly chosen hosts.  One
technique to improve the performance of random searches is to
proactively replicate data.  We explore the performance of different
replication strategies.  We show that, somewhat surprisingly, two
very common but very different strategies -- uniform and
proportional -- yield exactly the same performance.  We then define
the optimal replication strategy and show how it can be achieved with
a simple distributed algorithm.
<P>
 This is joint work with Scott Shenker.