Adaptive selection of necessary and sufficient checkpoints for dynamic verification of temporal constraints in grid workflow systems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Adaptive selection of necessary and sufficient checkpoints for dynamic verification of temporal constraints in grid workflow systems

Full text

Pdf (696 KB)

Source

ACM Transactions on Autonomous and Adaptive Systems (TAAS) archive
Volume 2 , Issue 2 (June 2007) table of contents

Article No. 6

Year of Publication: 2007

ISSN:1556-4665

Authors

Jinjun Chen	Swinburne University of Technology, Melbourne, Australia
Yun Yang	Swinburne University of Technology, Melbourne, Australia

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 15, Downloads (12 Months): 195, Citation Count: 1

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTex EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1242060.1242063 What is a DOI?

ABSTRACT

In grid workflow systems, a checkpoint selection strategy is responsible for selecting checkpoints for conducting temporal verification at the runtime execution stage. Existing representative checkpoint selection strategies often select some unnecessary checkpoints and omit some necessary ones because they cannot adapt to the dynamics and uncertainty of runtime activity completion duration. In this article, based on the dynamics and uncertainty of runtime activity completion duration, we develop a novel checkpoint selection strategy that can adaptively select not only necessary, but also sufficient checkpoints. Specifically, we introduce a new concept of minimum time redundancy as a key reference parameter for checkpoint selection. An important feature of minimum time redundancy is that it can adapt to the dynamics and uncertainty of runtime activity completion duration. We develop a method on how to achieve minimum time redundancy dynamically along grid workflow execution and investigate its relationships with temporal consistency. Based on the method and the relationships, we present our strategy and rigorously prove its necessity and sufficiency. The simulation evaluation further demonstrates experimentally such necessity and sufficiency and its significant improvement on checkpoint selection over other representative strategies.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Al-ali, R., Amin, K., Laszewski, G. V., Rana, O., Walker, D., Hategan, M., and Zaluzec, N. 2004. Analysis and provision of QoS for distributed grid applications. J. Grid Comput. 2, 2, 163--182.
	2	Abramson, D., Kommineni, J., McGregor, J. L., and Katzfey, J. 2004. An atmospheric sciences workflow and its implementation with Web services. In Proceedings of the 4th International Conference on Computational Science, Part I. Lecture Notes in Computer Science, vol. 3036, Springer Verlag, 164--173.
	3	Kaizar Amin , Gregor von Laszewski , Mihael Hategan , Nestor J. Zaluzec , Shawn Hampton , Albert Rossi, GridAnt: A Client-Controllable Grid Work.ow System, Proceedings of the Proceedings of the 37th Annual Hawaii International Conference on System Sciences (HICSS'04) - Track 7, p.70210.3, January 05-08, 2004
	4	Buyya, R., Abramson, D., and Venugopal, S. 2005. The grid economy. Proceedings of the IEEE 93, 3, 698--714.
	5	Junwei Cao , Stephen A. Jarvis , Subhash Saini , Graham R. Nudd, GridFlow: Workflow Management for Grid Computing, Proceedings of the 3st International Symposium on Cluster Computing and the Grid, p.198, May 12-15, 2003
	6	Jinjun Chen , Yun Yang , T. Y. Chen, Dynamic Verification of Temporal Constraints on-the-fly for Workflow Systems, Proceedings of the 11th Asia-Pacific Software Engineering Conference (APSEC'04), p.30-37, November 30-December 03, 2004 [doi>10.1109/APSEC.2004.47]
	7	Chen, J. and Yang, Y. 2005a. An activity completion duration based checkpoint selection strategy for dynamic verification of fixed-time constraints in grid workflow systems. In Proceedings of the 2nd International Conference on Grid Service Engineering and Management (GSEM'05). Lecture Notes in Informatics P-69, 296--310.
	8	Jinjun Chen , Yun Yang, Multiple Temporal Consistency States for Dynamical Verification of Upper Bound Constraints in Grid Workflow Systems, Proceedings of the First International Conference on e-Science and Grid Computing, p.124-131, December 05-08, 2005 [doi>10.1109/E-SCIENCE.2005.60]
	9	Jinjun Chen , Yun Yang, A Minimum Proportional Time Redundancy based Checkpoint Selection Strategy for Dynamic Verification of Fixed-time Constraints in Grid Workflow Systems, Proceedings of the 12th Asia-Pacific Software Engineering Conference (APSEC'05), p.299-306, December 15-17, 2005 [doi>10.1109/APSEC.2005.11]
	10	Chen, J. and Yang, Y. 2006. Selecting necessary and sufficient checkpoints for dynamic verification of fixed-time constraints in grid workflow systems. In Proceedings of the 4th International Conference on Business Process Management (BPM'06). Lecture Notes in Computer Science, vol. 4102, Springer-Verlag, 445--450.
	11	Chinn, S. and Madey, G. 2000. Temporal representation and reasoning for workflow in engineering design change review. IEEE Trans. Engin. Manag. 47, 4, 485--492.
	12	Crown Team. 2006. CROWN portal, http://www.crown.org.cn/en/.
	13	Dieter Cybok, A Grid workflow infrastructure: Research Articles, Concurrency and Computation: Practice & Experience, v.18 n.10, p.1243-1254, August 2006 [doi>10.1002/cpe.v18:10]
	14	Deelman, E., Blythe, J., Gil, Y., Kesselman, C., Mehta, G., and Vahi, K. 2003. Mapping abstract complex workflows onto grid environments. J. Grid Comput. 1, 1, 9--23.
	15	Johann Eder , Euthimios Panagos , Michael Rabinovich, Time Constraints in Workflow Systems, Proceedings of the 11th International Conference on Advanced Information Systems Engineering, p.286-300, June 14-18, 1999
	16	Fahringer, T., Pllana, S., and Villazon, A. 2004. A-GWL: Abstract grid workflow language. In Proceedings of the 4th International Conference on Computational Science, Part III, Lecture Notes in Computer Science, vol. 3038, Springer Verlag, 42--49.
	17	Foster, I., Kesselman, C., Nick, J., and Tuecke, S. 2002. The physiology of the grid: An open grid services architecture for distributed systems integration. In Proceedings of the 5th Global Grid Forum Workshop (GGF5).
	18	Claus Hagen , Gustavo Alonso, Exception Handling in Workflow Management Systems, IEEE Transactions on Software Engineering, v.26 n.10, p.943-958, October 2000 [doi>10.1109/32.879818 ]
	19	Han, Y., Sheth, A., and Bussler, C. 1998. A taxonomy of adaptive workflow management. In Proceedings of (Workshop on Towards Adaptive Workflow Systems) the ACM Conference on Computer Supported Cooperative Work.
	20	Yan Huang, JISGA: A Jini-Based Service-Oriented Grid Architecture, International Journal of High Performance Computing Applications, v.17 n.3, p.317-327, August 2003 [doi>10.1177/1094342003173001]
	21	Justus Klingemann , Jürgen Wäsch , Karl Aberer, Deriving Service Models in Cross-Organizational Workflows, Proceedings of the Ninth International Workshop on Research Issues on Data Engineering: Information Technology for Virtual Enterprises, p.100, March 23-24, 1999
	22	Justus Klingemann , Jürgen Wäsch , Karl Aberer, Adaptive Outsourcing in Cross-Organizational Workflows, Proceedings of the 11th International Conference on Advanced Information Systems Engineering, p.417-421, June 14-18, 1999
	23	Krishnan, S., Wagstrom, P., and Laszewski, G. V. 2002. GSFL: A workflow framework for grid services. Tech. rep., Argonne National Laboratory, Argonne, Chicago, IL, http://www-unix.globus.org/cog/papers/gsfl-paper.pdf.
	24	Hongchen Li , Yun Yang , T. Y. Chen, Resource constraints analysis of workflow specifications, Journal of Systems and Software, v.73 n.2, p.271-285, October 2004 [doi>10.1016/S0164-1212(03)00250-4]
	25	Li, J., Fan, Y., and Zhou, M. 2003. Timing constraint workflow nets for workflow analysis. IEEE Trans. Syst., Man Cybernet. Part A: Syst. Humans 33, 2, 179--193.
	26	Zhen Liu, Performance Analysis of Stochastic Timed Petri Nets Using Linear Programming Approach, IEEE Transactions on Software Engineering, v.24 n.11, p.1014-1030, November 1998 [doi>10.1109/32.730548 ]
	27	Marinescu, D. 2002. A grid workflow management architecture. Global Grid Forum White Paper, http://www.gridforum.org/mail_archive/gce-wg/2002/Archive/pdf00003.pdf.
	28	Marjanovic, O., and Orlowska, M. E. 1999. On modeling and verification of temporal constraints in production workflows. Know. Inform. Syst. 1, 2, 157--192.
	29	Reichert, M., Bauer, T., and Dadam, P. 1999. Enterprise-wide and cross-enterprise workflow management: Challenges and research issues for adaptive workflows. In Proceedings of Workshop on Enterprise-Wide and Cross-Enterprise Workflow Management. 56--64.
	30	Stefanie Rinderle , Manfred Reichert , Peter Dadam, Flexible Support of Team Processes by Adaptive Workflow Systems, Distributed and Parallel Databases, v.16 n.1, p.91-116, July 2004 [doi>10.1023/B:DAPD.0000026270.78463.77]
	31	Wasim Sadiq , Maria E. Orlowska, Analyzing process models using graph reduction techniques, Information Systems, v.25 n.2, p.117-134, April 2000 [doi>10.1016/S0306-4379(00)00012-0 ]
	32	Simpson, D. R., Kelly, N., Jithesh, P. V., Donachy, P., Harmer, T. J., Perrott, R. H., Johnston, J., Kerr, P., McCurley, M., and McKee, S. 2004. GeneGrid: A practical workflow implementation for a grid based virtual bioinformatics laboratory. In Proceedings of the UK e-Science All Hands Meeting. 547--554.
	33	Jin Hyun Son , Myoung Ho Kim, Improving the performance of time-constrained workflow processing, Journal of Systems and Software, v.58 n.3, p.211-219, September 15, 2001 [doi>10.1016/S0164-1212(01)00039-5 ]
	34	Swin De W-G Team. 2007. System architecture of SwinDeW-G. http://www.ict.swin.edu.au/personal/jchen/SwinDeW-G/System_Architecture.pdf.
	35	van der Aalst, W. M. P. 1998. The application of petri nets to workflow management. J. Circ. Syst. Comput. 8, 1, 21--66.
	36	Wil M. P. van der Aalst, Workflow Verification: Finding Control-Flow Errors Using Petri-Net-Based Techniques, Business Process Management, Models, Techniques, and Empirical Studies, p.161-183, January 2000
	37	Yan, J., Yang, Y., and Raikundalia, G. K. 2006. SwinDeW---A peer-to-peer based decentralised workflow management system. IEEE Trans. Syst. Man Cybern. Part A: Syst. Humans 36, 5, 922--935.
	38	Jia Yu , Rajkumar Buyya, A taxonomy of scientific workflow systems for grid computing, ACM SIGMOD Record, v.34 n.3, September 2005 [doi>10.1145/1084805.1084814]
	39	Jia Yu , Rajkumar Buyya , Chen Khong Tham, Cost-Based Scheduling of Scientific Workflow Application on Utility Grids, Proceedings of the First International Conference on e-Science and Grid Computing, p.140-147, December 05-08, 2005 [doi>10.1109/E-SCIENCE.2005.26]
	40	Hai Zhuge , To-yat Cheung , Hung-Keng Pung, A timed workflow process model, Journal of Systems and Software, v.55 n.3, p.231-243, Jan.15.2001 [doi>10.1016/S0164-1212(00)00073-X ]