research-article

Termination analysis of business process workflows

Authors:

Mandy Weißbach,

Wolf ZimmermannAuthors Info & Claims

WEWST '10: Proceedings of the 5th International Workshop on Enhanced Web Service Technologies

Pages 18 - 25

https://doi.org/10.1145/1883133.1883137

Published: 01 December 2010 Publication History

Abstract

For safety and deadlock analysis of workflows, Petri-Nets are frequently used. They provide a natural abstraction of workflows since they are able to describe parallel behavior. With a variety of model checking tools, it is possible to verify these workflows. The usual approach that abstracts business processes to Petri-Nets requires that each loop (whether purely internal or with external interactions) is terminating. In this paper, we show that without this termination assumption, there are real behaviors of business processes that are not represented by the Petri-Net abstractions and we provide a first approach towards termination analysis of loops in business processes thereby ensuring the preconditions required by many Petri-Net based approaches for analyzing business processes.

References

[1]

Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman. Compilers: Principles, Techniques, and Tools (2nd Edition). Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 2006.

Digital Library

[2]

Hugh Anderson and Siau-Cheng Khoo. Regular approximation and bounded domains for size-change termination. In PEPM '10: Proceedings of the 2010 ACM SIGPLAN workshop on Partial evaluation and program manipulation, pages 53--62, New York, NY, USA, 2010. ACM.

Digital Library

[3]

Andreas Both, Wolf Zimmermann, and René Franke. Model checking of component protocol conformance -- optimizations by reducing false negatives. Electron. Notes Theor. Comput. Sci., 263:67--94, 2010.

Digital Library

[4]

Kelly Rosa Braghetto, Jo ao Eduardo Ferreira, and Calton Pu. Using process algebra to control the execution of business processes. In SAC '08: Proceedings of the 2008 ACM symposium on Applied computing, pages 128--129, New York, NY, USA, 2008. ACM.

Digital Library

[5]

Van Breugel and Maria Koshkina. Models and verification of bpel franck.

[6]

Remco M. Dijkman, Marlon Dumas, and Chun Ouyang. Semantics and analysis of business process models in bpmn. Inf. Softw. Technol., 50(12):1281--1294, 2008.

Digital Library

[7]

Edsger W. Dijkstra. A Discipline of Programming. Prentice Hall, Inc., October 1976.

Digital Library

[8]

Edsger W. Dijkstra. Go to statement considered harmful. pages 351--355, 2002.

Digital Library

[9]

Ziyang Duan, Arthur Bernstein, Philip Lewis, and Shiyong Lu. A model for abstract process specification, verification and composition. In ICSOC '04: Proceedings of the 2nd international conference on Service oriented computing, pages 232--241, New York, NY, USA, 2004. ACM.

Digital Library

[10]

R. W. Floyd. Assigning meanings to programs. Mathematical aspects of computer science, 19(19--32):1, 1967.

[11]

David Gries. The Science of Programming. Springer-Verlag New York, Inc., Secaucus, NJ, USA, 1987.

Digital Library

[12]

Thomas S. Heinze, Wolfram Amme, and Simon Moser. Prozessumstrukturierung unter berücksichtigung von nachrichteninhalten. In ZEUS, pages 89--96, 2010.

[13]

Frank Heitmann and Daniel Moldt. Petri nets tool database. Online.

[14]

Sebastian Hinz, Karsten Schmidt, and Christian Stahl. Transforming bpel to petri nets. In Wil M. P. van der Aalst, Boualem Benatallah, Fabio Casati, and Francisco Curbera, editors, Proceedings of the 3rd Int'l Conference on Business Process Management (BPM 2005), pages 220--235, Nancy, France, 2005. Springer Verlag.

Digital Library

[15]

C. A. R. Hoare. An axiomatic basis for computer programming. Commun. ACM, 12(10):576--580, 1969.

Digital Library

[16]

Bartek Kiepuszewski, Arthur H. M. ter Hofstede, and Christoph Bussler. On structured workflows modelling. In CAiSE '00: Proceedings of the 12th International Conference on Advanced Information Systems Engineering, pages 431--445, London, UK, 2000. Springer-Verlag.

Digital Library

[17]

Chin Soon Lee, Neil D. Jones, and Amir M. Ben-Amram. The size-change principle for program termination. SIGPLAN Not., 36(3):81--92, 2001.

Digital Library

