In grid workflow systems, to verify temporal constraints efficiently at the run-time execution stage, some checkpoints are selected such that temporal verification need only be conducted at those checkpoints rather than at all activity points. However, existing typical checkpoint selection strategies may ignore some necessary checkpoints and select some unnecessary ones. This eventually impacts overall temporal verification effectiveness and efficiency. To improve such status, in this paper, we develop a new checkpoint selection strategy. Specifically, we first investigate the relationships between activity completion duration and the consistency of temporal constraints. Then, based on those relationships we present our new checkpoint selection strategy. Our new strategy can avoid the omission of necessary checkpoints and the selection of excess unnecessary checkpoints. Consequently, it can achieve better temporal verification effectiveness and efficiency than the existing typical checkpoint selection strategies. The final comparison and quantitative evaluation further demonstrate this result.
Aalst, W. M. P. van der (2000). Workflow verification: Finding control-flow errors using Petri-net based techniques, in International Conference on Business Process Management: Models, Techniques, and Empirical Studies Proceedings, Berlin, Germany, LNCS Vol. 1806, Berlin: Springer-Verlag, pp. 161-183.
2.
Abramson, D., Kommineni, J., McGregor, J.L., and Katzfey, J. (2005). An atmospheric sciences workflow and its implementation with Web services, Future Generation Computer Systems, 21(1): 69-78.
3.
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, Journal of Grid Computing, 2(2): 163-182.
4.
Amin, K., Laszewski, G.V., Hategan, M., Zaluzec, N.J., Hampton, S., and Rossi, A. (2004). GridAnt: A client-controllable grid workflow, in 37th Annual Hawaii International Conference on System Sciences (HICSS'04) Proceedings, Hawaii, Los Alamitos, CA: IEEE CS Press, pp. 210-219.
5.
Brandic, I., Benkner, S., Engelbrecht, G., and Schmidt, R. (2005). Towards Quality of Service support for grid workflows , in European Grid Conference Proceedings, Amsterdam, The Netherlands, LNCS Vol. 3470, Berlin: Springer-Verlag, pp. 661-670.
6.
Buyya, R., Abramson, D., and Venugopal, S. (2005). The grid economy, Proceedings of The IEEE, 93(3): 698-714.
7.
Cao, J.Jarvis, S.A., Saini, S., and Nudd, G.R. (2003). Grid-Flow: Workflow management for grid computing , in 3rd IEEE/ACM International Symposium on Cluster Computing and the Grid (CCGrid 2003) Proceedings, Tokyo , Japan, Los Alamitos, CA: IEEE CS Press, pp. 198-205.
8.
Chen, J. and Yang, Y. (2004). Temporal dependency for dynamic verification of temporal constraints in workflow systems, in 3rd International Conference on Grid and Cooperative Computing (GCC2004) Proceedings , Wuhan, China, LNCS Vol. 3251, Berlin: Springer-Verlag , pp. 1005- 1008.
9.
Chen, J. and Yang, Y. (2005a). Temporal dependency for dynamic verification of fixed-date constraints in grid workflow systems, in 7th Asia Pacific Web Conference (APWeb2005) Proceedings, Shanghai, China, LNCS Vol. 3399, Berlin: Springer-Verlag, pp. 820-831.
10.
Chen, J. and Yang, Y. (2005b). An activity completion duration based checkpoint selection strategy for dynamic verification of fixed-time constraints in grid workflow systems, in 2nd International Conference on Grid Service Engineering and Management (GSEM2005) Proceedings, Erfurt, Thuringia, Germany, LNI P-69, pp. 296-310.
11.
Chen, J. and Yang, Y. (2007). Multiple states based temporal consistency for dynamic verification of fixed-time constraints in grid workflow systems, Concurrency and Computation: Practice and Experience, 19(7): 965-982.
12.
Chen, J., Yang, Y., and Chen T. Y. (2004). Dynamic verification of temporal constraints on-the-fly for workflow systems, in 11th Asia-Pacific Software Engineering Conference (APSEC2004) Proceedings, Busan, Korea. Los Alamitos, CA: IEEE CS Press, pp. 30-37.
13.
Chinn, S. and Madey, G. (2000). Temporal representation and reasoning for workflow in engineering design change review, IEEE Transactions on Engineering Management, 47(4): 485-492.
14.
Cybok, D. (2006). A grid workflow infrastructure, Concurrency and Computation: Practice and Experience, 18(10): 1243- 1254.
15.
Deelman, E., Blythe, J., Gil, Y., Kesselman, C., Mehta, G., and Vahi, K. (2003). Mapping abstract complex workflows onto grid environments , Journal of Grid Computing, 1(1): 9-23.
16.
Eder, J., Panagos, E., and Rabinovich, M. (1999). Time constraints in workflow systems, in 11th International Conference on Advanced Information Systems Engineering (CAiSE'99) Proceedings, Heidelberg , Germany, LNCS Vol. 1626, Berlin: Springer-Verlag, pp. 286-300.
17.
Fahringer, T., Pllana, S., and Villazon, A. (2004). A-GWL: Abstract grid workflow language, in 4th International Conference on Computational Science Proceedings, Part III, Krakow, Poland, LNCS Vol. 3038, Berlin: Springer-Verlag, pp. 42-49.
18.
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 5th Global Grid Forum Workshop (GGF5), Edinburgh, Scotland, http://www.globus.org/alliance/publications/papers/ogsa.pdf , accessed on Feb. 1, 2007.
19.
Goble, C. (2004). Building ad hoc (personal) workflows in an open world: myGrid experiences, in 12th Global Grid Forum Workshop (GGF12), http://www.isi.edu/~deelman/wfm-rg/ggf12/GGF12goble.ppt, accessed on Feb. 1, 2007.
20.
Hagen, C. and Alonso, G. (2000). Exception handling in workflow management systems , IEEE Transactions on Software Engineering, 26(10): 943-958.
21.
Huang, Y. (2003). JISGA: A JINI-based service-oriented grid architecture , The International Journal of High Performance Computing Applications, 17(3): 317-327.
22.
Krishnan, S., Wagstrom, P., and Laszewski, G.V. (2002). GSFL: A workflow framework for grid services, Technical Report ANL/MCS-P980-0802, Argonne National Laboratory, U.S.A, http://www.-unix.globus.org/cog/papers/gsfl-paper.pdf, accessed on Feb. 1, 2007.
23.
Li, H., Yang, Y., and Chen, T.Y. (2004). Resource constraints analysis of workflow specifications , The Journal of Systems and Software, 73(2): 271-285.
24.
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 , accessed on Feb. 1, 2007.
25.
Marjanovic, O., and Orlowska, M.E. (1999). On modeling and verification of temporal constraints in production workflows, Knowledge and Information Systems , 1(2): 157- 192.
26.
Rinderle, S., Reichert, M., and Dadam, P. (2004). On dealing with structural conflicts between process type and instance changes, in 2nd International Conference on Business Process Management (BPM2004) Proceedings, Potsdam, Germany, LNCS Vol. 3080, Berlin: Springer-Verlag, pp. 274-289.
27.
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 3rd UK e-Science All Hands Meeting 2004 (AHM04) Proceedings, Nottingham, UK, Swindon UK: UK Engineering and Physical Science Research Council, pp. 547-554.
28.
Yu, J., Buyya, R., and Tham, C.K. (2005). Cost-based scheduling of scientific workflow applications on utility grids, in: 1st International Conference on e-Science and Grid Computing (e-Science2005) Proceedings, Melbourne, Australia, Los Alamitos, CA: IEEE CS Press, pp. 140-147.
29.
Zhuge, H., Cheung, T., and Pung, H. (2001). A timed workflow process model, The Journal of Systems and Software, 55(3): 231-243.
