ABSTRACT
This study presents an approach to judge the soundness of inter-organizational workflowl. It focuses on interactive messages in an inter-organizational system. Each workflow entity is packaged based on the object-oriented technologies. Firstly, this study defines a function of Finish (CPNW) (Cooperation Petri net Workflow-CPNW), which contains all messages that can interactive smoothly in the system. Then, an algorithm of getting the Finish (CPNW) is given. The next methods of deciding the soundness of inter-organizational workflows are obtained based on the algorithm. This study gives one theorem and one corollary to judge the soundness of inter-organizational workflow. And a simple example is given to validate the theorem. Further more, the soundness of CPNWs with resources competition is analyzed.
PDF Abstract XML References Citation
How to cite this article
DOI: 10.3923/itj.2008.1194.1199
URL: https://scialert.net/abstract/?doi=itj.2008.1194.1199
INTRODUCTION
In the 1980s, the term workflow was first used in its modern form in the software industry by Filenet vice president David Siegel. From then on, workflows have developing fast. Some research productions in workflow area have been used for practical applications now.
With the developing of electronic commerce and international companies, many existing business processes involve more than one organization. In order to describe these business processes, inter-organizational workflows are defined (Van der Aalst, 1998).
Inter-organizational workflows is one of the hottest topics now. Usually, Petri Nets (PN) are used to modeling inter-organizational workflows (Van der Aalst, 1998). In this study, one workflow described by PNs is called as Petri Net Workflow (PNW). One inter-organizational workflow described by PNs is called as Cooperation Petri Net Workflow (CPNW). PNs is a graphical and mathematical tool for modeling concurrent/distributed systems, which permit the explicit representation of the states and transitions of a system. PNs are a suitable modeling tool for workflows, because of several reasons: First, PNs are a graphical and intuitive language. They have a formal semantics and are expressive. Then, there are many analysis techniques used to investigate the properties of PNs.
Van der Aalst (2000) defined IOWF-nets (Inter-Organizational Workflow-IOWF) to model loosely coupled Inter-organizational workflows (Aalst, 2000). In the study, an IOWF-net is used to describe the local workflows and the coordination structures among them. An XRL (eXchangeable Routing Language) language based on XML languages can be used to specify inter-organizational workflows (Verbeek et al., 2002). And the Public-To-Private (P2P) approach may be used to describe inter-organizational workflows based on a notion of inheritance (Van der Aalst, 2003b). The public parts are related each other, making up an Inter-organizational workflow. Each private workflow corresponds to an actual workflow as it is executed in one of the domains. The P2P approach guarantees that each private workflow is a subclass of the corresponding public part under projection inheritance.
A new modeling approach of inter-organizational workflows is proposed based on PNs (Prisecaru and Jucan, 2008). It deals with loosely coupled inter-organizational workflows: there are n local workflow processes which can execute independently, but need to interact at certain points in order to achieve a global business goal. Moreover, a notion of soundness is introduced and it proves that soundness is decidable.
However, the analysis tools of soundness of inter-organizational workflows are lacking. Therefore, we focus on the interactive messages of inter-organizational workflows in this study to discuss the soundness of inter-organizational workflows. An object-oriented technology (Khetarpal et al., 1998) is used to analyze the soundness of inter-organizational workflows. The object-oriented technology is a whole-part method and each private workflow is considered as one object. Because this study focuses on the analysis of the soundness of inter-organizational workflows, we put more attention on the whole part and interactive actions of the workflows. Some details inside one private workflow are neglected. We investigate interactive messages need to satisfy the properties in a sound inter-organizational workflow. First, we analyze interactive messages by departing them to two parts (send messages and receive messages). Then by an illustrating example, we obtain an efficient method for deciding the soundness of inter-organizational workflows. More definitely, the method proposed in this study is validated based on a Customer-Company sale system.
A CUSTOMER AND COMPANY SALE SYSTEM
There exist many inter-organizational workflow systems in practical application. Here, we introduce a customer and company sale system (Du et al., 2008). Usually, in this system, there is one company and several customers. The company and each customer are private workflows. Each private workflow runs smoothly itself. When one customer buys some products from the company, it is an inter-organizational workflow. The normal proceeding process is as follows:
• | The company send products` introduction to customers |
• | Customers send order message or refuse message to the company |
• | If the company receives the orders. It begins to produce products and send them to customers |
• | Customers receive products they ordered and then they send money to the company |
• | The company receives money. Thus the trade is finished |
Figure 1 gives the model of a Customer and Company system. For simplicity, assume that there are only one company and one customer in this system. The company and the customer are two single entities. They are described as two private workflows by PNs. The customer buys products from the company. The company offers products to the customer. The inter-organizational workflow describes two entities` work process and the interactive messages between them. It has several interactive messages: company sending offer, customer sending refusal, customer sending order, company sending goods and customer payment.
For simplicity, we neglect the details of each private workflow. So, the Customer and Company system can be described simply in Fig. 2.
Fig. 1: | CPNW model of a sale system between a customer and a company |
Fig. 2: | Packaging model of the sale system focusing on interactive messages |
This study supposes each private workflow can run normally itself. From the Fig. 1, it is easy to see that one private workflow`s receiving messages relate only to itself. While its sending messages involve the soundness of CPNWs. Thus, in CPNWs we only need to judge the following problem; if all private workflows can deal with their interactive messages successfully? In Fig. 2, private workflows` sending messages are represented by Light lines.
BASIC NOTATIONS AND ALGORITHM
To be understood easily, this study reviews some basic notations as follows (Van der Aalst, 2003).
Definition 1 (Petri net): A Petri net is a triple (P, T, F):
• | P is a finite set of places, |
• | T is a finite set of transitions (P∩T = Φ) |
• | F ⊆ (PxT) ∪ (TxP) is a set of arcs (flow relation) |
Given a Petri net (P, T, F) and a marking M1, we have the following notations:
: | Transition t is enabled in marking M1 and firing t in M1 results in marking M2 | |
: | There is a transition t such that | |
: | Firing a sequence σ = t1, t2, t3, .., tn-1 leads from marking M1 to marking Mn via a (possible empty) set of intermediate markings |
A marking Mn is called a marking reachable from M1 (notation ) if and only if there is a firing sequence such that . Note that an empty firing sequence is also allowed, i.e., .
We use (PN, M) to denote a PN with an initial marking M. A marking M` is a reachable marking of (PN, M) if and only if .
Definition 2 (Live): (PN, M) is live if and only if for every reachable marking M` and every transition t, there is a marking M" reachable from M` which enables t.
In Fig. 2, the two private workflows are packaged and we can only see the external interfaces (those transitions that interactive with other private workflows). The external interfaces have a sequential order based on direction of workflow (Van der Aalst, 2000). They are divided to two parts: Receiving Message Interfaces (RMI) and Sending Message Interfaces (SMI).
Suppose that a private workflow has a sending message j. We use PRE (j) to represent a pre-set of j. It is a subset of the messages received by the private workflow. That is, PRE (j) is a set of the messages sent by other private workflows. By means of the flow direction of the workflow, those messages must be received by the private workflow before it sends j. Before giving the definition of PRE (j), we introduce some based notations such as node subsequences, receiving messages sets and sending messages sets.
Definition 3 (Du et al., 2008) (Node subsequence): Let PN be a Petri net. A path C from the start node n1 to the end node nk is a sequence (n1, n2, ..., nk) such that (ni, ni+1) ε F for 1≤i≤k· and (C) is s set of nodes on the path C. nj is a subsequence of ni if and only if ∃ ni, ni+1, ..., nj ε and (C) and (ni, ni+1), (ni+1, ni+2), ...(nj-1, nj)εF.
Definition 4 (Receiving messages sets): Let PNW be a Petri net workflow. Receiving messages sets RECEIVEM (PNW) = {j | j is an interactive message received by PNW}. Sending messages sets SENDM(PNW) = {j | j is an interactive message send by PNW}.
We use PNWi to represent the ith private workflow. For example, in Fig. 2, RECEIVEM (PNW customer) = {offer, goods} and SENDM (PNW customer) = {refuse, order, money}.
Assume that there are m private workflows and they construct a CPNW via interacting messages. From definition 4, we have, ∪1≤i≤m RECEIVEM (PNWi) = ∪1≤i≤m SENDM(PNWi).
Based on definitions 3 and 4, PRE (j) is defined as follows.
Definition 5 (PRE (j)): Let PNW be a Petri net workflow. j is a sending message. The message j`ε PRE (j) if and only if:
• | j` ε RECEIVEM (PNW) and jεSENDM (PNW); and |
• | ∃ a path C, j`ε and (C), jε and (C) and j` j |
To judge if a CPNW is running normally, we need to define a set-Finish (CPNW). Finish(CPNW) is a subset of ∪1≤i≤m SENDM(PNWi). Herein, Finish (CPNW) contains all messages which can interact successfully in the CPNW.
Definition 6 (Finish(CPNW)): Let CPNW be an inter-organizational Petri net workflow. CPNW contain m private workflows: PNWi (1≤i≤m).
• | Finish(CPNW) ⊆c1≤i≤m SENDM (PNWi) |
• | ∀ message i ε∪1≤i≤m SENDM (PNWi); i ε Finish(CPNW) if and only if PRE(i) ⊆c1≤i≤m SENDM (PNWi) |
We give the algorithm below to get Finish (CPNW).
Algorithm 1 (Finish (CPNW) get algorithm): Steps : (Suppose a CPNW has m private workflows and k interactive messages)
• | For each private workflow i and each sending message j, get PREi (j) (PREi (j) represents the PRE (j) in the ith private workflow) |
• | The initial value of Finish(CPNW): For i(j) = Φ, jε Finish(CPNW) |
• | For ∀ 1≤i≤m, 1≤j≤k |
If ∃ PREi (j) ⊆ Finish(CPNW), Finish(CPNW) = Finish(CPNW)∪{j}, let PREi (j) = Φ, Return to (c);
Else Exit.
Here, we get Finish (CPNW) on the basis of algorithm 1. Finish (CPNW) contains all messages which can interact successfully in a CPNW.
From Algorithm 1, an interactive message can be sent when all needed interactive messages are received successfully. We search all messages needed by the ith private workflow before it sends message j. When all needed messages have been received by the ith private workflow, message j can be sent successfully. This study supposes that when message j be sent successfully, it can be received successfully. Namely, we ignore all failure during message be send out and received.
THE SOUNDNESS OF CPNW
A workflow net is sound if and only if the workflow net contains no dead parts (i.e., tasks that can never be executed), any reachable marking is always possible to terminate and in the moment of the workflow termination, all places except the sink place (i.e., place end) are empty (Van der Aalst, 2003a).
In the following, we analyze the soundness of CPNWs.
Definition 7 (Du et al., 2007): (Soundness) A CPNW is sound if and only if:
• | Each private workflow in the CPNW is sound and |
• | The CPNW is live |
We use PNWi (1≤i≤m) to represent the ith private workflow in a CPNW. From Algorithm 1, we can analyze the soundness of a CPNW. Here, we obtain a sufficient and necessary condition for deciding the soundness of a CPNW. Assume that a CPNW contains two private workflows.
In many practical systems, there are some resource competitions in CPNWs. For simplicity, we discuss the soundness of the CPNWs without resource competitions first.
Theorem 1: Let CPNW contain two private workflows: PNW1 and PNW2. CPNW is soundness if and only if:
• | Both PNW1 and PNW2 are sound and |
• | Finish (CPNW) = SENDM (PNW1) ∪SENDM (PNW2) |
Proof: Based on definition 7, we need only to prove that: CPNW is live if and only if Finish (CPNW) = SENDM (PNW1) ∪SENDM (PNW2).
(Sufficiency)Assume that PNW1 and PNW2 are live. If all interactive messages between PNW1 and PNW2 interact successfully, the CPNW is live. From the definition of Finish (), the messages in Finish () can interact successfully. They can be used by private workflows directly. Because RECEIVEM (PNW1) ∪RECEIVEM (PNW2) = SENDM (PNW1) ∪SENDM (PNW2). If Finish (CPNW) = SENDM (PNW1) ∪SENDM (PNW2), we get, RECEIVEM (PNW1) ⊆ Finish (CPNW). Namely, PNW1 need not to wait for interactive messages. PNW1 will not lead to deadlock. PNW2 can be analyzed similarly. Besides, since both PNW1 and PNW2 are live, CPNW is live.
Necessity: Let CPNW be live, but Finish (CPNW) ≠SENDM (PNW1) ∪SENDM(PNW2).
Based on Algorithm 1, we have Finish(CPNW) ⊆ ENDM(PNW1)∪ SENDM(PNW2). Suppose that an interactive message jεSENDM (PNW1) ∪SENDM (PNW2), but j∉ Finish (CPNW). It means that since some messages are lacking, the private workflow that produces message j cannot run smoothly. Because PNW1 and PNW2 are live, there is no lack of messages inside them. Thus, there is lack of interactive messages. We use the sign j` to represent the lacking message and j` ∉Finish(CPNW). From the definition of Finish (CPNW), message j` cannot interact successfully between PNW1 and PNW2. There is deadlock. Hence, CPNW is not live. This conclusion conflicts with the assumption. So, if one CPNW is live, Finish (CPNW) = SENDM (PNW1) ∪SENDM (PNW2).
In the following, by Fig. 1 we show the process of judging the soundness of CPNWs.
The steps of deciding the soundness of the CPNW in Fig. 1 are as follows:
• | From Fig. 2, RECEIVEM (PNWcustomer) = {offer, goods}; SENDM (PNWcustomer) = {refuse, order, money}; SENDM (PNWcompany) = {offer, goods}; RECEIVEM (PNWcompany) = {refuse, order, money} |
• | PRE (refuse) = {offer}; PRE (order) = {offer}; PRE (money) = {offer, goods}; PRE (offer) = Φ; PRE (goods) = {refuse, order} |
Based on Algorithm 1
• | Initial value: Finish(CPNW) = {offer{ |
• | After the first cycle: Finish(CPNW) = {offer, refuse, order} |
• | After the second cycle: Finish (CPNW) = {offer, refuse, order, goods} |
• | After the third cycle: Finish (CPNW) = {offer, refuse, order, goods, money}; at the same time, |
• | From (3), Finish (CPNW) = SENDM (PNWcustomer) ∪SENDM (PNWcompany). Namely, ∀j, PRE (j) = Φ |
Thus, the CPNW model in Fig. 1 is sound.
Corollary 1: Let CPNW contain m private workflows: PNWi (1≤i≤m). There are k interactive messages among these private workflows. CPNW is sound if and only if:
• | PNWi (1≤i≤m) is sound, and |
• | Finish (CPNW) = ∪1≤i≤m SENDM (PNWi) |
Proof: (It is similar to the proof of Theorem 1)
SOUNDNESS OF CPNW WITH RESOURCES COMPETITION
In order to use CPNW to model practical systems, in fact, we need to add resources competition to CPNW. In this study, we use Logic Petri Net (LPN) to model these systems (Du et al., 2008).
Notation LPNW represents a private workflow modeled by an LPN, while CLPNW is an inter-organizational system composed by some LPNWs.
Since the OR structure exists in a CLPNW, the analysis of the soundness in CLPNWs is different from that in CPNWs. It is uncertain if an LPNW can get the resources as there is resource competition in CLPNWs.
Therefore, we introduce some notations in the following. Firstly, the soundness and weak soundness of CLPNWs are defined.
The Resource Allocation in a CLPNW is uncertain. According to each way of Resource Allocation, we package the CLPNW. Thus, we get a group of CPNWs. The soundness of CLPNWs can be analyzed according as these CPNWs` soundness.
Corollary 2: Let CLPNW be an inter-organizational workflow composed by LPNW1-LPNWm. And there are m interactive messages among them. CLPNW is weak sound if and only if:
• | LPNWi (1≤i≤m) is sound; and |
• | ∃ a kind of Resource Allocation: Finish (CPNW) = ∪#I≤m SENDM(PNWi) and |
• | ∃ a kind of Resource Allocation: Finish (CPNW) ≠c1≤i≤m SENDM (PNWi) |
Corollary 3: Let CLPNW be an inter-organizational workflow composed by LPNW1-LPNWm and there are m interactive messages among them. CLPNW is sound if and only if:
• | LPNWi (1≤i≤m) is sound; and |
• | In all kinds of resource allocation |
Finish (CPNW) = ∪1≤i≤m SENDM (PNWi). |
If a CLPNW is weak soundness, we should develop some rules. In order to enable the system to run smoothly, all LPNW in this CLPNW must comply with the rules.
If a CLPNW is soundness, system has not restricted conditions. Namely, The CLPNW can be used without some rules.
CONCLUSION
In this study, we focus on the interactive messages existing in CPNWs. The main work contains:
• | The definitions of PRE (j) and Finish (CPNW) are introduced to analyze the soundness of CPNWs |
• | By Algorithm 1 and Theorem 1, we can decide the soundness of a CPNW |
• | Furthermore, Using these Corollaries 2 and 3, the soundness of CLPNWs can be analyzed |
In order to extending the application of PNs, the combination of PNs and the object-oriented technologies are used in the analysis of the soundness of CPNW. This study uses PNs to model an entity, i.e., a private workflow. By packaging private workflows, we investigate mainly their interactive messages and discuss how interactive messages influence the soundness of a CPNW.
In this study, we have discuss soundness of inter-organizational workflow. It plays a very important role in practical systems. When different companies cooperation on internet, they composed an inter-organizational workflow system. We judge this system and then get some rules to make system run smoothly. Thus, we can avoid interactive loopholes in system. Only different entities interact with their interactive messages successfully, the whole system can run smoothly.
The algorithm, theorem and Corollaries proposed in this study can be applied to the analysis of general PNs. Thus, we can discuss similarly the properties of combination PNs.
The future study is to further investigate the soundness of CLPNWs, to analyze the soundness of flexible workflows and to study the compound properties of PNs.
ACKNOWLEDGMENTS
This study is supported by the National Natural Science Foundation of China under Grant 60773034; the Taishan Scholar construction project of shandong province, China; the National Basic Research Program of China (973 Program) under Grants 2007CB316502 and 2004CB318001-03; the Open Project of the State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences under Grant SYSKF0804 and the Graduate Innovation fund of Shandong University of Sciences and Technology.
REFERENCES
- Van der Aalst, W.M.P., 1998. The application of Petri nets to workflow management. J. Circ. Syst. Comput., 8: 21-66.
CrossRefDirect Link - Van der Aalst, W.M.P., 2000. Loosely coupled interorganizational workflows: Modeling and analyzing workflows crossing organizational boundaries. Inform. Manage., 37: 67-75.
CrossRefDirect Link - Verbeek, H.M.W., A. Hirnschall and W.M. P. van der Aalst, 2002. XRL/Flower: Supporting inter-organizational workflows using xml/petri-net technology. Proceedings of the Web Services, E-Business and the Semantic Web, May 27-28, 2002, Toronto, Canada, pp: 93-108.
Direct Link - Van der Aalst, W.M.P., 2003. Inheritance of interorganizational workflows: How to agree to disagree without loosing control?. Inform.Technol. Manage., 4: 345-389.
CrossRefDirect Link - Du, Y.Y. and C.J. Jiang, 2008. On the design and temporal Petri net verification of grid commerce architecture. Chinese J. Electron., 17: 247-251.
Direct Link - Du, Y.Y., C.J. Jiang and M.C. Zhou, 2008. A petri-net-based correctness analysis of internet stock trading systems. IEEE Trans. Syst. Man Cybern. Part C: Appl. Rev., 38: 93-99.
CrossRefDirect Link - Du, Y.Y., C.J. Jiang and M.C. Zhou, 2007. Modeling and analysis of real-time cooperative systems using petri nets. IEEE Trans. Syst. Man Cybern. Part A: Part A: Syst. Hum., 37: 643-654.
CrossRefDirect Link - Prisecaru, O. and T. Jucan 2008. Interorganizational workflow nets: A petri net based approach for modelling and analyzing interorganizational workflows. Proceedings of the 4th International Workshop on Enterprise and Organizational Modeling and Simulation held in conjunction with the CAiSE'08 Conference, June 16-17, 2008, Montpellier, France, pp: 64-78.
Direct Link