An approximation algorithm for a file-allocation problem in a hierarchical distributed system

ABSTRACT

A file allocation problem in a hierarchical distributed computer network is examined. It is shown that the problem is NP-hard. An approximation algorithm is suggested. It is estimated that the approximation algorithm has a high chance of obtaining the optimal solution. Experimental results show that the difference between the optimal solution and the solution generated by the approximation algorithm is no more than 4% away from the optimal solution.

REFERENCES

• 1: Casey, R.G., "Allocation of copies of a file in an information network," AFIPS Conference Proceedings, Vol. 40, 1972 Spring Joint Computer Conference, May 1972, pp. 617--625.
• 2: Shi-Kuo Chang, Data base decomposition in a hierarchical computer system, Proceedings of the 1975 ACM SIGMOD international conference on Management of data, May 14-16, 1975, San Jose, California [doi>10.1145/500080.500086]
• 3: Chu, W.W., "Optimal file allocation in a multi-computer information system," IEEE Transactions on Computers, Vol. C-18, No. 10, October 1969, pp. 885--889.
• 4: Eswaran, K.P., "Placement of records in a file and file allocation in a computer network," IFIP, August 1974, pp. 304--307.
• 5: Foley, J.D. and Brownlee, E.H., "A model of distributed processing in computer networks, with application to satellite graphics," Proc. of International Conference on Computer Communication, August 1974, Stockholm, pp. 330--336.
• 6: Ghosh, S.P., "Distributing a data base with logical associations on computer network for parallel searching," IBM Research Report, 1974.
• 7: Ellis Horowitz , Sartaj Sahni, Fundamentals of Computer Alori, W. H. Freeman & Co., New York, NY, 1978
• 8: Howson, H.R., Amay, L.R. and Thorpe, W.D., "Research and Development of parametric cost models to evaluate strategies in the design of a national data bank network," Research Report, Faculty of Management, McGill University, 1974.
• 9: Katriel Dan Levin, Organizing distributed data bases in computer networks., 1974
• 10: Samy Mahmoud , J. S. Riordon, Optimal allocation of resources in distributed information networks, ACM Transactions on Database Systems (TODS), v.1 n.1, p.66-78, March 1976 [doi>10.1145/320434.320449]
• 11: Howard L. Morgan , K. Dan Levin, Optimal program and data locations in computer networks, Communications of the ACM, v.20 n.5, p.315-322, May 1977 [doi>10.1145/359581.359591]
• 12: Whitney, V.K.M., "A study of optimal file assignment and communication network configuration in remote-access computer mesmage processing and communication systems," University of Michigan, Electrical Engineering Department, September 1970.
• 13: Urano, Y., Ono, K. and Inone, S., "Optimal design of distributed networks," Proc. of International Conference on Computer Communication, August 1974, pp. 413--420.