A game-theoretical analysis of Grid job scheduling

Taneja, Sonia (2012) A game-theoretical analysis of Grid job scheduling. Advisor: Buscemi, Dr. Maria Grazia. Coadvisor: Montanari, Prof. Ugo . pp. 113. [IMT PhD Thesis]

Text Taneja_phdthesis.pdf - Published Version Restricted to IMT staff and National library only Download (667kB)

Abstract

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.

Item Type:	IMT PhD Thesis
Subjects:	Q Science > QA Mathematics > QA75 Electronic computers. Computer science
PhD Course:	Computer Science and Engineering
Identification Number:	https://doi.org/10.6092/imtlucca/e-theses/84
NBN Number:	urn:nbn:it:imtlucca-27119
Date Deposited:	19 Jul 2012 10:34
URI:	http://e-theses.imtlucca.it/id/eprint/84

Actions (login required, only for staff repository)

View Item