Campus Event Calendar
Event Entry
What and Who
Replication in Unstructured P2P Networks with Availability Constraints
Stefan Holder
Max-Planck-Institut für Informatik - IMPRS
Masterseminar
AG 1, AG 2, AG 3, AG 4, AG 5, SWS, RG1, RG2
Public Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 22 April 2008
13:00
60 Minutes
E1 4
024
Saarbrücken
Abstract
Random walks are one approach for decentralized search in unstructured peer-to-peer (P2P) networks. In this search strategy, a
query is forwarded by each peer to a random neighbor. A replication strategy is then required to achieve a sufficiently high probability for finding requested data items. In this context, we investigate the problem to minimize the number of replicas needed to achieve a given availability constraint. An availability constraint is a minimum threshold for the probability to find an existing data item via random walks and can be specified for every data item and every peer. It turns out that this optimization problem can be formulated as a generalization of the partial set cover problem. Because of the NP-hardness of the
(partial) set cover problem, we use a greedy approximation algorithm to compute an optimal replica distribution and we investigate the worst-case approximation ratio of our algorithm. Finally, our goal is to develop a distributed replication algorithm that only requires local knowledge of the network.
query is forwarded by each peer to a random neighbor. A replication strategy is then required to achieve a sufficiently high probability for finding requested data items. In this context, we investigate the problem to minimize the number of replicas needed to achieve a given availability constraint. An availability constraint is a minimum threshold for the probability to find an existing data item via random walks and can be specified for every data item and every peer. It turns out that this optimization problem can be formulated as a generalization of the partial set cover problem. Because of the NP-hardness of the
(partial) set cover problem, we use a greedy approximation algorithm to compute an optimal replica distribution and we investigate the worst-case approximation ratio of our algorithm. Finally, our goal is to develop a distributed replication algorithm that only requires local knowledge of the network.
Contact
imprs
225
--email hidden
passcode not visible
logged in users only
Stephanie Jörg, 03/31/2008 10:00
Jennifer Gerling, 03/27/2008 10:09 -- Created document.
Jennifer Gerling, 03/27/2008 10:09 -- Created document.