Some theorems to aid in solving the file allocation problem

ABSTRACT

The file allocation problem — i.e. the problem of finding the optimal set of network sites at which to locate copies of a file — is known to be, in general, polynomial complete. Heuristics and other aids to finding optimal, or near-optimal, solutions are therefore much needed. In this paper we present three theorems which can be applied a priori to indicate that certain sites should (or should not) be included in an optimal allocation.

REFERENCES

• 1: Casey, R.G. Allocation of copies of a file in an information network. Proc. AFIPS 1972 SJCC, Vol. 40, AFIPS Press, Montvale, N.J., pp. 617-625.
• 2: K. M. Chandy , J. E. Hewes, File allocation in distributed systems, Proceedings of the 1976 ACM SIGMETRICS conference on Computer performance modeling measurement and evaluation, p.10-13, March 29-31, 1976, Cambridge, Massachusetts, United States [doi>10.1145/800200.806177]
• 3: Chu, W.W. Optimal file allocation in a multi-computer information system. 1EEE Trans. Comptrs. C-18 (1969), pp. 885- 889.
• 4: Chu, W.W. Optimal file allocation in a computer network. In Computer-Communications Networks, N. Abramson and F. Kuo, Eds., Prentice-Hall, Englewood Cliffs, N.J., 1973.
• 5: Eswaran, K.P. Placement of records in a file and file allocation in a computer network. Information Processing 74, North-Holland Pub. Co., Amsterdam, 1974, pp. 304-307.
• 6: Katriel Dan Levin, Organizing distributed data bases in computer networks., 1974
• 7: Spinetto, R.D. A facility location problem. SlAM Review 18 (1976), 294-295.
• 8: Urano, Y., Ono, K., and Inoue, S. Optimal design of distributed networks. Second Int. Conf. on Comptr. Comm., 1974, pp. 413-420.

INDEX TERMS

Keywords:
computer networks, distributed data management, file allocation