Distributed Load Balancing Algorithms for Heterogeneous Players in Asynchronous Networks

Luiz F. Bittencourt (University of Campinas, Brazil)

Flávio K. Miyazawa (University of Campinas, Brazil)

André L. Vignatti (University of Campinas, Brazil)

Abstract: In highly scalable networks, such as grid and cloud computing environments and the Internet itself, the implementation of centralized policies is not feasible. Thus, nodes in such networks act according to their interests. One problem with these networks is load balancing. This paper considers load balancing in networks with heterogeneous nodes, that is, nodes with different processing power, and asynchronous actions, where there is no centralized clock and thus one or more nodes can perform their actions simultaneously. We show that if the nodes want to balance the load without complying with certain rules, then load balancing is never achieved. Thus, it is necessary to implement some rules that need to be distributed (i.e., so that they run locally on each node) due to the unfeasibility of centralized implementation. Due to the game-theoretic nature of the nodes, the concept of solution is when all nodes are satisfied with the load assigned to them, a Nash equilibrium state. Moreover, we discuss how the rules can be created and present three sets of rules for the nodes to reach a Nash equilibrium. For each set of rules, we prove its correctness and, through simulations, evaluate the number of steps needed to reach the network's Nash equilibrium.

Keywords: Nash equilibrium, game theory, load balancing

Categories: F.2.0, I.2.11