File Decomposition and Assignment Problems on Distributed Systems

摘要

File decomposition and assignment problems have been two of the principal research topics in parallel and distributed processing. In this paper, we present these problems and propose a heuristic algorithm for determining effective file decomposition and assignment solutions. At first, a model is developed for decomposing and allocating files on distributed systems. The model considers storage costs, communication costs, the query rate, updating rates of files, the maximum expected access times to files at each computer, the storage capacity of each computer and the workload imbalance cost. The criterion of optimality is minimal overall operating costs. Because these problems are in general NP-hard, we propose a heuristic algorithm based on genetic algorithm to solve them. Several examples for different distributed systems are given to illustrate our model.