A game-theoretical analysis of Grid job scheduling
Creators: name: Taneja, Sonia
Publisher: name: IMT Alti Studi Lucca
Year: 2012
Subjects: QA75 Electronic computers. Computer science

description: Computational Grid is a well-established platform that  gives an assurance to provide a vast range of heterogeneous  resources for high performance computing. To grasp the full advantage of Grid systems, efficient and effective resource management and Grid job scheduling are key requirements. Particularly in resourcemanagement and job scheduling, conflictsmay arise as Grid resources are usually owned by different organizations/sites,which have different and often contradictory goals. For instance some site prefers first to execute its own local jobs over the Grid jobs, in order to minimize the completion time of the former jobs. Nevertheless, for a Grid to properly work, sites should be incentivated to collaborate for the faster execution of Grid jobs. Each site who accepts to execute the job, gets an incentive amounting to the length of the job. A crucial objective is to analyze potential scenarios where selfish or  cooperative behaviors of organizations impact heavily  on global Grid efficiency. In this thesis, we study the  job scheduling problem in computational Grid and analyze  it using game theoretic approaches. We consider a hierarchical job scheduling model that is formulated as a sequential non-cooperative job scheduling game among Grid sites, which may have selfish concerns. We exploit the concept of Nash equilibrium, a situation in which no player can gain any profit by unilaterally changing its strategy.  In the general case in which there are local jobs besides Grid jobs we conjecture that the selfish strategy profile,  in which every site chooses to execute a local job if there is any in its queue and otherwise bids for executing a Grid job offering its earliest estimated response time, in the presence of heavy load is a Nash equilibrium. Earliest estimated response time is an estimation of the time interval between the job submission and the beginning of the job execution. Next, we restrict to a special sub-case in which there are no local jobs. We give a formal proof that the strategy profile where every site bids its earliest estimated response time upon arrival of a new Grid job is a Nash equilibrium. In both cases we make two main assumptions over our model. First, we require that every incoming job (either Grid or local) needs the same amount of time to be executed. Second, we assume that the Grid is heavily loaded, namely there must be enough incoming jobs so  that every site that is free and willing to execute a job  cannot be inactive. We also investigate the above two strategies after relaxing the heavy load condition. For  the general case, in absence of heavy load condition, interestingly we have spotted a counter-example. It is  counterintuitive to the fact that the selfish strategy profile where a player prefers to execute a local job over  the Grid job is a Nash. It is expected that executing a  local job at a given site s will have a consequence that  the other sites will have to accept the execution of Grid  job. Which in turn will decrease the probability of the  other sites of accepting future Grid jobs, with consequent  advantage for site s. But interestingly, we found a counter-example for this fact. We correlated and complemented our theoretical results by performing an experimental analysis based on two kinds of approaches, simulation and exhaustive search.