AGAMETHEORETICFRAMEWORKFORLOADBALANCING IN DISTRIBUTEDSYSTEMS

Abstract

Distributed computing is a widely adopted technology that has been around for more than four decades. It has become a foundation model for various computing paradigms, such as cluster computing, grid computing, and cloud computing. A key concept behind distributed computing is the notion of a distributed system where a group of users shares heterogeneous computational resources located at different geographical locations. A vital issue in a dis tributed system is to effectively manage the utilization of resources to improve the distributed system’s performance. The problem of managing the efficient utilization of resources is re ferred to as a load balancing problem. Load balancing is a process of allocating workloads across multiple computing re sources to improve the resources’ utility while ensuring the service’s quality to the end-users. The purpose of load balancing is to: i) minimize the response time of users, ii) minimize the cost to users, iii) fair utilization of resources (i.e., no resource is over-utilized or underuti lized), iv) reducing energy consumption. The load balancing problem is very challenging since, in a distributed system, there is no centralized controlling authority, and the users are autonomous and self-interested. Autonomous means a user is free to decide without any controlling authority, and self-interested means a user is concerned about optimizing his own goal(s). In such systems, it is impossible to optimize each user’s goal by using a centralized approach. The reason behind is that the users do not have any prior motivation to cooperate and maybedissatisfied with the outcome; thus, one or more user may improve their outcome while worsening the outcome for others. Game theory plays a vital role in modeling such a situation as a multi-player game, to analyze it and to provide efficient (rational) strategies for each player. The combination of each player’s efficient strategies is called Nash equilibrium (NE) of the game– a stable v Abstract solution point. However, the concept of NE provided by game theory is descriptive, not prescriptive: it does not suggest any such algorithm to compute NE. This necessitates the design of an algorithm for computing NE of the game in a distributed fashion. In this thesis, the load balancing problem in distributed systems is considered. The main goal of this thesis is to provide the following objectives: i) minimize the response time of users, ii) minimize the cost to users, iii) fair utilization of resources (i.e., no resource is over-utilized or underutilized), iv) reducing energy consumption. In this thesis, four load balancing problems with different objectives are considered. All the problems are formulated as a game-theoretic model. The NE characterization of each game is presented, and four different distributed algorithms based on the concept of game theory are proposed. The proposed approaches’ performance is compared with that of other existing approaches, and their advantages are demonstrated.