Minimizing the probability of load imbalance in heterogeneous distributed computer systems

We study the probability of load imbalance in heterogeneous distributed computer systems where nodes have different computing power. When load imbalance occurs in a distributed computer system equipped with a dynamic load balancing mechanism, jobs from some overloaded nodes are transferred to some underloaded nodes. Minimizing the probability of load imbalance is actually reducing the amount of system overhead, because job migration increases communication traffic, and excessive migration will degrade overall system performance. Since nodes have different processing speeds, we must assign more jobs to nodes with higher processing speed. Therefore, there is a problem of finding an optimal load distribution that minimizes the probability of performing dynamic load balancing. We develop a method to distribute load among heterogeneous nodes with different computing power in such a way that the probability of load imbalance in the entire system is minimized. We also show that a system with identical node utilization exhibits near-optimal performance in terms of probability of load imbalance.