MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Rajaraman, Rajmohan
Richa, Andrea W.
Vöcking, Berthold
Vuppuluri, Gayathri
dblp
dblp
dblp
dblp
Editor(s):
BibTeX cite key*:
Voecking2001a
Title, Booktitle
Title*:
A Data Tracking Scheme for General Networks
Booktitle*:
Proceedings of the 13th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA-01)
Event, URLs
Conference URL::
Downloading URL:
Event Address*:
Crete Island, Greece
Language:
English
Event Date*
(no longer used):
July, 3-6, 2001
Organization:
Event Start Date:
3 July 2001
Event End Date:
6 July 2001
Publisher
Name*:
ACM
URL:
Address*:
New York
Type:
Vol, No, Year, pp.
Series:
Volume:
Number:
Month:
Pages:
247-254
Year*:
2001
VG Wort Pages:
ISBN/ISSN:
1-58113-409-6
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
Consider an arbitrary distributed network in which large numbers of
objects are continuously being created, replicated, and destroyed. A
basic problem arising in such an environment is that of organizing a
distributed directory service for locating object copies. In this
paper, we present a new {\em data tracking scheme}\/ for locating
nearby copies of objects in arbitrary distributed environments.

Our tracking scheme supports efficient accesses to data objects while
keeping the local memory overhead low. In particular, our tracking
scheme achieves an expected $\polylog(n)$-approximation in the cost of
any access operation, for an arbitrary network. The memory overhead
incurred by our scheme is $O(\polylog(n))$ times the maximum number of
objects stored at any node, with high probability. We also show that
our tracking scheme adapts well to dynamic changes in the network.
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Audience:
Expert
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat



BibTeX Entry:

@INPROCEEDINGS{Voecking2001a,
AUTHOR = {Rajaraman, Rajmohan and Richa, Andrea W. and V{\"o}cking, Berthold and Vuppuluri, Gayathri},
TITLE = {A Data Tracking Scheme for General Networks},
BOOKTITLE = {Proceedings of the 13th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA-01)},
PUBLISHER = {ACM},
YEAR = {2001},
PAGES = {247--254},
ADDRESS = {Crete Island, Greece},
ISBN = {1-58113-409-6},
}


Entry last modified by Uwe Brahm, 03/02/2010
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)
Berthold Voecking
Created
03/17/2002 05:22:54 PM
Revisions
5.
4.
3.
2.
1.
Editor(s)
Uwe Brahm
Anja Becker
Anja Becker
Berthold Voecking
Berthold Voecking
Edit Dates
02/14/2005 09:43:41 PM
08.04.2002 12:51:50
22.03.2002 13:25:58
17/03/2002 17:30:43
17/03/2002 17:28:23