Game theory based job allocation/load balancing in distributed systems with applications to grid computing

In this dissertation, we present job allocation or load balancing schemes for distributed systems and grid systems based on game theory. The main goal of our work is to provide fairness to the users and the users' jobs i.e., all the users and their jobs should experience approximately equal expected response time (expected queuing delay + processing time + any communication time) or be charged approximately equal price for their execution independent of the computers allocated, and we will show that game theory provides a suitable framework for characterizing such schemes. Most of the previous work on load balancing did not take the fairness of allocation into account or considered fairness in a system without any communication costs.;For distributed systems in which all the jobs belong to a single user (single-class), we use a cooperative game to model the load balancing problem which takes the average system information into account (static load balancing). Our solution is based on the Nash Bargaining Solution which provides a Pareto optimal solution for the distributed system and is also a fair solution. We then extend the system model to include jobs from various users (multi-user/multi-class job distributed system) and include pricing to model a Grid system. For a grid system, we propose three static price-based job allocation schemes whose objective is to minimize the expected price for the grid users. One scheme provides a system optimal solution and is formulated as a constraint minimization problem and the other two schemes provide a fair solution and are formulated as non-cooperative games among the users. We use the concept of Nash equilibrium as the solution of our non-cooperative games and derive distributed algorithms for computing it. We also extend the proposed static load balancing schemes for multi-user jobs and formulate two schemes that take the current state of the system into account (dynamic load balancing). One dynamic scheme tries to minimize the expected response time of the entire system and the other tries to minimize the expected response time of the individual users to provide a fair solution.