Decentralized job scheduling in the cloud based on a spatially generalized Prisoner's Dilemma game

Jakub Gąsior; Franciszek Seredyński

International Journal of Applied Mathematics and Computer Science (2015)

  • Volume: 25, Issue: 4, page 737-751
  • ISSN: 1641-876X

Abstract

top
We present in this paper a novel distributed solution to a security-aware job scheduling problem in cloud computing infrastructures. We assume that the assignment of the available resources is governed exclusively by the specialized brokers assigned to individual users submitting their jobs to the system. The goal of this scheme is allocating a limited quantity of resources to a specific number of jobs minimizing their execution failure probability and total completion time. Our approach is based on the Pareto dominance relationship and implemented at an individual user level. To select the best scheduling strategies from the resulting Pareto frontiers and construct a global scheduling solution, we developed a decision-making mechanism based on the game-theoretic model of Spatial Prisoner's Dilemma, realized by selfish agents operating in the two-dimensional cellular automata space. Their behavior is conditioned by the objectives of the various entities involved in the scheduling process and driven towards a Nash equilibrium solution by the employed social welfare criteria. The performance of the scheduler applied is verified by a number of numerical experiments. The related results show the effectiveness and scalability of the scheme in the presence of a large number of jobs and resources involved in the scheduling process.

How to cite

top

Jakub Gąsior, and Franciszek Seredyński. "Decentralized job scheduling in the cloud based on a spatially generalized Prisoner's Dilemma game." International Journal of Applied Mathematics and Computer Science 25.4 (2015): 737-751. <http://eudml.org/doc/275890>.

