Dissertation, University of Stuttgart, 2010

The ability to cope with change is one of the biggest challenges companies are facing today [JLN08]. Methods to increase business agility, such as outsourcing or off-shoring of non-core parts of the business are practiced already and will continue to play an important role in the future. A change in business however always means to also change the underlying IT infrastructure, which therefore needs to be designed in a way to be able to support flexible re-arrangement of its support for business operations. IT systems today are integrated using so called workflow management systems, that execute a business process in the form of "orchestrations" of the individual applications used for carrying out business functions.

 

These processes today are enacted centrally, i.e. the workflow engine acts as a central point of control governing the lifecycle of all activities of a process. This way of enacting processes has certain drawbacks, revealed when executing change such as outsourcing parts of a process. Using state-of-the-art workflow engines, this results in development of process partitions that need to be maintained separately and were not created because the original business goal has changed, but because the used workflow engine does not allow for flexible deployment of a single process model to multiple process engines. This thesis proposes a fundamentally new execution model for decentralized workflow enactment that does not have these drawbacks. It allows for flexible deployment of arbitrary partitions of the original workflow graph, thus supporting change at the level of business processes avoiding the need to change a process solely because the underlying IT infrastructure has changed.

 

The contributions of this thesis are: an in-depth analysis of differences between tuplespace-based and message-oriented middleware systems, a Petri net based formalization of tuplespace interactions called Executable Workflow Nets (EWFN), a fully-fledged Petri net formalization of WS-BPEL 2.0, a method and algorithm to execute Petri nets using tuplespaces and an architecture and implementation of the "coordination kernel" of a decentralized workflow engine that executes Petri net based workflows.

 

In the following, we present a summary of each chapter of this thesis.

 

Background and Related Work

 

Distributed Workflow enactment is a wide field in today's research on business process management. Chapter 2 consequently provides background on prominent technologies and surveys the field by highlighting key contributions. Relevant publications are analyzed with a focus on coordination languages, the use of Petri nets in workflow management and selected approaches in distributed workflow enactment.

 

The main differentiator of our work compared to state of the art is the avoidance of a central point of control by mapping the semantics of a given process execution language to token passing and thus allowing a given process model to be arbitrarily distributed. This exhibits the following characteristics that distinguish our approach from existing work: (i) arbitrary distribution of activities of a given process model, (ii) support for automatic, semi-automatic and fully user-driven partitioning of a process, and thereby, (iii) the ability to create partitions of a process influenced by business reasons e.g. outsourcing, as well as technical reasons such as better execution time or throughput, (iv) fullfledged support for WS-BPEL 2.0, not only a restricted subset of the language, (v) independence of a certain process definition language.

 

Comparison of Message-Oriented and Tuplespace-Based Middleware

 

A prerequisite to the decentralized execution model is a clear understanding of the concepts behind Linda [Gel85] and tuplespace computing. Before designing the execution model, in Chapter 3 we therefore analyze the properties of tuplespaces and compare them to message-oriented middleware, a technology found to be very similar by related work. While the comparisons done before use high-level properties such as levels of decoupling [AvdADtH05] or simple message exchange patterns [FKLT07, Ley06], the basis of our comparison are Enterprise Integration Patterns [HWB03]. These patterns represent harvested knowledge from almost two decades of applied use of message-oriented middleware in enterprise application integration (EAI) scenarios. For comparison, we assume tuplespaces instead of message-oriented middleware as the underpinning of the patterns and in that way, reveal the differences between both technologies.

 

The knowledge gained from the comparison is then used to decide whether tuplespaces or message-oriented middleware is a suitable basis to implement the inherent requirements such as absence of a central point of control or certain quality of services (QoS) to build a decentralized workflow engine. We conclude that tuplespaces are superior to messaging systems for our application. The drivers for this decision are that the tuplespace coordination model is very similar to Petri nets and thus to the execution model we foresee. Tuplespaces do not enforce a direction in communication and allow random access to tuples in a tuplespace. Furthermore, tuplespaces allow for destructive as well as non-destructive retrieval of tuples, enabling us to use the same middleware to handle both: data access (typically handled using non-destructive read operations) and control flow (typically expressed using destructive read operations). Additionally, tuplespaces implement the demanded decoupling dimensions and do not require a central point of control, the key requirement for independent activities and thus independent process partitions.

 

EWFN - An Execution Model for Decentralized Workflow Enactment

 

Next, a formal model to describe tuplespace-based interactions is developed in Chapter 4. Based on the close relationship of Petri nets and tuplespaces, this model uses non-hierarchical, Colored Petri Nets extended with read arcs and a Linda like template language [Gel85] instead of CPN ML for arc inscriptions. The resulting Petri net dialect is called "Executable Workflow Nets" (EWFN), as each element of the model has an equivalent element in a tuplespacebased application, making EWFNs directly executable on tuplespace-based middleware. We provide a formal description of the syntax and semantics of EWFNs, as well as a mapping to Place-Transition Nets, allowing standard Petri net analysis and verification techniques to be used with EWFNs.

 

Transformation of WS-BPEL 2.0 to EWFN

 

The EWFN model allows to describe tuplespace-based applications in a formal way. In order to execute process models using tuplespaces, a mapping from a process definition language such as WS-BPEL is required. In Chapter 5 we therefore express each element of the WS-BPEL 2.0 specification in form of an EWFN graph, specifying the semantics of a BPEL element by tuplespace operations and thus in a way that is executable directly on tuplespace systems. By doing so, we follow common practice in the implementation of workflow systems: Apache ODE for instance translates BPEL constructs into an internal object model that is executed using Jacob, a framework that provides - very much like tuplespaces do in our case - support for persistence and concurrency and thus builds the basis for process execution.

 

Tuplespace-Based Execution of EWFNs

 

Subsequently, Chapter 6 discusses how to execute EWFNs using tuplespaces. We start by introducing several possibilities of execution based on different kinds of Petri nets such as Place-Transition or Colored Petri Nets. A major aspect of executing Petri nets on tuplespaces is the way how the structure of the Petri net graph is encoded in tuples. For efficient execution, we present algorithms to implement basic tuplespace operations such as writing, destructive and non-destructive consumption of tuples as well as for batch operations such as multi-read or update. Furthermore, the problem of synchronized consumption of tuples in tuplespaces is discussed and a solution in form of the sync operation is proposed.

 

Architecture and Implementation

 

The next part of this thesis describes the architecture and implementation of the tuplespace kernel that natively executes EWFNs and thus builds the basis for the implemented, decentralized workflow engine. In particular, the presented tuplespace kernel implements the tuplespace operations discussed in the previous chapter for efficient EWFN execution. This chapter also defines EWFN-ML, the XML-based serialization format for EWFNs.

 

Finally, in Chapter 8 a summary of the contribution is presented and several areas for future research are identified.