Search
  • All Journals
Advanced Search
Search articles by Title, Author, Keywords, DOI
3.9CiteScore
1.3Impact Factor
Advanced Search
MAP  >  The Knowledge Engineering Review
2019 Volume 34
Article Contents
Next Previous
ORIGINAL RESEARCH   Open Access    

Time-sensitive resource re-allocation strategy for interdependent continuous tasks

  • Bristol BS8 2BN

  • London WC2R 2LS

More Information
  • Abstract: An increase in volumes of data and a shift towards live data enabled a stronger focus on resource-intensive tasks which run continuously over long periods. A Grid has potential to offer the required resources for these tasks, while considering a fair and balanced allocation of resources among multiple client agents. Taking this into account, a Grid might be unwilling to allocate its resources for long time, leading to task interruptions. This problem becomes even more serious if an interruption of one task may lead to the interruption of dependent tasks. Here, we discuss a new strategy for resource re-allocation which is utilized by a client with the aim to prevent too long interruptions by re-allocating resources between its own tasks. Those re-allocations are suggested by a client agent, but only a Grid can re-allocate resources if agreed. Our strategy was tested under the different Grid settings, accounting for the adjusted coefficients, and demonstrated noticeable improvements in client utilities as compared to when it is not considered. Our experiment was also extended to tests with environmental modelling and realistic Grid resource simulation, grounded in real-life Grid studies. These tests have also shown a useful application of our strategy.
  • 加载中
  • Andrzejak , A. & Ceyran , M. 2005. Characterizing and predicting resource demand by periodicity mining. Network and Systems Management 13(2), 175–196.

    Google Scholar

    Apache. 2014. Storm - distributed and fault-tolerant realtime computation. http://storm.incubator.apache.org/

    Google Scholar

    Babu , S. & Widom , J. 2001. Continuous queries over data streams. SIGMOD Record 30(3), 109–120.

    Google Scholar

    Barbieri , D. F., Braga , D., Ceri , S., Della Valle, E. & Grossniklaus , M. 2009. C-SPARQL: SPARQL for continuous querying. In The 18th International Conference on World Wide Web. ACM, 1061–1062.

    Google Scholar

    Decker , K. S. & Lesser , V. R. 1992. Generalizing the partial global planning algorithm. International Journal of Intelligent and Cooperative Information Systems 1, 319–346.

    Google Scholar

    EsperTech. 2014. Event Series Intelligence: Esper & NEsper. http://esper.codehaus.org/

    Google Scholar

    Foster , I., Kesselman , C. & Tuecke , S. 2001. The anatomy of the grid: Enabling scalable virtual organizations. International Journal of High Performance Computing Applications, 15, 200–222. http://portal.acm.org/citation.cfm?id=1080644.1080667

    Google Scholar

    Ghanem , M., Guo , Y., Hassard , J., Osmond , M. & Richards , M. 2004. Sensor Grids for Air Pollution Monitoring. In The 3rd UK e-Science All Hands Meeting.

    Google Scholar

    Haberland , V. 2015. Strategies for the Execution of Long-Term Continuous and Simultaneous Tasks in Grids.PhD thesis NMS. King’s College London.

    Google Scholar

    Haberland , V., Miles , S. and Luck , M. 2014. Negotiation to Execute Continuous Long-Term Tasks. In The 21st European Conference on Artificial Intelligence, T. Schaub et al. (eds.) Vol. 263. Frontiers in Artificial Intelligence and Applications, 1019–1020.

    Google Scholar

    Haberland , V., Miles , S. & Luck , M. 2015. Adjustable fuzzy inference for adaptive grid resource negotiation. In Next Frontier in Agent-based Complex Automated Negotiation. Vol. 596. Studies of Computational Intelligence. Springer, 37–57.

    Google Scholar

    Haberland , V., Miles , S. & Luck , M. 2017a. Negotiation strategy for continuous long-term tasks in a grid environment. Autonomous Agents and Multi-Agent Systems 31(1), 130–150.

    Google Scholar

    Haberland , V., Miles , S. & Luck , M. 2017b. Resource Re-allocation for Data Inter-dependent Continuous Tasks in Grids. In Vol. 10207. LNCS. Springer International Publishing, 187–201.

    Google Scholar

    Iosup , A., Li , H., Jan , M., Anoep , S., Dumitrescu , C., Wolters , L. & Epema , D. H. J. 2008. The grid workloads archive. Future Generation Computer System 24(7), 672–686.

    Google Scholar

    Jin , H., He , Y., Wen , W. & Liu , H. 2005. A run-time scheduling policy for dependent tasks in grid computing systems. In The 6th International Conference on Parallel and Distributed Computing, Applications and Technologies, 521–523.

    Google Scholar

    Kondo , D., Taufer , M., Brooks , C., Casanova , H. & Chien , A. 2004. Characterizing and evaluating desktop grids: An empirical study. In The 18th International Parallel and Distributed Processing Symposium.

    Google Scholar

    Lacroix , B., Paulus , C. & Mercier , D. 2012. Multi-agent control of thermal systems in buildings. In Proceedings of the 3rd International workshop on Agent Technologies in Energy Systems.

    Google Scholar

    Le-Phuoc , D., Nguyen-Mau , H. Q., Parreira , J. X. & Hauswirth , M. 2012. A middleware framework for scalable management of linked streams. Web Semantics: Science, Services and Agents on the World Wide Web 16(0), 42–51.

    Google Scholar

    Lee , L.-T., Chen , C.-W., Chang , H.-Y., Tang , C.-C. & Pan , K.-C. 2009. A non-critical path earliest-finish algorithm for inter-dependent tasks in heterogeneous computing environments. In The 11th IEEE International High Performance Computing and Communications, 603–608.

    Google Scholar

    Lesser , V., Decker , K., Wagner , T., Carver , N., Garvey , A., Horling , B., Neiman , D., Podorozhny , R., Nagendra Prasad , M., Raja , A., Vincent , R., Xuan , P. and Zhang , X. Q. 2004. Evolution of the GPGP/TAEMS Domain-Independent Coordination Framework. Autonomous Agents and Multi-Agent Systems 9(1–2), 87–143.

    Google Scholar

    Lesser , V. R. 1991. A retrospective view of FA/C distributed problem solving. IEEE Transactions on Systems, Man and Cybernetics 21(6), 1347–1362.

    Google Scholar

    Lim , H. and Babu , S. 2013. Execution and Optimization of Continuous Queries with Cyclops. In Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data. ACM, 1069–1072.

    Google Scholar

    Llanes , K. R., Casanova , M. A. & Lemus , N. M. 2016. From Sensor Data Streams to Linked Streaming Data: a survey of main approaches. Journal of Information and Data Management 7(2), 130–140.

    Google Scholar

    Meriem , M. and Belabbas , Y. 2010. Dynamic dependent tasks assignment for grid computing. In Algorithms and Architectures for Parallel Processing, C.-H. Hsu et al. (eds.) Vol. 6082. LNCS. Springer. 112–120.

    Google Scholar

    Motwani , R., Widom , J., Arasu , A., Babcock , B., Babu , S., Datar , M., Manku , G., Olston , C., Rosenstein , J. & Varma , R. 2003. Query Processing, Resource Management, and Approximation in a Data Stream Management System. In The 1st Biennial Conference on Innovative Data Systems Research, 245–256.

    Google Scholar

    Sandnes , F. E. and Sinnen , O. 2005. Stochastic DFS for Multiprocessor Scheduling of Cyclic Taskgraphs. In Parallel and Distributed Computing: Applications and Technologies, K.-M. Liew et al. (eds.) Vol. 3320. LNCS. Springer, 354–362.

    Google Scholar

    Sardinha , A., Alves , T. A. O., Marzulo , L. A. J., Franca , F. M. G., Barbosa , V. C. & Costa , V. S. 2012. Scheduling cyclic task graphs with SCC-Map. In The 3rd Workshop on Applications for Multi-Core Architectures, 54–59.

    Google Scholar

    Sequeda , J. F. and Corcho , O. 2009. Linked stream data: A position paper. In The 2nd International Workshop on Semantic Sensor Networks. Vol. 522, 148–157.

    Google Scholar

    Terry , D., Goldberg , D., Nichols , D. & Oki , B. 1992. Continuous queries over append-only databases. SIGMOD Rec. 21(2), 321–330.

    Google Scholar

    TIBCO. 2014. http://www.streambase.com/

    Google Scholar

    Wooldridge , M. and Jennings , N. R. 1995. Intelligent agents: Theory and practice. The Knowledge Engineering Review 10, 115–152.

    Google Scholar

    Yan , K. Q., S. C. Wang , C. P. Chang & J. S. Lin . 2007. A hybrid load balancing policy underlying grid computing environment. Computer Standards & Interfaces 29(2), 161–173.

    Google Scholar

    Yang , T. and Fu , C. 1997. Heuristic algorithms for scheduling iterative task computations on distributed memory machines. IEEE Transactions on Parallel and Distributed Systems 8(6), 608–622.

    Google Scholar

    Zhao , H. & Sakellariou , R. 2004. A low-cost rescheduling policy for dependent tasks on grid computing systems. In The European Across Grids Conference, 21–31.

    Google Scholar

  • Cite this article

    Valeriia Haberland, Simon Miles, Michael Luck. 2019. Time-sensitive resource re-allocation strategy for interdependent continuous tasks. The Knowledge Engineering Review. 34:67 doi: 10.1017/S0269888919000067
    Valeriia Haberland, Simon Miles, Michael Luck. 2019. Time-sensitive resource re-allocation strategy for interdependent continuous tasks. The Knowledge Engineering Review. 34:67 doi: 10.1017/S0269888919000067
    shu
