Distributed Algorithms for Dynamic Replication of Data.

Ouri Wolfson, Sushil Jajodia: Distributed Algorithms for Dynamic Replication of Data. PODS 1992: 149-163

@inproceedings{DBLP:conf/pods/WolfsonJ92,
  author    = {Ouri Wolfson and
               Sushil Jajodia},
  title     = {Distributed Algorithms for Dynamic Replication of Data},
  booktitle = {Proceedings of the Eleventh ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, June 2-4, 1992, San Diego,
               California},
  publisher = {ACM Press},
  year      = {1992},
  isbn      = {0-89791-519-4},
  pages     = {149-163},
  ee        = {http://doi.acm.org/10.1145/137097.137858, db/conf/pods/WolfsonJ92.html},
  crossref  = {DBLP:conf/pods/92},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We present two distributed algorithms for dynamic replication of a data-item in communication networks. The algorithms are adaptive in the sense that they change the replication scheme of the item (i.e. the set of processors at which the data-item is replicated), as the read-write pattern of the processors in the network changes. Each algorithm continuously moves the replication scheme towards an optimal one, where optimality is defined with respect to different objective functions. One algorithm optimizes the communication cost objective function, and the other optimizes the communication time. We also provide a lower bound on the performance of any dynamic replication algorithm.

Copyright © 1992 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 Eleventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 2-4, 1992, San Diego, California. ACM Press 1992, ISBN 0-89791-519-4
Contents

Online Edition: ACM Digital Library

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

References

[AE1]: Divyakant Agrawal, Amr El Abbadi: Storage Efficient Replicated Databases. IEEE Trans. Knowl. Data Eng. 2(3): 342-352(1990)
[AE2]: ...
[ABG1]: Rafael Alonso, Daniel Barbará, Hector Garcia-Molina, Soraya Abad: Quasi-Copies: Efficient Data Sharing for Information Retrieval Systems. EDBT 1988: 443-468
[ABG2]: Rafael Alonso, Daniel Barbará, Hector Garcia-Molina: Data Caching Issues in an Information Retrieval System. ACM Trans. Database Syst. 15(3): 359-384(1990)
[B]: ...
[BG]: ...
[BHG]: Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5
Contents
[BLS]: Allan Borodin, Nathan Linial, Michael E. Saks: An Optimal Online Algorithm for Metrical Task Systems. STOC 1987: 373-382
[BS]: ...
[CP]: Stefano Ceri, Giuseppe Pelagatti: Distributed Databases: Principles and Systems. McGraw-Hill Book Company 1984, ISBN 0-07-010829-3
[CL]: ...
[DGS]: Susan B. Davidson, Hector Garcia-Molina, Dale Skeen: Consistency in Partitioned Networks. ACM Comput. Surv. 17(3): 341-370(1985)
[DF]: Lawrence W. Dowdy, Derrell V. Foster: Comparative Models of the File Assignment Problem. ACM Comput. Surv. 14(2): 287-313(1982)
[E]: ...
[GB]: Hector Garcia-Molina, Daniel Barbará: How to Assign Votes in a Distributed System. J. ACM 32(4): 841-860(1985)
[GS]: Bezalel Gavish, Olivia R. Liu Sheng: Dynamic File Migration in Distributed Computer Systems. Commun. ACM 33(2): 177-189(1990)
[GZ]: Ornan Ori Gerstel, Shmuel Zaks: A New Characterization of Tree Medians with Applications to Distributed Algorithms. WG 1992: 135-144
[H]: Maurice Herlihy: Dynamic Quorum Adjustment for Partitioned Data. ACM Trans. Database Syst. 12(2): 170-194(1987)
[KMRS]: Anna R. Karlin, Mark S. Manasse, Larry Rudolph, Daniel Dominic Sleator: Competitive Snoopy Caching. Algorithmica 3: 77-119(1988)
[KB]: Narayanan Krishnakumar, Arthur J. Bernstein: Bounded Ignorance in Replicated Systems. PODS 1991: 63-74
[LLS]: Rivka Ladin, Barbara Liskov, Liuba Shrira: A Technique for Constructing Highly Available Services. Algorithmica 3: 393-420(1988)
[J]: ...
[OV]: M. Tamer Özsu, Patrick Valduriez: Principles of Distributed Database Systems. Prentice-Hall 1991, ISBN 0-13-715681-2
[ST]: Daniel Dominic Sleator, Robert Endre Tarjan: Amortized Efficiency of List Update and Paging Rules. Commun. ACM 28(2): 202-208(1985)
[WM]: Ouri Wolfson, Amir Milo: The Multicast Policy and Its Relationship to Replicated Data Placement. ACM Trans. Database Syst. 16(1): 181-205(1991)
[Z]: ...