Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








Author, Editor

Author(s):

Sozio, Mauro
Neumann, Thomas
Weikum, Gerhard

dblp
dblp
dblp



Editor(s):

Lenzerini, Maurizio
Lembo, Domenico

dblp
dblp

Not MPII Editor(s):

Lenzerini, Maurizio
Lembo, Domenico

BibTeX cite key*:

SozioNW2008

Title, Booktitle

Title*:

Near-Optimal Dynamic Replication in Unstructured Peer-to-Peer Networks.

Booktitle*:

Proceedings of the Conference on Principles of Database System (PODS 2008)

Event, URLs

URL of the conference:


URL for downloading the paper:


Event Address*:

Vancouver, Canada

Language:

English

Event Date*
(no longer used):


Organization:


Event Start Date:

9 June 2008

Event End Date:

12 April 2008

Publisher

Name*:

ACM

URL:


Address*:

NY, USA

Type:


Vol, No, Year, pp.

Series:


Volume:


Number:


Month:

June

Pages:

281-290

Year*:

2008

VG Wort Pages:


ISBN/ISSN:

978-1-60558-108-8

Sequence Number:


DOI:




Note, Abstract, ©


(LaTeX) 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, replicating popular data items is also crucial to ensure high probability 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 request rates, but did not address the issue of where replicas should be placed and was very very limited in the capabilities 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 determines 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 solution. The algorithm is efficient 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.



Download
Access Level:

Institute

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Databases and Information Systems Group

Audience:

popular

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{SozioNW2008,
AUTHOR = {Sozio, Mauro and Neumann, Thomas and Weikum, Gerhard},
EDITOR = {Lenzerini, Maurizio and Lembo, Domenico},
TITLE = {Near-Optimal Dynamic Replication in Unstructured Peer-to-Peer Networks.},
BOOKTITLE = {Proceedings of the Conference on Principles of Database System (PODS 2008)},
PUBLISHER = {ACM},
YEAR = {2008},
PAGES = {281--290},
ADDRESS = {Vancouver, Canada},
MONTH = {June},
ISBN = {978-1-60558-108-8},
}


Entry last modified by Martin Theobald, 04/17/2009
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Olha Condor
Created
04/16/2008 03:29:50 PM
Revisions
4.
3.
2.
1.
0.
Editor(s)
Martin Theobald
Martin Theobald
Ralf Schenkel
Olha Condor
Olha Condor
Edit Dates
04/17/2009 04:56:13 PM
04/15/2009 02:12:50 PM
07.04.2009 15:28:46
17.11.2008 15:57:09
16.04.2008 15:39:33