Download PDF

Article Metrics

Article views(16) PDF downloads(92)

Other Articles By Authors

ORIGINAL RESEARCH   Open Access    

Time-sensitive resource re-allocation strategy for interdependent continuous tasks

  • Bristol BS8 2BN

  • London WC2R 2LS

  • Received: 15 November 2017
  • Revised: 27 August 2018
  • Accepted: 12 June 2019
The Knowledge Engineering Review  34,  Article number: e9  (2019)  |  Cite this article

Abstract: Abstract: An increase in volumes of data and a shift towards live data enabled a stronger focus on resource-intensive tasks which run continuously over long periods. A Grid has potential to offer the required resources for these tasks, while considering a fair and balanced allocation of resources among multiple client agents. Taking this into account, a Grid might be unwilling to allocate its resources for long time, leading to task interruptions. This problem becomes even more serious if an interruption of one task may lead to the interruption of dependent tasks. Here, we discuss a new strategy for resource re-allocation which is utilized by a client with the aim to prevent too long interruptions by re-allocating resources between its own tasks. Those re-allocations are suggested by a client agent, but only a Grid can re-allocate resources if agreed. Our strategy was tested under the different Grid settings, accounting for the adjusted coefficients, and demonstrated noticeable improvements in client utilities as compared to when it is not considered. Our experiment was also extended to tests with environmental modelling and realistic Grid resource simulation, grounded in real-life Grid studies. These tests have also shown a useful application of our strategy.

    HTML

    Acknowledgments

    • Many thanks to King’s College London for awarding Graduate School Studentship and King’s Overseas Research Studentship to Valeriia Haberland in order to accomplish her PhD (Haberland, 2015).

    • This paper is an extended version of the paper presented at the joint European Conference on Multi-Agent Systems and Agreement Technologies by Haberland et al. (2017b). It extends a previously described strategy with detailed algorithms, an illustrative example, and an extended evaluation using a realistic Grid resource simulator and environment models, while also clarifying some model choices.

    • A linear combination (instead of a possible variety of nonlinear solutions) is chosen for a greater clarity of presentation and evaluation of SimTask.

    • These values were taken from our computer simulation.

    • This is a new experiment as compared to our evaluation in (Haberland et al., 2017b)

    Rights and permissions
    • © Cambridge University Press, 2019 2019Cambridge University Press
References (34)
  • About this article
    Cite this article
    Valeriia Haberland, Simon Miles, Michael Luck. 2019. Time-sensitive resource re-allocation strategy for interdependent continuous tasks. The Knowledge Engineering Review. 34:67 doi: 10.1017/S0269888919000067
    Valeriia Haberland, Simon Miles, Michael Luck. 2019. Time-sensitive resource re-allocation strategy for interdependent continuous tasks. The Knowledge Engineering Review. 34:67 doi: 10.1017/S0269888919000067
    shu

    • Catalog

      /

      DownLoad:  Full-Size Img  PowerPoint
      Return
      Return