Experimental Evaluation of Dynamic Data Allocation Strategies in A Distributed Database with Changing Workloads.

Anna Brunstrom, Scott T. Leutenegger, Rahul Simha: Experimental Evaluation of Dynamic Data Allocation Strategies in A Distributed Database with Changing Workloads. CIKM 1995: 395-402
  author    = {Anna Brunstrom and
               Scott T. Leutenegger and
               Rahul Simha},
  title     = {Experimental Evaluation of Dynamic Data Allocation Strategies
               in A Distributed Database with Changing Workloads},
  booktitle = {CIKM '95, Proceedings of the 1995 International Conference on
               Information and Knowledge Management, November 28 - December
               2, 1995, Baltimore, Maryland, USA},
  publisher = {ACM},
  year      = {1995},
  pages     = {395-402},
  ee        = {db/conf/cikm/BrunstromLS95.html,},
  crossref  = {DBLP:conf/cikm/95},
  bibsource = {DBLP,}


Traditionally, allocation of data in distributed database management systems has been determined by off-line anidysis and optimization. This technique works well for static database access patterns, but is often inadequate for frequently changing workloads. This paper addresses the problem of dynamically reallocating data in a partionable distributed database with changing access patterns. Rather than complicated and expensive optimization algorithms, a simple heuristic is presented and shown, via an implementation study, to improve system throughput by 30% in a local area net work based system. For a wide area network the performance gain is expected to be even larger. It is also shown that individual site load must be taken into consideration when reallocating data. A a simple policy that incorporates load in the reallocation decision is provided.

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

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 2 Issue 4, CIKM, DOLAP, GIS, SIGFIDET, ..." and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

CIKM '95, Proceedings of the 1995 International Conference on Information and Knowledge Management, November 28 - December 2, 1995, Baltimore, Maryland, USA. ACM 1995
Contents BibTeX

Online Edition

Citation Page BibTeX


Peter M. G. Apers: Data Allocation in Distributed Database Systems. ACM Trans. Database Syst. 13(3): 263-304(1988) BibTeX
Baruch Awerbuch, Yair Bartal, Amos Fiat: Competitive distributed file allocation. STOC 1993: 164-173 BibTeX
Michael J. Carey, David J. DeWitt, Daniel Frank, Goetz Graefe, M. Muralikrishna, Joel E. Richardson, Eugene J. Shekita: The Architecture of the EXODUS Extensible DBMS. OODBS 1986: 52-65 BibTeX
Stefano Ceri, Giancarlo Martella, Giuseppe Pelagatti: Optimal File Allocation in a Computer Network: a Solution Method Based on the Knapsack Problem. Computer Networks 6(5): 345-357(1982) BibTeX
Yuan-Chieh Chow, Walter H. Kohler: Models for Dynamic Load Balancing in a Heterogeneous Multiple Processor System. IEEE Trans. Computers 28(5): 354-361(1979) BibTeX
Bruno Ciciani, Daniel M. Dias, Philip S. Yu: Analysis of Replication in Distributed Database Systems. IEEE Trans. Knowl. Data Eng. 2(2): 247-261(1990) BibTeX
Douglas W. Cornell, Philip S. Yu: On Optimal Site Assignment for Relations in the Distributed Database Environment. IEEE Trans. Software Eng. 15(8): 1004-1009(1989) BibTeX
Wesley W. Chu: Optimal File Allocation in a Multiple Computer System. IEEE Trans. Computers 18(10): 885-889(1969) BibTeX
Lawrence W. Dowdy, Derrell V. Foster: Comparative Models of the File Assignment Problem. ACM Comput. Surv. 14(2): 287-313(1982) BibTeX
Xiaolin Du, Fred J. Maryanski: Data Allocation in a Dynamically Reconfigurable Environment. ICDE 1988: 74-81 BibTeX
Derek L. Eager, Edward D. Lazowska, John Zahorjan: Adaptive Load Sharing in Homogeneous Distributed Systems. IEEE Trans. Software Eng. 12(5): 662-675(1986) BibTeX
Kapali P. Eswaran: Placement of Records in a File and File Allocation in a Computer. IFIP Congress 1974: 304-307 BibTeX
Marshall L. Fisher, Dorit S. Hochbaum: Database Location in Computer Networks. J. ACM 27(4): 718-735(1980) BibTeX
Jim Gray (Ed.): The Benchmark Handbook for Database and Transaction Systems (1st Edition). Morgan Kaufmann 1991
Contents BibTeX
Anna Hac: A Distributed Algorithm for Performance Improvement Through File Replication, File Migration, and Process Migration. IEEE Trans. Software Eng. 15(11): 1459-1470(1989) BibTeX
Akhil Kumar, Arie Segev: Cost and Availability Tradeoffs in Replicated Data Concurrency Control. ACM Trans. Database Syst. 18(1): 102-131(1993) BibTeX
James F. Kurose, Rahul Simha: A Microeconomic Approach to Optimal Resource Allocation in Distributed Computer Systems. IEEE Trans. Computers 38(5): 705-717(1989) BibTeX
Will E. Leland, Teunis J. Ott: Load-Balancing Heuristics and Process Behavior. SIGMETRICS 1986: 54-69 BibTeX
Miron Livny, Myron Melman: Load Balancing in Homogeneous Broadcast Distributed Systems. SIGMETRICS 1982: 47-56 BibTeX
Samy A. Mahmoud, J. Spruce Riordon: Optimal Allocation of Resources in Distributed Information Networks. ACM Trans. Database Syst. 1(1): 66-78(1976) BibTeX
Howard L. Morgan, K. Dan Levin: Optimal Program and Data Locations in Computer Networks. Commun. ACM 20(5): 315-322(1977) BibTeX
Lionel M. Ni, Kai Hwang: Optimal Load Balancing in a Multiple Processor System with Many Job Classes. IEEE Trans. Software Eng. 11(5): 491-496(1985) BibTeX
Pedro I. Rivera-Vega, Ravi Varadarajan, Shamkant B. Navathe: Scheduling Data Redistribution in Distributed Databases. ICDE 1990: 166-173 BibTeX
M. Tamer Özsu, Patrick Valduriez: Principles of Distributed Database Systems. Prentice-Hall 1991, ISBN 0-13-715681-2
Benjamin W. Wah: File Placement on Distributed Computer Systems. IEEE Computer 17(1): 23-32(1984) BibTeX
Yung-Terng Wang, Robert J. T. Morris: Load Sharing in Distributed Systems. IEEE Trans. Computers 34(3): 204-217(1985) BibTeX
Songnian Zhou: A Trace-Driven Simulation Study of Dynamic Load Balancing. IEEE Trans. Software Eng. 14(9): 1327-1341(1988) BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
CIKM 1995 Proceedings, ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:01:51 2009