Load balancing in distributed systems: A game theoretic approach

In this dissertation we introduce and investigate a new generation of load balancing schemes based on game theoretic models. First, we design a load balancing scheme based on a cooperative game among computers. The solution of this game is the Nash Bargaining Solution (NBS) which provides a Pareto optimal and fair allocation of jobs to computers. The main advantages of this scheme are the simplicity of the underlying algorithm and the fair treatment of all jobs independent of the allocated computers. Then we design a load balancing scheme based on a noncooperative game among users. The Nash equilibrium provides a user-optimal operation point for the distributed system and represents the solution of the proposed noncooperative load balancing game. We present a characterization of the Nash equilibrium and a distributed algorithm for computing it. The main advantages of our noncooperative scheme are its distributed structure and user-optimality. We compare the performance of the proposed load balancing schemes with that of other existing schemes and show their main advantages.; This dissertation is also concerned with the design of load balancing schemes for distributed systems in which the computational resources are owned and operated by different self interested agents. In such systems there is no a-priori motivation for cooperation and the agents may manipulate the resource allocation algorithm in their own interest leading to severe performance degradation and poor efficiency. Using concepts from mechanism design theory (a sub-field of game theory) we design two load balancing protocols that force the participating agents to report their true parameters and follow the rules. We prove that our load balancing protocols are truthful and satisfy the voluntary participation condition. Finally we investigate the effectiveness of our protocols by simulation.