Optimal Replication in Random Search Networks

Edith Cohen (AT&T Labs-Research)

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.

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.

This is joint work with Scott Shenker.