Change regions approximate dynamic instance non- migratability through schema based approach. In a distributed process, each node may have a partial view of the structure of the whole process. The distributed structure-fragments may evolve independently at runtime. Established centralized algorithms to compute change regions cannot be directly applied to such a scenario, due to absence of a centralized view. A fully distributed algorithm working on distributed fragments to solve this problem is presented. First, a new centralized change region computation algorithm is developed and proved correct as a basis for the distributed approach. The distributed algorithm is itself presented as a Hierarchical Colored Petri net. An application case is also illustrated.
Dynamic process migration approaches address the problem of adapting a
running workflow process instance of an old schema correctly to a new schema.
The instance after migration needs to be consistent. In the context of adaptive
systems, this problem is referred to as the state transfer problem [
Dynamic evolution is inevitable in an ever-changing business environment,
yet the technical support for the same is far from mature, especially for
distributed processes. As pointed out by Protogeros et al. [
The area of evolving distributed processes has been in focus quite recently
due to current trends of automation in the inter-organizational collaborative
processes. Recently Zaplata et al. [
However, the adaptation of such a theory in practice will need to face further challenges of many practical issues such as lack of consensus among different execution ends, contradictory independent changes, and unexpected delays in communication. Nevertheless, an algorithmic approach to evolve a fragmented process contributes a solution to the core of the bigger problem structure. The paper develops an algorithm for the distributed computation of the change region for a fully fragmented process schema of structured workflows. In this model, an execution node does not posses the knowledge of the full schema and the structural changes on other nodes. The change region is computed by making local decisions and through communication of minimal information. Such a change region determines migratability of the running instances, different parts of which may be live under different workflow engines in the distributed nodes.
In the paper, firstly, a formalization of the change region is presented for structured workflows, followed by the novel concept of conjoint tree (Section 2), which is used in formulating an algorithm for computing change region on centralized process schema (Section 3). Over a schema fragmentation model (Section 4), the centralized technique is adopted to develop and prove the distributed computation of change region (Sections 5 and 6 respectively). A practical example is also discussed to illustrate the applicability of approach.
Reason to use Change Regions: Change region provides a structural
approximation of non-migratability given a migration net pair. To elaborate, change
region is a region in the old schema, from where the old state cannot be transferred
into the new schema within the framework of the chosen consistency model.
When an instance state is outside such a region, its old state is a valid state in
the new schema, and hence, consistent migration is ensured. Thus, change
regions when known ahead of execution permit smooth maneuvering of transfer of
process control-flow into a new schema. This approach was formally introduced
by Van der Aalst [
Related Work on Fragmented Process Migration: The recent literature
in distributed process migration uses the minimal-SESE regions originally
proposed for centralized workflows. Cicirelli et al. [
Block-Structured WF-nets Application of Petri nets for workflow modeling
was introduced by Van der Aalst [
The scope of the work is characterized by ECWS-nets, a class of structured
WF-nets composed of the basic primitives of sequence, exclusive-choice,
concurrent blocks and iterative blocks. The blocks are sound by construction. The
following ECWS is a grammar built over a convenient “string” based
representation to ease specification and programming. More importantly, ECWS precisely
represents the class of nets targeted in the paper. ECWS includes place labels
and iterative blocks over the CWS language introduced in our earlier work [
Pnet → Place | Pnet Trans Place | Pnet Trans loop Trans Pnet | Pnet Trans and Trans Pnet | Pnet xor Pnet loop xor and
→ { Pnet } { Tnet } → [ Tnet ] [ Tnet ]
| [ Tnet ] xor → ( Pnet ) ( Pnet )
| ( Pnet ) and
Trans | Trans Pnet Trans
In the ECWS, the branches in an exclusive-choice blocks are enclosed in square
brackets such as in [A][B], whereas round brackets are used for enclosing
concurrent block such as in (A)(B), where A and B are ECWS subnets. A loop with
execution path A BA BA ... is expressed with curly brackets as {A}{B}.
Sequence of net-elements or blocks does not use spatial delimiters. As an example,
the ECWS specification for the net in Fig. 1 is specified in the figure itself.
Consistency Criteria and Instance Migratability An instance state is a
marking in the WF-net model of a given process schema. Migratability of an
instance determines whether the corresponding state of the old workflow is also
reachable in the new workflow. This state to state migration correspondence is
termed as the consistency criteria, which was used by earlier researchers [
A marking in the old net is non-migratable if it is unreachable in the new net from the corresponding initial marking. In this context, a change region is a schema based approximation of the non-migratability, i.e. any marking having a place in the change region is considered to be non-migratable.
In contrast with the SESE change regions discussed previously, we define the change region as a set of places instead of subnets with transitions included. This definition simplifies the collection in terms of places only without any loss of accuracy of the region. The transitions are thus overlooked for investigation of migratability, since marking reachability requires the knowledge of only the places. The definition of consistency and change region are as follows considering a WF-net as a tuple (P, T, F ) of sets of places, transitions and the arcs.
Let the old WF-net be N = (P, T, F ) and the new net be N 0 = (P 0, T 0, F 0) with the respective initial markings M0 and M00 , each consisting of only the source place of the respective nets of N and N 0. Also, let R(m) be the set of markings reachable from a marking m, where each marking is a set of places. Definition 1 Consistency: A marking M ⊆ P in the old WF-net N is consistent with a marking M 0 ⊆ P 0 in the new WF-net N 0 iff M = M 0. Definition 2 Migratability: A marking M is migratable iff M ∈ R(M0) and M ∈ R(M00 ). A non-migratable marking M is reachable in the old net but not in the new net, i.e., M ∈ R(M0) and M 6∈ R(M00 ).
Definition 3 Change Region: A subset of places in a given WF-net N defines the change region denoted by CR(N, N 0) for the old net N against a new WF-net N 0, if it covers all non-migratable markings. In other words, the change region includes at least one place from every non-migratable marking, i.e., M ∈ R(M0) and M 6∈ R(M00 ) ⇒ M ∩ CR(N, N 0) 6= ∅, i.e. non-migratable marking ⇒ place overlap with change region.
Following the definition, by taking contrapositive, we can observe that a marking in the old net that does not have a place in common with the change region is directly migratable. It can be noted that the above definition of change region permits overestimates since it permits a marking M to be part of change region and yet be reachable in the new net i.e., M ∩CR(N, N 0) 6= ∅ in the old net and M ∈ R(M00 ) in the new. Ease of computation is at the cost of overestimates. Conjoint Tree (C-tree), Generator of Concurrent Submarking (GCS):
A C-tree of a given net is a tree capturing concurrency of sets of places
covering the entire net. Consequently, it embeds all reachable markings. A node in
the tree holds places which are component of a sequential branch. The nested
structure of AND-blocks is captured through inner C-block elements (denoted
by symbol) in a parent node, pointing to child C-trees. One C-block points
to a single AND-block. Notably, places in XOR-blocks, loops and sequences do
not form a hierarchy on their own. Construction of the C-tree of a net can be
easily achieved from its ECWS specification. It can be noted that, a C-tree is
Algo. 1: Centralized Computation of Change Region
not a process tree as in [
The centralized algorithm (Algo. 1) works on the C-trees of the old and the new nets and produces the change region as a set of places. The algorithm is designed based on the principle that it is sufficient to include in the change region at least one place from every non-migratable marking. Intuitively, it works by finding and including five kinds of places in the change region listed below. C1: Places which are deleted from the old net (line 1) C2: Places which are concurrent in the old but not the new net (line 2) C3: Places which are concurrent in the new but not in the old net (line 3) C4: Places inside a concurrent block which lose their concurrency w.r.t. at least one place inside the same concurrent block (line 9) C5: Places inside a concurrent block that gain additional concurrency (line 11)
The algorithm to implement the above scheme is given in Listing Algo 1. It uses two functions places and GCS. Function places(n) returns the set of places present in the net structure n (which can be identified by a full C-tree, its subtree, or a GCS). In the algorithm, sets CR and Saf e are respectively used to contain the places inside and outside the change region. Line 4 builds up the initial set for CR following C1-3 by collecting the places which are either removed or which either gain or lose concurrency. Line 5 builds up the initial set Saf e collecting in it the places which are non-concurrent in both the nets.
The while loop iterates over all the unmarked nodes of the C-tree by picking the next place p (line 7) in each iteration. In each iteration, more than one places may be marked as members of either set CR or of set Saf e. The loop terminates when both the sets together cover the entire set of places (condition on line 6).
The loop continues to grow set CR by collecting the places which are concurrent relative to p in the old but not in the new net (lines 8,9). Set LCp gives the set of places of lost concurrency w.r.t. p. LCp is computed by subtracting from the set of places involved in the concurrent submarkings of p in the old net the set of places involved in non-concurrent submarkings in the new net (line 8). These are added into set CR (line 9).
Set CBp gives the set of places which are in the same concurrent branch (i.e. the same C-tree node) as p in both the nets, and have remained intact in the node with p after the structural changes from the old net to the new net (line 10). If p experiences an increased degree of concurrency by addition of a whole new branch in the concurrent block, p and CBp are included in set CR (line 11). Otherwise, p and the places in set CBp are marked as safe (line 12). It can be noted that, sets LCp and CBp are disjoint.
A case may arise where the root C-block in GCS(p,C) has same or more number of branches than that of the root C-block in GCS(p,C’) where p and CBp are involved in non-migratable markings due to local rearrangements or removal of places from the rest of the concurrent places. Both these cases are covered by inserting the responsible places into set CR on lines 1, 2 and 9. Thus, marking p and CBp as safe (line 12) optimizes set CR in such a case. Proof of Correctness: The correctness of the algorithm is proved by showing that its output set CR satisfies Def. 3 of change region. Assume the contrary, that there is a non-migratable marking of which not a single place belongs to set CR, i.e. ∃M ∈ R(M0), M ∩ CR = ∅, M 6∈ R(M00 ). If marking M is not migratable, it must satisfy one of the cases in Table 1. These are the exhaustive Case Structure No. migratable
M of non- Structure of markings in Concurrency of p in New marking N 0 that overlap with M (i) {p}: Non-concurrent no marking includes p Absent (p is deleted) (ii) {p, ...}: Concurrent no marking includes p Absent (p is deleted) (iii) {p}: Non-concurrent {p, ...}, but {p} not avail- Concurrent (p moves in able an AND-block) (iv) {p, ...}: Concurrent {p}, but {p, ...} not avail- Non-concurrent (p moves able out of AND-block) (v) {p, ...}: Concurrent {p, ...}, but same set not Concurrent (changes in available other branches) cases of non-migratability when seen through concurrency. The only case that it does not list is that of the combination non-concurrent × non-concurrent, which is migratable (line 5), since it is a case of a standalone place reachable in both.
It can be seen from the concurrency properties that for cases (i)-(iv), place p ∈ M is put in set CR by line 1-4 of the algorithm (C1-3), thereby leading to a contradiction. In case (v), as per the assumption, M has been declared nonmigratable, therefore an M 0 which includes the common member p must follow one of the three possibilities: (i) M 0 ⊂ M , (ii) M ⊂ M 0, (iii) M 0 is neither subset nor a superset of M but M ∩ M 0 6= ∅. It can be noted that the case M 0 = M is contrary to the assumption. In possibility (i) and (iii), M 0 misses at least one member q of M . Therefore, place q is concurrent with p in N , but is not so in N 0 though it may be present elsewhere in net N 0. Therefore, q must have been put in set CR by line 9 of Algo. 1 (C4), leading to a contradiction. Possibility (ii) implies an increased degree of concurrency for p. In other words, p requires at least one additional places to be marked along with along with it in the new net N 0. In line 11 of the algorithm, p is put in set CR since it has an increased number of concurrent branches in the GCS subtree of the new C-tree w.r.t. that of the old C-tree, thereby implying its increased degree of concurrency (C5), which leads to a contradiction. Hence the proof.
Cost of the Algorithm: The cost of our algorithm involves a series of set operations (lines 1-5), and a loop iterating over all places in worst case. Inside the iteration, a few set operations are involved. The complexity of the C-tree based change region algorithm is O(n2 log n) if n is the number of places. 4
In a distributed environment, a workflow schema is assumed to be fragmented among different execution nodes. No single end of execution has total knowledge of the process schema, i.e., no single participant possesses a global view of the workflow state at any point of time. Local changes to different fragmented schema result in evolutionary changes to the whole process schema. Due to the fragmented nature of the schema and this localization of changes, simple local application of the algorithm discussed previously is not sufficient. The distributed adaptation of the algorithm develops around a model of fragmented workflows and sharing of local change region information among the fragments.
A fragment is a connected subnet having places and not transitions in its boundary. In fragmentation, boundary places are shared among fragments which keep them connected. If a place in a fragment has more than one incoming or outgoing transitions, all of them are included in the fragment. As a fallout, the boundary places can also be from an inner part of a SESE-block in the fragment. However, the boundaries must be singleton places with exactly one incoming and exactly one outgoing transition in the global net. Consequently, the scheme allows for sequential, concurrent and nested fragmentation as shown in Fig. 3. A fragmentation partitions the net into a set of fragments. Using the WF-net notation given in Section 2, these two notions are formally defined next. Definition 4 Fragment: A fragment f of a ECWS-net N = (P, T, F ) is a net f = (Pf , Tf , Ff ) which adheres to the following properties. 1. A fragment is a subnet - Pf ⊆ P, Tf ⊆ T, Ff ⊆ F 2. The fragment subnet is a fully connected graph without local partitions. 3. A fragment includes all the pre-places and post-places of all its member transitions - ∀t ∈ Tf s. t. •t ∪ t• ⊆ Pf 4. Every input boundary place in a fragment must have exactly one pre-transition in the global net: ∀p ∈ Pf •p ∩ Tf = ∅ ⇒ | • p ∩ T | = 1 5. Every output boundary place in a fragment must have exactly one posttransition in the global net: ∀p ∈ Pf p • ∩Tf = ∅ ⇒ |p • ∩T | = 1 6. If a place in the fragment has multiple pre- or post-transitions, they belong to the same fragment - ∀p ∈ Pf , | • p| > 1 ⇒ •p ⊆ Tf , |p • | > 1 ⇒ p• ⊆ Tf .
A net is fragmented by creating multiple subnets such that when all the fragments are put together the original net is formed. Global source and sink are not boundary places. Fragments do not have common transitions. However, adjacent fragments need to have common boundary places to pass tokens around through fragments. The scheme can be applied to nets constructed by the ECWS grammar. Fig. 4 shows an example of a valid fragmentation of the net given in Fig. 1 in presence of a loop. The loop through place p9 spans two fragments. The direction of token flow through the six fragments of this process is also shown in the figure. Fragments may be located on different machines. The scheme of fragmentation prevents any overlap between two fragments apart from just the singleton boundary places as points of contacts.
Definition 5 Fragmentation: A fragmentation of a given ECWS-net N = (P, T, F ) is a set R = { |
f f = (Pf , Tf , Ff ) is a fragment of N }, such that it satisfies the following properties. 1. All the fragments in the fragmentation together form the complete net
P = Sf∈R Pf , T = Sf∈R Tf , F = Sf∈R Ff , 2. No two different fragments in the fragmentation share any transition: ∀f, f 0 ∈ R, f 6= f 0, Tf ∩ Tf0 = ∅.
Fig. 5 shows the corresponding fragmentation of the global C-tree showing six fragmented C-trees. Only the tree nodes get partitioned into different fragments, and the C-blocks preserve the cardinality of their branching which is due to condition 3 of Def. 4 that makes it mandatory for all forking/joining element to hold all its forked/joined branches together. In other words, a C-block element may repeat in multiple partitions, but the branches of a C-block cannot be partitioned and at least one place must be present in every partition.
Though the C-trees of each of the fragments in the example are formed from the global C-tree, they can be constructed from the respective fragments independently. It can be noted here that a fragment is a subnet but may not be a complete WF-net by itself, as it can be observed in the case of fragments f1 to f6 in Fig. 4. When a local structural change is made to a fragment, it assumes that the change does not violate global well-formedness of ECWS structure and the local C-tree is available. The local C-trees can be constructed by adapting the C-tree construction of Section 2.
Practical Example of Fragmentation: Fig. 6 shows a distributed collaborative BPMN employee transfer process fragmented at five locations. When an employee is transferred from one administrative unit to another, this process is executed. The fragments correspond to five pools operated by five actors: ( f1) Exiting Section, (f2) Accounts department, (f3) Service records, (f4) Employee, and (f5) Reporting Section. Clearly, none of the fragments has the global view of the process. This process has now changed. In the new process, fragments Accounts (f2) and Reporting Section (f5) have changed their internal structure.
The fragmented ECWS-net model of the process is also depicted in the figure.
Translation from BPMN to Petri net is a widely researched area [
Schema Change Specification: Independent schema change specifications are given per fragment. Thus, individually they are local. They are together assumed to preserve the well-formedness of the global net. C-trees of the respective fragments are available locally. Once a place is assigned into a fragment, the change specification does not move it to another fragment. In other words, if a place is absent in a fragment after a structural change, it cannot be found in any other fragment, which makes it a deleted place. As a consequence, a boundary place in a fragment can not become an internal place in that fragment, since it would lead to removal of that place from the peer fragment that shares it. The algorithm uses the the following symbols: f is the old local fragment, f 0 represents the new fragment after the local structural change. If no change is performed on f , the value of f 0 is considered to be null.
A High-level Overview of the Algorithm: The algorithm is depicted as
a Hierarchical Colored Petri net in Fig. 7. This and the rest of the models
have been constructed using CPN Tools [
IR Initiation Round
ICBBN Initial CR, Broadcast Boundary Notifications
Receive Boundary
Notifications
RcvBN
ConflctR Conflict Resolution
TermNtn Termination end
Fig. 7. Phases of the Algorithm ........other k-2 broadcast mediums........
EBBMk EVOLVE_
Broadcast_medium_k EVOLVE Inter-Fragment Event Communication: Communication among the fragments is through a lossless publish-subscribe event-substrate. Between a pair of fragments event-messages are ordered. Every action in the algorithm logic is guarded by either the occurrence of an event or by a precondition, or by a combination of both. One instance of the algorithm runs on one fragment and this bundle is called a Logical execution node. Number k, the total number of logical execution nodes in the environment is known to every logical execution node. However, it is possible to combine multiple logical execution nodes on a single physical machine, which is a non-algorithmic deployment issue.
Each event type is assigned a color declaration. There are five event types, which are EVOLVE, CR_B, SAFE_B, CHANGE and NOCHANGE. Fig. 8 depicts the CPN model of the part of the substrate covering the connections for one event type EVOLVE. The substrate makes these connections for each event type. The event is published at place broadcast medium, and after the broadcast through the substrate, it is received at place notification buffer in a peer fragment. The bound variables on the arc inscriptions carry the parameters of the events. The substrate is thus a simple value passing CPN implementing point-to-point broadcast. Initiation Round (IR): As shown in Fig. 9, the initial round implements a rendezvous to bring every node into the change region computation. The round is initiated by all fragments where change is required. A structural change request arrives from some external user to every changing fragment in the form of event INITIATE in place INB. A change request carries (i) f 0 the new fragment, which is stored in place NF, (ii) count c of the number of fragments which are changing in this round of evolution, and (iii) eid, a global evolution id, which is an unused provision for withholding the next evolution till the current one completes.
A node receiving INITIATE publishes in place EBM a broadcast of EVOLVE carrying only the eid and count c. This broadcast brings about the involvement of non-changing fragments into the change region computation. In place ENB, every changing and non-changing fragment receives from peers a total of c − 1
EVOLVE_ Notification_buffer ENB1 (ENB) EVOLVE (eid,c)
c NotifIiNcaITtiIoAnT_Eb_uffer (f',eid,c)
(INB) INITIATE
INT c
c (eid,c) (n,x) PAIR
[n=c,n>0] (n+1,c) EVOLVE and c EVOLVE tokens respectively. Fig. 9 implements the common IR module unifying the rendezvous logic of both types of participants. The rendezvous is achieved in place REN when a total of c notifications are received. The value c is known only when the first notification arrives either from ENB or INB. Initial CR, broadcast boundary notifications (ICBBN): As shown in Fig. 10, after the rendezvous, every fragment computes its local change region by applying function computeCR (which uses Algo. 1) given in Table 2 on inputs f and f 0 (old and new fragments). It produces a local result CR × SAF E (color CRnSAF E). From here, one branch computes local set CR and the other computes local set SAF E. After computing CR, the boundary places in local CR are identified as intersection of places in CR, and ShB, the known set of boundary places. The boundary places in CR and SAF E are published through events CR_B and SAFE_B respectively, after which this module completes. It can be observed from the figure that the net puts tokens from CR (unsafe) and SAF E back into their respective places since they are needed later in the algorithm. enabled ICBBN
In 1`"yes"
FRAG old 1 fragment f
Fig. 10. Initial CR, broadcast boundary notifications (Module ICBBN) intersect ShB (union s crbset) intersect ShB (union s safebset) Receive boundary notifications (RcvBN): As shown in Fig. 11, set C R_ext stores the set of boundary places which are announced to be unsafe by peers. Whenever a set of unsafe boundary places is notified through the notification buffer, set C R_ext is updated. Similarly, set SAF E_ext stores and updates the set of boundary places upon receiving SAFE_B notifications. Sets C R_ext and SAF E_ext are used later. This module completes after it receives and processes notifications about safe and unsafe boundaries from each of k − 1 peer fragments. Conflict Resolution (ConflctR): The module is shown in Fig. 12. When this round is enabled, intersection of local safe (SAF E) and external unsafe (C R_ext) is computed. If this result is nil (arc 1`[ ]), event NOCHANGE is published and a no change count is incremented (NOCHANGE counter), else the result (conflict set) is bound to variable a.
enabled ConflctR In
1`[] CRext CR_ext 1
SAFE LocalSafe crx sf
PLACESET intersect crx sf PLACESET [not(a=[])] PLACESET
PLACESET a a
NOCBM1
NOCHANGE_ Broadcast_medium NOCHANGE PLACESET
Out enabled TermNtn publish CHANGE
t CBM1 CHANGE_ Broadcast_medium
CHANGE 1 NOCC INT NOCHANGE_ counter 1`0 x x+1
1`0
publish
NOCHANGE rectifyCR(a) s intersect s ShB
t changed PLACESET
s a s
PLACESET union crset (union a s)
union safeset (union a s) crset safeset
Fig. 12. Conflict Resolution (Module ConflctR ) In enabled TermNtn enabled ConflctR
Out CBp ← { q | q ∈ Saf e, p ∈ Conf lict_set, q co-occur with p either in the same node or in a descender node in both C-trees of f and f 0} return CBp;
As a result of the conflict, some additional locally safe places may become unsafe, which are bound to variable s after they are identified by function rectifyCR. Boundary places in set s are published through event CHANGE. CR and SAF E are recomputed using their previous values and a and s. The C-tree based algorithm of function rectifyCR is shown in Table 2, which has been detailed in the proof given in the next section.
Termination (TermNtn): Fig. 13 shows the corresponding CPN model. After CHANGE or NOCHANGE broadcast, the fragment waits for similar event notifications from every other node. If the node has broadcast NOCHANGE due to no conflict in the previous module and received k − 1 NOCHANGE notifications (value 1` k in NOCHANGE counter), the termination condition is reached. Otherwise, set CR_ext is updated with the parameter places of CHANGE notifications and the conflict resolution phase is again re-triggered. Place Notification counter in the net keeps track of total number of CHANGE and NOCHANGE notifications received in one round. Place choice of looping provides an exclusive choice between termination of the algorithm and pursuing the conflict resolution round again. Cost: The initiation round results in c broadcasts. After local computation of CR, the initial sharing of place status results in 2k broadcasts. The conflict resolution phase involves k broadcasts in each round, with at most s rounds, where s is the number of safe boundary places judged locally by computeCRs.
Lemma 1 proves that place deletion does not cause a conflict. Lemma 2 proves that change in concurrency is detected at least in one fragment. Due to fragmentation, the change in concurrency may not be visible in all the affected fragments due to lack of knowledge of the global GCS. If a fragment, locally safe, has changed concurrency globally, at least one of its boundary comes to know about the change through status notifications from sharing fragments if the boundary in the peer fragment is able to detect the change by local GCS. This gives a case of conflict in the fragment which is not able to see the global GCS, which causes the fragment to call procedure rectifyCR. This procedure includes the locally safe boundary in CR. Since the reason of conflict is known to be change in concurrency only, the places in the same AND-branch (same or deeper nesting) also gets affected in the same way as the boundary. Therefore, rectifyCR puts all of them in CR. Any newly unsafe boundary has to propagate this rectification in the same manner until all non-migratabilities get covered by this branch. Conflict resolution messages are propagated from one fragment to another until the conflict stabilizes.
Lemma 1 The effect of deletion of a place in the change region in a fragment is fully covered by the fragment in which the place is deleted.
Proof: If the deleted place is not shared between two fragments, it is inserted in the change region of only its container fragment by procedure computeCR which directly uses Algo. 1 on the fragment and its new replacement. If the deleted place is a boundary shared between two fragments, it is inserted into the change region by both the fragments by procedure computeCR. It is assumed that the new f 0s corresponding to the two fragments remain consistent in deleting the globally deleted place. Further, a boundary place does not become an internal place as per the assumptions. Consequently, deletion of a place in a fragment does not create a conflict with the change region locally identified by some other fragment. The lemma covers cases (i) and (ii) in Table 1.
Lemma 2 If there is any change in concurrency of a place in the global net, some fragment detects it.
Proof: The cases of change in concurrency are the three cases (iii), (iv), (v) in Table 1. We need to prove that a change in GCS of the place p in contention is locally detectable by at least one fragment in all these cases.
In case (iii), the global gained concurrency of p can happen by either by adding new concurrent branches and gateways around p, or by moving p in an existing AND-block globally. In the former sub-case, an existing transition t1 upstream to p with its only post-place q (which can also be p) is expanded with additional post-places. Similarly, downstream transition t2 with its only preplace q0 (which can also be p) additionally joins with new pre-place. As per the fragmentation property 3 of Def. 4, since a transition cannot be a boundary, t1, q and the new fork-places are co-located, and t2, q0 and the new join-places are co-located. So the respective fragments detect the change in concurrency for q and q0 in computeCR after the initial rendezvous. This is because the procedure generates a non-empty GCS for q and q0 in both their host fragments, though p may be located in those fragments (lines 11-12 of Algo. 1).
In the latter sub-case, a part of the the AND-block in reference must be in the same fragment as that of p since none of them can move out. Also, for p to move in the AND-block, either the fork or the join gateway of this AND-block must be in the same fragment, else the fragment becomes disconnected. Due to the existence of a concurrent gateway, computeCR creates a local non-empty GCS for p, which detects the gained concurrency (lines 11-12 of Algo. 1)
The argument for case (iv) is exactly a reverse one with the sub-cases of removal of AND-branches which need not be located in the same fragment, or by a movement of p out of an AND-block somewhere in a sequence without an enclosing AND-block in the same fragment. In this case, with the reverse argument for its both sub-cases, the procedure computeCR detects the loss of concurrency by observing differences in the GCS (lines 8-9 of Algo. 1).
Case (v) occurs when (a) p moves in an existing inner AND-block or an existing outer AND-block or jumps into another branch of the same block, or (b) the AND-block in which p occurs is modified by either removal or addition of branches anywhere in the nesting but by maintaining p to be concurrent. Thus we get two sub-cases. In the first sub-case, the part of the AND-block where p is moving to is in the same fragment as that of p. Hence, one of the fork and join gateways that p crosses must be in the fragment to keep the fragment connected, leading to detection of the change. In the second case, fragments containing either of fork or join gateways detect deletion and addition of branches. Bounded Wait: Every broadcast is non-blocking. It is released immediately after the resource is generated. Asynchronous event communication is assumed to be handled by the substrate. Every event token is consumed in the respective modules in bounded time. Therefore, a cyclic deadlock through multiple nodes involving a broadcast and wait for notification does not arise. Also, the conflict resolution loop eventually terminates as discussed below.
Termination: Let the initial global change region be CRglobal = Sik=1 CRi, where CRi and SAF Ei are sets CR and SAF E computed by computeCR in ith fragment. The conflict resolution phase in node i either grows set CRi by adding places through rectifyCR or keeps it the same. Therefore, set CRglobal monotonically increases in every round till stabilizes (becomes non-increasing) in all fragments, when we know that the termination is reached. In other words, SAF Ei is monotonically decreasing. At least one node broadcasts CHANGE in each round prior to the termination round. Since set SAF Ei monotonically decreases, after a finite number of rounds there is no change in all nodes, at termination. A Trace of the Algorithm: The above algorithm has been simulated in CPN tools on the example provided in Fig. 6. Currently, we have separate implementation of the local functions given in Table 2 in Java, which are not integrated with the CPN models. We have used results obtained from these functions as return results of functions computeCR and rectifyCR used in the CPN models that appear as arc inscriptions. In addition to the initial markings shown in the respective module nets, place old fragment (module ICBBN) in the non-changing fragments require initial marking “null” to run the simulation.
For the given net, fragments f2 and f5 are initiator participants, fragments f1, f3 and f4 are participants in which nothing changes. In f2, non-concurrent places p6, p8, T S, p7 become concurrent. In f5, places p10 and p28 gain additional concurrency. Hence, all of them are put in the change regions of their respective host fragments. Initially, f3 has all its places locally safe. However, according to boundary status received from f2 and f5, it obtains conflict set {p8, p10}, then puts all its places in the change region by rectifyCR, and publishes CHANGE event with empty list as parameter. Every fragment therefore proceeds to another round of conflict resolution, where each of them finds no conflict. As a result, the algorithm requires two rounds of the second phase loop before termination. The final change region is depicted with shaded backgrounds in Fig. 6. 7
The paper presents a fully distributed algorithm to compute change region for fragmented processes in a dynamic evolution context. The algorithm works on structured WF-net models specified by the ECWS language. First, a distributionfriendly centralized approach to compute of change region was developed, and it was later fragmented to work in a fully distributed environment. The change region is seen as a set of places instead of the traditional connected subnet. This view enabled the distributed algorithm to use a strategy based on asynchronous status exchange. The distributed algorithm comprises three stages of initiation, basic local CR computation, and exchange of status of boundaries for adjustments to local change region till termination. The algorithm computes change region through fragmented processes without using node ids, and without requiring a centralized change manager, in contrast to the existing approaches for distributed processes. The algorithm was presented as a Hierarchical Colored Petri net, which is instantiated by every fragment. The applicability of the approach was highlighted through a fragmented BPMN collaborative process. The fragmentation rules are flexible enough for SESE-blocks to be fragmented. The approach may further be continued towards development and extensions such as places jumping between nodes, optimization of the static change region, integration of a distributed dynamic instance migration protocol possibly through a horizontal (concurrent) approach, optimization of messaging rounds without relaxing the condition of non-disclosure of the identities, and an algebraic proof that works on independent fragments to produce a result equivalent to the centralized computation albeit with certain overestimates.