JUCS - Journal of Universal Computer Science 18(20): 2771-2797, doi: 10.3217/jucs-018-20-2771

Distributed Load Balancing Algorithms for Heterogeneous Players in Asynchronous Networks

‡ University of Campinas, Campinas, Brazil

Corresponding author: Luiz Bittencourt ( bit@ic.unicamp.br ) © Luiz Bittencourt, Flávio Miyazawa, André Vignatti. This article is freely available under the J.UCS Open Content License. Citation:
Bittencourt LF, Miyazawa FK, Vignatti AL (2012) Distributed Load Balancing Algorithms for Heterogeneous Players in Asynchronous Networks. JUCS - Journal of Universal Computer Science 18(20): 2771-2797. https://doi.org/10.3217/jucs-018-20-2771 |

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

load balancing, Nash equilibrium, game theory