[18]

Niels Lohmann. A feature-complete Petri net semantics for WS-BPEL 2.0 and its compiler BPEL2oWFN. Informatik-Berichte 212, Humboldt-Universität zu Berlin, Berlin, Germany, August 2007.

[19]

T. Murata. Petri nets: Properties, analysis and applications. Proceedings of the IEEE, 77(4):541--580, August 2002.

[20]

W. Reisig. Modeling- and analysis techniques for web services and business processes. In In FMOODS, pages 243--258, 2005.

Digital Library

[21]

Ana M. Roldan, Ernesto Pimentel, and Antonio Brogi. Software composition with linda. Comput. Lang. Syst. Struct., 35(4):395--405, 2009.

Digital Library

[22]

Ioan Salomie, Tudor Cioara, Ionut Anghel, Mihaela Dinsoreanu, and Tudor Ioan Salomie. A layered workflows model enhanced with process algebra verification for industrial processes. In IEEE 3rd International Conference on Intelligent Computer Communication and Processing, pages 185--191, September 2007.

[23]

Ioan Salomie, Tudor Cioara, Ionut Anghel, Mihaela Dinsoreanu, and Tudor Ioan Salomie. Workflows models enhanced with process algebra verification for industrial business processes. In ICCOMP'07: Proceedings of the 11th WSEAS International Conference on Computers, pages 502--507, Stevens Point, Wisconsin, USA, 2007. World Scientific and Engineering Academy and Society (WSEAS).

Digital Library

[24]

H. W. Schmidt and W. Zimmermann. A complexity calculus for object-oriented programs. Journal of Object-Oriented Systems, 1(2):117--147, 1994.

[25]

H. W. Schmidt and W. Zimmermann. Reasoning about complexity of object-oriented programs. In E.-R. Olderog, editor, Programming Concepts, Methods and Calculi, volume A-56 of IFIP Transactions, pages 553--572, 1994.

Digital Library

[26]

OASIS Web Services Business Process Execution Language (WSBPEL) TC. Web services business process execution language version 2.0 (oasis standard). Online, April 2007.

[27]

A. H. M. ter Hofstede, M. E. Orlowska, and J. Rajapakse. Verification problems in conceptual workflow specifications. Data and Knowledge Engineering, 24:239--256, 1996.

Digital Library

[28]

