Optimal Response Time Retrieval of Replicated Data.

Ling Tony Chen, Doron Rotem: Optimal Response Time Retrieval of Replicated Data. PODS 1994: 36-44

@inproceedings{DBLP:conf/pods/ChenR94,
  author    = {Ling Tony Chen and
               Doron Rotem},
  title     = {Optimal Response Time Retrieval of Replicated Data},
  booktitle = {Proceedings of the Thirteenth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, May 24-26, 1994, Minneapolis,
               Minnesota},
  publisher = {ACM Press},
  year      = {1994},
  isbn      = {0-89791-642-5},
  pages     = {36-44},
  ee        = {http://doi.acm.org/10.1145/182591.182596, db/conf/pods/pods94-36.html},
  crossref  = {DBLP:conf/pods/94},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

This work deals with the problem of finding efficient access plans for retrieving a set of pages from a multi-disk system with replicated data. The paper contains two results related to this problem: (a) We solve the problem of finding an optimal access path by transforming it into a network flow problem. We also indicate how our method may be employed indynamic environments where some (or all) of the disks have a preexisting load, are heterogeneous, and reside on different servers. (b) We present a lower bound for the worst case response time of a request under all replication schemes, and also discuss the replication scheme that results in this lower bound. We then use simulation to show how this replication scheme can also greatly reduce the average case response time.

Copyright © 1994 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
UNIX/LINUX/Mac: use mount point /pods8298/... or /cdrom/...

Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
UNIX/LINUX/Mac: use mount point /aDVD1/... or /cdrom/...

Printed Edition

Proceedings of the Thirteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 24-26, 1994, Minneapolis, Minnesota. ACM Press 1994, ISBN 0-89791-642-5
Contents

Online Edition: ACM Digital Library

[Abstract and Index Terms]
[Full Text in PDF Format, 758 KB]

References

[BG88]: Dina Bitton, Jim Gray: Disk Shadowing. VLDB 1988: 331-338
[CLR90]: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest: Introduction to Algorithms. The MIT Press and McGraw-Hill Book Company 1989, ISBN 0-262-03141-8,0-07-013143-0
[CR93]: Ling Tony Chen, Doron Rotem: Declustering Objects for Visualization. VLDB 1993: 85-96
[FF62]: ...
[GTT89]: ...
[LM92]: Raymond Wai-Man Lo, Norman S. Matloff: A Probabilistic Limit on the Virtual Size of Replicated Disk Systems. IEEE Trans. Knowl. Data Eng. 4(1): 99-102(1992)
[PBD93]: Christos A. Polyzois, Anupam Bhide, Daniel M. Dias: Disk Mirroring with Alternating Deferred Updates. VLDB 1993: 604-617
[RS92]: ...