Online Bicriteria Load Balancing for Distributed File Servers

We study the online bicriteria load balancing problem in a system of M distributed homogeneous file servers located in a cluster. The load and storage space are assumed to be independent. We propose two online approximate algorithms for balancing the load and required storage space of each server during document placement. Our first algorithm combines the first result in [10] and the upper bound result in [1]. With applying document reallocation, we further obtain improvement and give a smoother tradeoff curve of the upper bounds of load and storage space. This result improves the best existing solutions. The second algorithm is for theoretical purpose. Its existence proves that the bounds for the load and the required storage space of each server, respectively, are strictly better when document reallocation is allowed. It enhances the research in applying document reallocation. The time complexities of both algorithms are O(logM); and the cost of document reallocation should be taken into account.