File allocation in distributed systems
- Creators
- Chandy, K. M.
- Hewes, J. E.
Abstract
The problem of allocating files in a computer network is a complex combinatorial problem due to the number of integer design parameters involved. These parameters include system cost, number of copies of each file to be stored, and sites at which the copies should be stored. The tradeoffs between these parameters are discussed. The design problem is formulated as an integer programming problem. A branch and bound algorithm is proposed to solve the problem. A linear programming formulation which ignores integer restrictions (and allows a fraction of a file to reside at a site) is shown to yield integer solutions in most cases. In other words integer restrictions are satisfied automatically. A near-optimal heuristic is presented, along with computational results. An efficient method to solve the file allocation problem for medium-scale networks is proposed.
Additional Information
© 1976 Association for Computing Machinery (ACM). This work was performed by the authors while they were working for Information Research Associates, Austin, Texas. Information Research Associates carried out this work under contract to NASA Langley Research Center. The authors gratefully acknowledge the help of Dr. James C. Browne of the University of Texas and James Harris of NASA Langley Research Center.Additional details
- Eprint ID
- 92197
- DOI
- 10.1145/800200.806177
- Resolver ID
- CaltechAUTHORS:20190110-112538692
- NASA
- Created
-
2019-01-10Created from EPrint's datestamp field
- Updated
-
2021-11-16Created from EPrint's last_modified field