Bicriteria Load Balancing for Online Placement in Heterogeneous Servers with Pareto Upper Bounds

We study the online load balancing problem for two independent criteria in heterogeneous systems. For convenience, we choose a system of distributed file servers located in a cluster as the scenario, although our work is not limited to it. Every server is assigned upper bounds for its load and storage space. We assume that the heterogeneity of servers is eventually reflected by the difference of these assignments among different servers. In this paper, the upper bounds are designed in the way that they are totally different, and form a pareto set (such that no server is more capable than the others). We propose a solution for balancing their loads and required storage spaces for online document placements, and document reallocation is allowed. The time complexity is O(log M), where M is the number of servers, plus the reallocation cost incurred. This cost is a measure of the price for coping with the heterogeneity of our model.