Replication
Strategies in Unstructured Peer-to-Peer Networks. Edith Cohen(AT&T Labs) and
Scott Shenker (ICSI)
The Peer-to-Peer (P2P) architectures that are most prevalent in today's
Internet are decentralized and unstructured. Search is blind in
that it is independent of the query and is thus not more effective than
probing randomly chosen peers. One technique to improve the effectiveness
of blind search is to proactively replicate data.
We evaluate and compare different replication strategies and reveal interesting
structure: Two very common but very different replication strategies --
uniform and proportional -- yield the same average performance on successful
queries, and are in fact worse than any replication strategy which lies
between them. The optimal strategy lies between the two and can be
achieved by simple distributed algorithms.
These fundamental results offer a new understanding of replication and show
that currently deployed replication strategies are far from optimal and that
optimal replication is attainable by protocols that resemble existing ones in
simplicity and operation.
Papers are provided as
a service to all by the members of ACM SIGCOMM.
This
paper is available in Adobe PDF format.
|