A near-optimal database allocation for reducing the average waiting time in the grid computing environment

In a grid computing environment, a great many users may access the same database simultaneously. To reduce the average waiting time for all users, a grid designer usually replicates the frequently accessed database among nodes based on the load balance heuristic. On the other hand, users may raise identical queries regarding an issue of interest, e.g., stock information, on a database and each of the queries will be directed to any node having a replica of that database. That is, the same answer will be determined by multiple nodes. Consequently, there exist two shortcomings of poor data sharing and duplicate calculations if the database is not replicated and allocated adequately. In this paper, we aim to minimize average waiting time and try to overcome the two shortcomings by performing database allocation over multiple nodes without any replication. The main idea behind the proposed method is to map the original problem to the Euclidean space RnRn and to solve the mapped problem in RnRn by a gradient-based optimization technique. The theoretical analyses ensure that the proposed method can converge linearly and achieve near-optimal results.