ACM SIGMOD Anthology TODS dblp.uni-trier.de

The Multicast Policy and Its Relationship to Replicated Data Placement.

Ouri Wolfson, Amir Milo: The Multicast Policy and Its Relationship to Replicated Data Placement. ACM Trans. Database Syst. 16(1): 181-205(1991)
@article{DBLP:journals/tods/WolfsonM91,
  author    = {Ouri Wolfson and
               Amir Milo},
  title     = {The Multicast Policy and Its Relationship to Replicated Data
               Placement},
  journal   = {ACM Trans. Database Syst.},
  volume    = {16},
  number    = {1},
  year      = {1991},
  pages     = {181-205},
  ee        = {http://doi.acm.org/10.1145/103140.103146, db/journals/tods/WolfsonM91.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

In this paper we consider the communication complexity of maintaining the replicas of a logical data-item, in a database distributed over a computer network. We propose a new method, called the minimum spanning tree write, by which a processor in the network should multicast a write of a logical data-item, to all the processors that store replicas of the item. Then we show that the minimum spanning tree write is optimal from the communication cost point of view. We also demonstrate that the method by which a write is mutlicast to all the replicas of a data-item affects the optimal replication scheme of the item, i.e., at which processors in the network the replicas should be located. Therefore, next we consider the problem of determining an optimal replication scheme for a data item, assuming that each processor employs the minimum spanning tree write at run-time. The problem for general networks is shown NP-Complete, but we provide efficient algorithms to obtain an optimal allocation scheme for three common types of network topologies. They are completely-connected, tree, and ring networks. For these topologies, efficient algorithms are also provided for the case in which reliability considerations dictate a minimum number of replicas.

Copyright © 1991 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.

Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 2, TODS 1991-1995, TKDE 1989-1992" and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

Online Edition: ACM Digital Library

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

References

[1]
...
[2]
...
[3]
David R. Cheriton, Willy Zwaenepoel: Distributed Process Groups in the V Kernel. ACM Trans. Comput. Syst. 3(2): 77-107(1985) BibTeX
[4]
...
[5]
...
[6]
Yogen K. Dalal, Robert Metcalfe: Reverse Path Forwarding of Broadcast Packets. Commun. ACM 21(12): 1040-1048(1978) BibTeX
[7]
Stephen E. Deering, David R. Cheriton: Multicast Routing in Datagram Internetworks and Extended LANs. ACM Trans. Comput. Syst. 8(2): 85-110(1990) BibTeX
[8]
Lawrence W. Dowdy, Derrell V. Foster: Comparative Models of the File Assignment Problem. ACM Comput. Surv. 14(2): 287-313(1982) BibTeX
[9]
Marshall L. Fisher, Dorit S. Hochbaum: Database Location in Computer Networks. J. ACM 27(4): 718-735(1980) BibTeX
[10]
...
[11]
Ephraim Korach, Doron Rotem, Nicola Santoro: Distributed Algorithms for Finding Centers and Medians in Networks. ACM Trans. Program. Lang. Syst. 6(3): 380-401(1984) BibTeX
[12]
Samy A. Mahmoud, J. Spruce Riordon: Optimal Allocation of Resources in Distributed Information Networks. ACM Trans. Database Syst. 1(1): 66-78(1976) BibTeX
[13]
...
[14]
Howard L. Morgan, K. Dan Levin: Optimal Program and Data Locations in Computer Networks. Commun. ACM 20(5): 315-322(1977) BibTeX
[15]
Shojiro Muro, Toshihide Ibaraki, Hidehiro Miyajima, Toshiharu Hasegawa: Evaluation of the File Redundancy in Distributed Database Systems. IEEE Trans. Software Eng. 11(2): 199-205(1985) BibTeX
[16]
...
[17]
C. V. Ramamoorthy, Benjamin W. Wah: The Isomorphism of Simple File Allocation. IEEE Trans. Computers 32(3): 221-232(1983) BibTeX
[18]
Adrian Segall, Ouri Wolfson: Transaction Commitment at Minimal Communication Cost. PODS 1987: 112-118 BibTeX
[19]
Clement T. Yu, Man-Keung Siu, K. Lam, C. H. Chen: Adaptive File Allocation in Star Computer Network. IEEE Trans. Software Eng. 11(9): 959-965(1985) BibTeX
[20]
...

Referenced by

  1. Ouri Wolfson, Sushil Jajodia, Yixiu Huang: An Adaptive Data Replication Algorithm. ACM Trans. Database Syst. 22(2): 255-314(1997)
  2. Salvatore T. March, Sangjyu Rho: Allocating Data and Operations to Nodes in Distributed Database Design. IEEE Trans. Knowl. Data Eng. 7(2): 305-317(1995)
  3. A. B. Stephens, Yelena Yesha, Keith E. Humenik: Optimal Allocation for Partially Replicated Database Systems on Ring Networks. IEEE Trans. Knowl. Data Eng. 6(6): 975-982(1994)
  4. Yixiu Huang, A. Prasad Sistla, Ouri Wolfson: Data Replication for Mobile Computers. SIGMOD Conference 1994: 13-24
  5. Yixiu Huang, Ouri Wolfson: Object Allocation in Distributed Databases and Mobile Computers. ICDE 1994: 20-29
  6. Yixiu Huang, Ouri Wolfson: A Competitive Dynamic Data Replication Algorithm. ICDE 1993: 310-317
  7. Ouri Wolfson, Sushil Jajodia: Distributed Algorithms for Dynamic Replication of Data. PODS 1992: 149-163
  8. Wesley W. Chu, Berthier A. Ribeiro-Neto, Patrick H. Ngai: Object Allocation in Distributed Systems with Virtual Replication. ICDE 1992: 238-245
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Tue Jun 24 18:39:10 2008