@article{JakubGąsior2015,
abstract = {We present in this paper a novel distributed solution to a security-aware job scheduling problem in cloud computing infrastructures. We assume that the assignment of the available resources is governed exclusively by the specialized brokers assigned to individual users submitting their jobs to the system. The goal of this scheme is allocating a limited quantity of resources to a specific number of jobs minimizing their execution failure probability and total completion time. Our approach is based on the Pareto dominance relationship and implemented at an individual user level. To select the best scheduling strategies from the resulting Pareto frontiers and construct a global scheduling solution, we developed a decision-making mechanism based on the game-theoretic model of Spatial Prisoner's Dilemma, realized by selfish agents operating in the two-dimensional cellular automata space. Their behavior is conditioned by the objectives of the various entities involved in the scheduling process and driven towards a Nash equilibrium solution by the employed social welfare criteria. The performance of the scheduler applied is verified by a number of numerical experiments. The related results show the effectiveness and scalability of the scheme in the presence of a large number of jobs and resources involved in the scheduling process.},
author = {Jakub Gąsior, Franciszek Seredyński},
journal = {International Journal of Applied Mathematics and Computer Science},
keywords = {job scheduling; multiobjective optimization; genetic algorithm; Prisoner's Dilemma; cellular automata},
language = {eng},
number = {4},
pages = {737-751},
title = {Decentralized job scheduling in the cloud based on a spatially generalized Prisoner's Dilemma game},
url = {http://eudml.org/doc/275890},
volume = {25},
year = {2015},
}

TY - JOUR
AU - Jakub Gąsior
AU - Franciszek Seredyński
TI - Decentralized job scheduling in the cloud based on a spatially generalized Prisoner's Dilemma game
JO - International Journal of Applied Mathematics and Computer Science
PY - 2015
VL - 25
IS - 4
SP - 737
EP - 751
AB - We present in this paper a novel distributed solution to a security-aware job scheduling problem in cloud computing infrastructures. We assume that the assignment of the available resources is governed exclusively by the specialized brokers assigned to individual users submitting their jobs to the system. The goal of this scheme is allocating a limited quantity of resources to a specific number of jobs minimizing their execution failure probability and total completion time. Our approach is based on the Pareto dominance relationship and implemented at an individual user level. To select the best scheduling strategies from the resulting Pareto frontiers and construct a global scheduling solution, we developed a decision-making mechanism based on the game-theoretic model of Spatial Prisoner's Dilemma, realized by selfish agents operating in the two-dimensional cellular automata space. Their behavior is conditioned by the objectives of the various entities involved in the scheduling process and driven towards a Nash equilibrium solution by the employed social welfare criteria. The performance of the scheduler applied is verified by a number of numerical experiments. The related results show the effectiveness and scalability of the scheme in the presence of a large number of jobs and resources involved in the scheduling process.
LA - eng
KW - job scheduling; multiobjective optimization; genetic algorithm; Prisoner's Dilemma; cellular automata
UR - http://eudml.org/doc/275890
ER -

References

top
  1. An, B., Miao, C. and Shen, Z. (2007). Market based resource allocation with incomplete information, in M. Veloso (Ed.), Proceedings of the 20th International Joint Conference on Artificial Intelligence, IJCAI'07, Morgan Kaufmann Publishers Inc., San Francisco, CA, pp. 1193-1198. 
  2. Brandic, I., Pllana, S. and Benkner, S. (2006). An approach for the high-level specification of QoS-aware grid workflows considering location affinity, Workshop on Workflows in Support of Large-Scale Science, WORKS'06, Paris, France, Vol. 14, pp. 231-250. 
  3. Christodoulou, G., Koutsoupias, E. and Vidali, A. (2007). A lower bound for scheduling mechanisms, in H. Gabow (Ed.), Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'07, Society for Industrial and Applied Mathematics, Philadelphia, PA, pp. 1163-1170. Zbl1302.90077
  4. Deb, K., Agrawal, S., Pratap, A. and Meyarivan, T. (2000). A fast elitist non-dominated sorting genetic algorithm for multi-objective optimisation: NSGA-II, in M. Schoenauer et al. (Eds.), Proceedings of the 6th International Conference on Parallel Problem Solving from Nature, PPSN VI, Springer-Verlag, London, pp. 849-858. 
  5. Even-Dar, E., Kesselman, A. and Mansour, Y. (2007). Convergence time to Nash equilibrium in load balancing, ACM Transactions on Algorithms 3(3): 111-132. Zbl1192.68956
  6. Hwang, S. and Kesselman, C. (2003). A flexible framework for fault tolerance in the grid, Journal of Grid Computing 1(3): 251-272. Zbl1076.68509
  7. Katsumata, Y. and Ishida, Y. (2008). On a membrane formation in a spatio-temporally generalized prisoner's dilemma, in H. Umeo et al. (Eds.), Proceedings of the 8th International Conference on Cellular Automata for Research and Industry, ACRI'08, Springer-Verlag, Berlin/Heidelberg, pp. 60-66. Zbl1159.68494
  8. Khan, S.U. and Ahmad, I. (2006). Non-cooperative, semi-cooperative, and cooperative games-based grid resource allocation, 20th International Parallel and Distributed Processing Symposium, IPDPS 2006, Rhodes, Greece. 
  9. Kolodziej, J. and Xhafa, F. (2011). Meeting security and user behavior requirements in grid scheduling, Simulation Modelling Practice and Theory 19(1): 213-226. 
  10. Lee, Y. and Zomaya, A. (2012). Energy efficient utilization of resources in cloud computing systems, The Journal of Supercomputing 60(2): 268-280. 
  11. Li, Z.-J., Cheng, C.-T. and Huang, F.-X. (2009). Utility-driven solution for optimal resource allocation in computational grid, Computer Languages, Systems & Structures 35(4): 406-421. 
  12. Lin, C., Varadharajan, V., Wang, Y. and Pruthi, V. (2004). Enhancing grid security with trust management, in L.-J. Zhang, J. Zhang and H. Cai (Eds.), Proceedings of the 2004 IEEE International Conference on Services Computing, SCC'04, IEEE Computer Society, Washington, DC, pp. 303-310. 
  13. Londoño, J., Bestavros, A. and Teng, S.-H. (2009). Collocation games and their application to distributed resource management, Proceedings of the 2009 Conference on Hot Topics in Cloud Computing, HotCloud'09, San Diego, CA, USA. 
  14. Nowak, M.A. and May, R.M. (1992). Evolutionary games and spatial chaos, Nature 359: 826. 
  15. Palmieri, F., Buonanno, L., Venticinque, S., Aversa, R. and Di Martino, B. (2013). A distributed scheduling framework based on selfish autonomous agents for federated cloud environments, Future Generation Computer Systems 29(6): 1461-1472. 
  16. Perc, M. and Szolnoki, A. (2008). Social diversity and promotion of cooperation in the spatial prisoner's dilemma game, Physical Review E 77: 011904. Zbl1189.91034
  17. Song, S., Hwang, K. and Kwok, Y.-K. (2006). Risk-resilient heuristics and genetic algorithms for security-assured grid job scheduling, IEEE Transactions on Computers 55(6): 703-719. 
  18. Sookhak, M., Akhunzada, A., Talebian, H., Gani, A., Khan, S., Buyya, R. and Zomaya, A.Y. (2015). Remote data auditing in cloud computing environments: A survey, taxonomy, and open issues, ACM Computing Surveys 47(4), Article no. 65. 
  19. Switalski, P. and Seredynski, F. (2011). An efficient evolutionary scheduling algorithm for parallel job model in grid environment, in V. Malyshkin (Ed.), Proceedings of the 11th International Conference on Parallel Computing Technologies, PaCT'11, Springer-Verlag, Berlin/Heidelberg, pp. 347-357. Zbl1328.90061
  20. Szabó, G., Vukov, J. and Szolnoki, A. (2005). Phase diagrams for Prisoner's Dilemma game on two-dimensional lattices, Physical Review E 72(4). Zbl1188.91045
  21. Tchernykh, A., Schwiegelshohn, U., Yahyapour, R. and Kuzjurin, N. (2010). On-line hierarchical job scheduling on grids with admissible allocation, Journal of Scheduling 13(5): 545-552. Zbl1208.68102
  22. Tziritas, N., Xu, C.-Z., Loukopoulos, T., Khan, S. and Yu, Z. (2013). Application-aware workload consolidation to minimize both energy consumption and network load in cloud environments, 42nd International Conference on Parallel Processing (ICPP), Lyon, France, pp. 449-457. 
  23. Wu, C.-C. and Sun, R.-Y. (2010). An integrated security-aware job scheduling strategy for large-scale computational grids, Future Generation Computer Systems 26(2): 198-206. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.