Campus Event Calendar
Event Entry
What and Who
Near-Optimal Dynamic Replication in Unstructured Peer-to-Peer Networks
Luis de la Garza
International Max Planck Research School for Computer Science - IMPRS-CS
Masterseminar
AG 1, AG 3, AG 4, AG 5, SWS, RG1, MMCI
Public Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Wednesday, 15 July 2009
13:05
60 Minutes
E1 4
024
Saarbrücken
Abstract
Replicating data in distributed systems is often needed for
availability and performance. In unstructured peer-to-peer
networks, with epidemic messaging for query routing, repli-
cating popular data items is also crucial to ensure high prob-
ability of finding the data within a bounded search distance
from the requestor. This paper considers such networks and
aims to maximize the probability of successful search. Prior
work along these lines has analyzed the optimal degrees of
replication for data items with non-uniform but global re-
quest rates, but did not address the issue of where replicas
should be placed and was very very limited in the capabili-
ties for handling heterogeneity and dynamics of network and
workload.
This paper presents the integrated P2R2 algorithm for
dynamic replication that addresses all these issues, and de-
termines both the degrees of replication and the placement
of the replicas in a provably near-optimal way. We prove
that the P2R2 algorithm can guarantee a successful-search
probability that is within a factor of 2 of the optimal so-
lution. The algorithm is effcient and can handle workload
evolution. We prove that, whenever the access patterns are
in steady state, our algorithm converges to the desired near-
optimal placement. We further show by simulations that the
convergence rate is fast and that our algorithm outperforms
prior methods.
availability and performance. In unstructured peer-to-peer
networks, with epidemic messaging for query routing, repli-
cating popular data items is also crucial to ensure high prob-
ability of finding the data within a bounded search distance
from the requestor. This paper considers such networks and
aims to maximize the probability of successful search. Prior
work along these lines has analyzed the optimal degrees of
replication for data items with non-uniform but global re-
quest rates, but did not address the issue of where replicas
should be placed and was very very limited in the capabili-
ties for handling heterogeneity and dynamics of network and
workload.
This paper presents the integrated P2R2 algorithm for
dynamic replication that addresses all these issues, and de-
termines both the degrees of replication and the placement
of the replicas in a provably near-optimal way. We prove
that the P2R2 algorithm can guarantee a successful-search
probability that is within a factor of 2 of the optimal so-
lution. The algorithm is effcient and can handle workload
evolution. We prove that, whenever the access patterns are
in steady state, our algorithm converges to the desired near-
optimal placement. We further show by simulations that the
convergence rate is fast and that our algorithm outperforms
prior methods.
Contact
imprs
225
--email hidden
passcode not visible
logged in users only
Jennifer Gerling, 07/09/2009 16:00 -- Created document.