W. M. P. van der Aalst. Three good reasons for using a Petri-net-based workflow management system. In S. Navathe and T. Wakayama, editors, Proceedings of the International Working Conference on Information and Process Integration in Enterprises (IPIC'96), pages 179--201, 1996.

[29]

W. M. P. van der Aalst. The application of Petri nets to workflow management. The Journal of Circuits, Systems and Computers, 8(1):21--66, 1998.

[30]

W. M. P. van der Aalst. Formalization and verification of event-driven process chains. Information and Software Technology, 41(10):639--650, 1999.

[31]

W. M. P. van der Aalst and Ter. Yawl: yet another workflow language. Information Systems, 30(4):245--275, June 2005.

Digital Library

[32]

Wil M. P. van der Aalst. Verification of workflow nets. In ICATPN '97: Proceedings of the 18th International Conference on Application and Theory of Petri Nets, pages 407--426, London, UK, 1997. Springer-Verlag.

Digital Library

[33]

Wil M. P. van der Aalst, Alistair P. Barros, Arthur H. M. ter Hofstede, and Bartek Kiepuszewski. Advanced workflow patterns. In CooplS '02: Proceedings of the 7th International Conference on Cooperative Information Systems, pages 18--29, London, UK, 2000. Springer-Verlag.

Digital Library

[34]

Ben Wegbreit. Mechanical program analysis. Commun. ACM, 18(9):528--539, 1975.

Digital Library

[35]

WFMC. Wfmc-tc-1025-oct-10-08-a (final xpdl 2.1 specification). Online, October 2008.

[36]

Wolf Zimmermann. Automatische Komplexitätsanalyse funktionaler Programme. Informatik-Fachberichte. Springer, 1990.

Cited By

Weißbach M(2018)Deadlock Analysis of Service-Oriented Systems with Recursion and ConcurrencyAdvances in Service-Oriented and Cloud Computing10.1007/978-3-319-72125-5_20(247-259)Online publication date: 31-Jan-2018
https://doi.org/10.1007/978-3-319-72125-5_20
Weißbach MZimmermann W(2017)On Abstraction-Based Deadlock-Analysis in Service-Oriented Systems with RecursionService-Oriented and Cloud Computing10.1007/978-3-319-67262-5_13(168-176)Online publication date: 1-Sep-2017
https://doi.org/10.1007/978-3-319-67262-5_13
Wang MZhu LRamamohanarao K(2015)Reasoning task dependencies for robust service selection in data intensive workflowsComputing10.1007/s00607-013-0381-697:4(337-355)Online publication date: 1-Apr-2015
https://dl.acm.org/doi/10.1007/s00607-013-0381-6
Show More Cited By

Index Terms

Termination analysis of business process workflows
1. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Formal software verification
  2. Software organization and properties
    1. Software functional properties
      1. Formal methods

Recommendations

Optimization of WS-BPEL Workflows through Business Process Re-Engineering Patterns

With the advent of XML-based SOA, WS-BPEL swiftly became a widely accepted standard for modeling business processes. Although SOA is said to embrace the principle of business agility, BPEL process definitions are still manually crafted into their final ...
A business process explorer: recovering and visualizing e-commerce business processes
ICSE '08: Proceedings of the 30th international conference on Software engineering

A business process is composed of a set of interrelated tasks which are joined together by control flow elements. E-commerce systems implement business processes to automate the daily operations of an organization. Organizations must continuously modify ...
Enterprise architecture patterns for business process support analysis

The field of enterprise architectures lacks architecture patterns that would support analysis of a given enterprise architecture, comparison of different enterprise architecture solutions and provide guidelines for development of a target enterprise ...

Comments

Information & Contributors

Information

Published In

cover image ACM Other conferences

WEWST '10: Proceedings of the 5th International Workshop on Enhanced Web Service Technologies

December 2010

48 pages

ISBN:9781450302388

DOI:10.1145/1883133

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 December 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

WEWST '10

WEWST '10: Workshop on Enhanced Web Service Technologies

December 1, 2010

Ayia Napa, Cyprus

Acceptance Rates

WEWST '10 Paper Acceptance Rate 5 of 13 submissions, 38%;

Overall Acceptance Rate 5 of 13 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
237
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Weißbach M(2018)Deadlock Analysis of Service-Oriented Systems with Recursion and ConcurrencyAdvances in Service-Oriented and Cloud Computing10.1007/978-3-319-72125-5_20(247-259)Online publication date: 31-Jan-2018
https://doi.org/10.1007/978-3-319-72125-5_20
Weißbach MZimmermann W(2017)On Abstraction-Based Deadlock-Analysis in Service-Oriented Systems with RecursionService-Oriented and Cloud Computing10.1007/978-3-319-67262-5_13(168-176)Online publication date: 1-Sep-2017
https://doi.org/10.1007/978-3-319-67262-5_13
Wang MZhu LRamamohanarao K(2015)Reasoning task dependencies for robust service selection in data intensive workflowsComputing10.1007/s00607-013-0381-697:4(337-355)Online publication date: 1-Apr-2015
https://dl.acm.org/doi/10.1007/s00607-013-0381-6
Wang MZhu LChen J(2012)Risk-Aware Checkpoint Selection in Cloud-Based Scientific WorkflowProceedings of the 2012 Second International Conference on Cloud and Green Computing10.1109/CGC.2012.46(137-144)Online publication date: 1-Nov-2012
https://dl.acm.org/doi/10.1109/CGC.2012.46
Börger E(2012)Approaches to modeling business processesSoftware and Systems Modeling (SoSyM)10.1007/s10270-011-0214-z11:3(305-318)Online publication date: 1-Jul-2012
https://dl.acm.org/doi/10.1007/s10270-011-0214-z
Rybacki SHimmelspach JHaack FUhrmacher A(2011)WorMS- a framework to support workflows in M&SProceedings of the Winter Simulation Conference10.5555/2431518.2431602(716-727)Online publication date: 11-Dec-2011
https://dl.acm.org/doi/10.5555/2431518.2431602
Rybacki SHimmelspach JHaack FUhrmacher A(2011)WORMS- A framework to support workflows in M&SProceedings of the 2011 Winter Simulation Conference (WSC)10.1109/WSC.2011.6147799(716-727)Online publication date: Dec-2011
https://doi.org/10.1109/WSC.2011.6147799

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten