ACM SIGMOD Anthology TODS dblp.uni-trier.de

Optimal Allocation of Resources in Distributed Information Networks.

Samy A. Mahmoud, J. Spruce Riordon: Optimal Allocation of Resources in Distributed Information Networks. ACM Trans. Database Syst. 1(1): 66-78(1976)
@article{DBLP:journals/tods/MahmoudR76,
  author    = {Samy A. Mahmoud and
               J. Spruce Riordon},
  title     = {Optimal Allocation of Resources in Distributed Information Networks},
  journal   = {ACM Trans. Database Syst.},
  volume    = {1},
  number    = {1},
  year      = {1976},
  pages     = {66-78},
  ee        = {http://doi.acm.org/10.1145/320434.320449, db/journals/tods/MahmoudR76.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

The problems of file allocation and capacity assignment in a fixed topology distributed computer network are examined. These two aspects of the design are tightly coupled by means of an average message delay constraint. The objective is to allocate copies of information files to network nodes and capacities to network links so that a minimum cost is achieved subject to network delay and file availability constraints. A model for solving the problem is formulated and the resulting optimization problem is shown to fall into a class of nonlinear integer programming problems. Deterministic techniques for solving this class of problems are computationally cumbersome, even for small size problems. A new heuristic algorithm is developed, which is based on a decomposition technique that greatly reduces the computational complexity of the problem. Numerical results for a variety of network configurations indicate that the heuristic algorithm, while not theoretically convergent, yields practicable low cost solutions with substantial savings in computer processing time and storage requirements. Moreover, it is shown that this algorithm is capable of solving realistic network problems whose solutions using deterministic techniques are computationally intractable.

Copyright © 1976 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 1, TODS 1976-1990" and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

Conference Presentation

Samy A. Mahmoud, J. Spruce Riordon: Optimal Allocation of Resources in Distributed Information Networks. VLDB 1975: (in the table of contents only) BibTeX

References

[1]
...
[2]
...
[3]
...
[4]
...
[5]
Wesley W. Chu: Optimal File Allocation in a Multiple Computer System. IEEE Trans. Computers 18(10): 885-889(1969) BibTeX
[6]
...
[7]
Kapali P. Eswaran: Placement of Records in a File and File Allocation in a Computer. IFIP Congress 1974: 304-307 BibTeX
[8]
...
[9]
...
[10]
...
[11]
...
[12]
...
[13]
...
[14]
...
[15]
...
[16]
...

Referenced by

  1. 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
  2. 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)
  3. Nabil Kamel, Roger King: Intelligent Database Caching Through the Use of Page-Answers and Page-Traces. ACM Trans. Database Syst. 17(4): 601-646(1992)
  4. Ouri Wolfson, Amir Milo: The Multicast Policy and Its Relationship to Replicated Data Placement. ACM Trans. Database Syst. 16(1): 181-205(1991)
  5. Sudha Ram, Roy E. Marsten: A Model for Database Allocation Incorporating a Concurrency Control Mechanism. IEEE Trans. Knowl. Data Eng. 3(3): 389-395(1991)
  6. Uwe M. Borghoff: Voting and Relocation Strategies Preserving Consistency among Replicated Files. ICDT 1990: 318-332
  7. Peter M. G. Apers: Data Allocation in Distributed Database Systems. ACM Trans. Database Syst. 13(3): 263-304(1988)
  8. George P. Copeland, William Alexander, Ellen E. Boughter, Tom W. Keller: Data Placement In Bubba. SIGMOD Conference 1988: 99-108
  9. Amir Milo, Ouri Wolfson: Placement of Replicated Items in Distributed Databases. EDBT 1988: 414-427
  10. Clement T. Yu, C. H. Chen: Adaptive Information System Design: One Query at a Time. SIGMOD Conference 1985: 280-290
  11. Shamkant B. Navathe, Stefano Ceri, Gio Wiederhold, Jinglie Dou: Vertical Partitioning Algorithms for Database Design. ACM Trans. Database Syst. 9(4): 680-710(1984)
  12. Clement T. Yu, M. K. Siu, K. Lam, C. H. Chen: File Allocation in Distributed Databases with Interaction between Files. VLDB 1983: 248-259
  13. Kowtha Murthy, John B. Kam, M. S. Krishnamoorthy: An Approximation Algorithm to the File Allocation Problem in Computer Networks. PODS 1983: 258-266
  14. Elisa Bertino: Distributed Database Design Using the Entity-Relationship Model. ER 1983: 189-203
  15. Stefano Ceri, Mauro Negri, Giuseppe Pelagatti: Horizontal Data Partitioning in Database Design. SIGMOD Conference 1982: 128-136
  16. K. Lam, Clement T. Yu: An Approximation Algorithm for a File-Allocation Problem in a Hierarchical Distributed System. SIGMOD Conference 1980: 125-132
  17. K. C. Toth, Samy A. Mahmoud, J. Spruce Riordon, O. Sherif: The ADD System: An Architecture for Distributed Databases. VLDB 1978: 462-471
  18. James B. Rothnie Jr., Nathan Goodman: A Survey of Research and Development in Distributed Database Management. VLDB 1977: 48-62
  19. K. Mani Chandy: Models of Distributed Systems. VLDB 1977: 105-120
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:38:35 2008