<abstract xml:lang="en" xmlns="http://www.w3.org/1999/xhtml"><p>Tasks scheduling and resource allocation are among crucial issues in any large scale distributed system, including Computational Grids (CGs). These issues are commonly investigated using traditional computational models and resolution methods that yield near-optimal scheduling strategies. One drawback of such approaches is that they cannot effectively tackle the complex nature of CGs. On the one hand, such systems account for many administrative domains with their own access policies, user privileges, etc. On the other, CGs have hierarchical nature and therefore any computational model should be able to effectively express the hierarchical architecture in the optimization model. Recently, researchers have been investigating the use of game theory for modeling user requirements regarding task and resource allocation in grid scheduling problems. In this paper we present two general non-cooperative game approaches, namely, the <italic>symmetric non-zero sum</italic> game and the <italic>asymmetric Stackelberg</italic> game for modeling grid user behavior defined as user requirements. In our game-theoretic approaches we are able to cast new requirements arising in allocation problems, such as asymmetric users relations, security and reliability restrictions in CGs. For solving the games, we designed and implemented GA-based hybrid schedulers for approximating the equilibrium points for both games. The proposed hybrid resolution methods are experimentally evaluated through the grid simulator under heterogeneity, and large-scale and dynamics conditions. The relative performance of the schedulers is measured in terms of the makespan and flowtime metrics. The experimental analysis showed high efficiency of meta-heuristics in solving the game-based models, especially in the case of an additional cost of secure task scheduling to be paid by the users.</p></abstract>

Tasks scheduling and resource allocation are among crucial issues in any large scale distributed system, including Computational Grids (CGs). These issues are commonly investigated using traditional computational models and resolution methods that yield near-optimal scheduling strategies. One drawback of such approaches is that they cannot effectively tackle the complex nature of CGs. On the one hand, such systems account for many administrative domains with their own access policies, user privileges, etc. On the other, CGs have hierarchical nature and therefore any computational model should be able to effectively express the hierarchical architecture in the optimization model. Recently, researchers have been investigating the use of game theory for modeling user requirements regarding task and resource allocation in grid scheduling problems. In this paper we present two general non-cooperative game approaches, namely, the symmetric non-zero sum game and the asymmetric Stackelberg game for modeling grid user behavior defined as user requirements. In our game-theoretic approaches we are able to cast new requirements arising in allocation problems, such as asymmetric users relations, security and reliability restrictions in CGs. For solving the games, we designed and implemented GA-based hybrid schedulers for approximating the equilibrium points for both games. The proposed hybrid resolution methods are experimentally evaluated through the grid simulator under heterogeneity, and large-scale and dynamics conditions. The relative performance of the schedulers is measured in terms of the makespan and flowtime metrics. The experimental analysis showed high efficiency of meta-heuristics in solving the game-based models, especially in the case of an additional cost of secure task scheduling to be paid by the users.

Modern approaches to modeling user requirements on resource and task allocation in hierarchical computational grids

Department of Mathematics and Computer Science, University of Bielsko-Biała, ul. Willowa 2, 43-309 Bielsko-Biała, Poland

Department of Languages and Informatics Systems Polytechnic, University of Catalonia, Campus Nord, Ed. Omega, C/Jordi Girona 1-3, 08034 Barcelona, Spain

International Journal of Applied Mathematics and Computer Science

Tasks scheduling and resource allocation are among crucial issues in any large scale distributed system, including Computational Grids (CGs). These issues are...

Modern approaches to modeling user requirements on resource and task allocation in hierarchical computational grids

Published Online: Jun 22, 2011

Page range: 243 - 257

DOI: https://doi.org/10.2478/v10006-011-0018-x

Keywords
computational grids, scheduling, non-cooperative games, user behavior, security, meta-heuristics

This content is open access.

Modern approaches to modeling user requirements on resource and task allocation in hierarchical computational grids

Published Online: Jun 22, 2011

Page range: 243 - 257

DOI: https://doi.org/10.2478/v10006-011-0018-x

Keywordscomputational grids, scheduling, non-cooperative games, user behavior, security, meta-heuristics

This content is open access.

Keywords
computational grids, scheduling, non-cooperative games, user behavior, security, meta-heuristics