=Paper= {{Paper |id=Vol-1591/paper12 |storemode=property |title=Distributed Change Region Detection in Dynamic Evolution of Fragmented Processes |pdfUrl=https://ceur-ws.org/Vol-1591/paper12.pdf |volume=Vol-1591 |authors=Ahana Pradhan,Rushikesh K. Joshi |dblpUrl=https://dblp.org/rec/conf/apn/PradhanJ16 }} ==Distributed Change Region Detection in Dynamic Evolution of Fragmented Processes== https://ceur-ws.org/Vol-1591/paper12.pdf

Distributed Change Region Detection in Dynamic
Evolution of Fragmented Processes

Ahana Pradhan and Rushikesh K. Joshi

Department of Computer Science and Engineering
Indian Institute of Technology Bombay,
Powai, Mumbai-400076, India.
Email:{ahana,rkj}@cse.iitb.ac.in

Abstract. Change regions approximate dynamic instance non- migrata-
bility 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 com-
putation 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.

Keywords: Change region, Distributed process evolution, Dynamic migration,
Fragmented processes, WF-nets

1 Introduction

Dynamic process migration approaches address the problem of adapting a run-
ning 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 [1]. Between
a pair of nets the problem is seen as instance to instance migration. In the do-
main of business processes, this problem is scaled up to a problem for a mass
of workflow instances, so that all active automated instances are evolved while
they are under execution in a workflow engine. Many theoretical approaches for
dynamic workflow evolution have been developed since the mid-nineties includ-
ing the approaches by Ellis et al. [2], Van der Aalst et al. [3] and Sun et al. [4].
Recent BPM solutions include support for process flexibility, as in YAWL [5]
and Aristaflow [6], which provide centralized approaches for dynamic migration.
Dynamic evolution is inevitable in an ever-changing business environment,
yet the technical support for the same is far from mature, especially for dis-
tributed processes. As pointed out by Protogeros et al. [7], due to non-solidified
154 PNSE’16 – Petri Nets and Software Engineering

protocols among the parties, problems such as indefinite waits, incorrect invoca-
tions, which are typical to distributed systems may result, in addition to incon-
sistency. Autonomous evolution of parties pose additional challenges of conflicts.
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. [8] point out that the root of the difficulty
in making changes in a distributed process is the fragmentation of the schema,
due to which, the global view of the process is lost. The change region based
approaches of (i) decentralized instance migration by Cicirelli et al. [9], and (ii)
dynamic evolution of fragmented workflow process by Hens et al. [10] adopt a
centralized process in the distributed setup. Therefore, a fully distributed ap-
proach of dynamic change remains to be theorized, which is the focus of our
paper. The difference between the algorithm presented in this paper and the
work of Hens et al. is that our algorithms compute the change region in a fully
distributed environment without needing the centralized change manager.
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 struc-
tural changes on other nodes. The change region is computed by making local
decisions and through communication of minimal information. Such a change re-
gion 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 cen-
tralized process schema (Section 3). Over a schema fragmentation model (Section
4), the centralized technique is adopted to develop and prove the distributed com-
putation 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 approx-
imation of non-migratability given a migration net pair. To elaborate, change re-
gion 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 re-
gions 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 [11] to eliminate the cost of instance-by-instance state-space
exploration by replacing it with one-time computation of change regions.
A. Pradhan and R.K. Joshi: Distributed Change Region Detection 155

Related Work on Change Regions: A preliminary notion of change region
was given by Ellis et al. [2] in their early work on dynamic workflow change.
Considering marking reachability as the consistency criteria, which is followed
in this paper, the notion of change region was introduced by Van der Aalst
[11]. The term dynamic change region was defined as the subnet in the old net,
which, when is completely unmarked in a marking, guarantees consistent state
transfer of that marking into the new net. Their work presented an algorithm to
identify the smallest single-entry-single-exit (SESE) block (sometimes referred
to as the minimal-SESE region) covering the structural changes performed on
the net as the change region. Several other approaches to compute the minimal-
SESE change region are found in the literature. Gao et al. [12] perform the same
objective on Special Net Structure (SNS) models. Sun et al. [4] present a variant
of the algorithm given by Van der Aalst [11] as an attempt to obtain a smaller
region. Zou et al. [13] use the process structure tree of workflow graphs [14] to
compute SESE change regions. In contrast, our approach does not require the
region to be a strict SESE-block, and hence is applicable to fragmented nets
where SESE-blocks may not even exist.

Related Work on Fragmented Process Migration: The recent literature
in distributed process migration uses the minimal-SESE regions originally pro-
posed for centralized workflows. Cicirelli et al. [9] adopt it for decentralized mi-
gration. Whereas distributed execution of different tasks at different physical
locations are permitted, a centralized view on the whole process is required in
their approach for computing the change region. Their mechanism facilitates in-
dependent migrations in the execution ends concurrent to each other, rather than
mandating the whole instance migration at once. The recent works of Hens et
al. [10], [15] apply the SESE approach to evolve fragmented processes, where the
change region is first computed on the global process. For applying the knowl-
edge of change region to migrate instances, a centralized change manager is
considered to coordinate among the fragments of the live instances. The change
manager constructs global state views of the running instances by collecting in-
formation from the live fragments, and then supervises the dynamic migration.
Summarily, these approaches consider independent migrations based on scatter-
ing of blocks in distributed environment, but do not compute the change region
through a fragmented schema devoid of a centralized view. The algorithm we
present considers distributed decision making in presence of fragmented schema.

2 The Foundations
Block-Structured WF-nets Application of Petri nets for workflow modeling
was introduced by Van der Aalst [16] through the class of Workflow nets, or
WF-nets. WF-nets are elementary nets, model control flow of workflow schemas,
whereas a marked WF-net models a workflow instance. A WF-net has a single
source place and a single sink place. A token only in the source place is the
initial marking and a token only in the sink place is the terminal marking. A
156 PNSE’16 – Petri Nets and Software Engineering

sound WF-net, once started with its initial marking, always reaches the terminal
marking, and does not have any dead intermediate state or dead transition.
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, con-
current blocks and iterative blocks. The blocks are sound by construction. The
following ECWS is a grammar built over a convenient “string” based representa-
tion 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 [17].

Net → Pnet loop → { Pnet } { Tnet }
Pnet → Place xor → [ Tnet ] [ Tnet ]
| Pnet Trans Place | [ Tnet ] xor
| Pnet Trans loop Trans Pnet and → ( Pnet ) ( Pnet )
| Pnet Trans and Trans Pnet | ( Pnet ) and
| Pnet xor Pnet Tnet → 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 concur-
rent 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}. Se-
quence 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 [11], [9],
[15]. The consistency criteria ensures that, an old workflow instance can carry on
to follow the new schema from its current state without having to encounter any
control-flow error till termination. In business terms, the question becomes, ‘can
the process migrate safely and correctly with same status, place labels reflecting
the status’. As an illustration, in some context of a technical conference process,
one can think of a state Paper Accepted as not migration equivalent to state
Paper Accepted, Author Registration Confirmed.

Fig. 1. Example of a Structured WF-net
A. Pradhan and R.K. Joshi: Distributed Change Region Detection 157

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 con-
sistent 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 cov-
ering 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
158 PNSE’16 – Petri Nets and Software Engineering

Algo. 1: Centralized Computation of Change Region
Input: C-trees C of N , C 0 of N 0
Output: Subsets CR and saf e of places in N w.r.t. N 0
0
1 CR1 ← places(C) − places(C )
0
2 CR2 ← places(root of C ) ∩ places(C except the root)
0
3 CR3 ← places(root of C) ∩ places(C except the root)
4 CR ← CR1 ∪ CR2 ∪ CR3
5 saf e ← places(root of C) − CR
6 while CR ∪ saf e 6= places(C) do
7 pick the next p from set places(C) − (CR ∪ saf e)
8 LCp ← places(GCS(p, C)) − places(GCS(p, C 0 ))
9 CR ← CR ∪ LCp
10 CBp ← {q|p, q co-occur in a node in both C and C 0 }
11 if root C-block in GCS(p, C) has less number of branches than root C-block
in GCS(p, C 0 ) then CR ← CR ∪ {p} ∪ CBp
12 else saf e ← saf e ∪ {p} ∪ CBp

not a process tree as in [18], since it captures only the nesting of concurrency.
Fig. 2 shows the C-tree of the ECWS-net given in Fig. 1. A marking can be
constructed from the C-tree by selecting one place from each node, by covering
all concurrent branches w.r.t. the node. For example, {p1 }, {p9 , p12 } are valid
markings, but {p11 , p16 } and {p1 , p16 } are not. Given a C-tree C and a place p in
it, GCS(p,C) is only the subtree in C that is concurrent to p and excluding p. For
example, GCS of p16 in Fig. 1 is shown in Fig. 2. Subtree GCS(p,C) is obtained
by removing from C-tree C those places in the entire ancestry and postgenitus
of place p that are not concurrent to p, including p. Thus, GCS retains only the
places which can be concurrently marked with p in a reachable marking.

3 Dynamic Migration of Centralized Workflows

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

Fig. 2. C-tree for the ECWS-net shown in Fig. 1
A. Pradhan and R.K. Joshi: Distributed Change Region Detection 159

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 con-
current 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
160 PNSE’16 – Petri Nets and Software Engineering

Table 1. All Cases of Non-migratable Markings

Case Structure of non- Structure of markings in Concurrency of p in New
No. migratable marking N 0 that overlap with M
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 non-
migratable, 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 The Model of Fragmentation for Distributed Schema
In a distributed environment, a workflow schema is assumed to be fragmented
among different execution nodes. No single end of execution has total knowl-
edge 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
A. Pradhan and R.K. Joshi: Distributed Change Region Detection 161

Fig. 3. Fragmentation Scheme

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 ap-
plication 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 post-
transition 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
162 PNSE’16 – Petri Nets and Software Engineering

Fig. 4. A Valid Fragmentation of Net in Fig. 1

Fig. 5. Fragmentation of C-tree corresponding to Fig. 4

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
S fragments in S the fragmentation
S together form the complete net -
P = f ∈R Pf , T = f ∈R Tf , F = f ∈R Ff ,
2. No two different fragments in the fragmentation share any transition: ∀f, f 0 ∈
R, f 6= f 0 , Tf ∩ Tf 0 = ∅.

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
A. Pradhan and R.K. Joshi: Distributed Change Region Detection 163

Fig. 6. BPMN process and its WF-net obtained by a BPMN to Petri net Mapping

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 collabo-
rative 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 [19], from
164 PNSE’16 – Petri Nets and Software Engineering

which we adopt a translation for basic primitives that are of interest to us as
shown in the figure. It can be noted that a BPMN activity is modeled as a
sequence of start transition, a place and an end transition, rather than as a
single transition, in order to bring it in the fold of place-based change regions.
When the corresponding place is a member of the change region, it implies that
the real-world BPMN activity is in the change region. In the figure, the respective
net elements that are not removed are shown in thin lines, deleted elements are
crossed, and additions are shown in think lines.

5 The Distributed Algorithm

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 respec-
tive 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 [20]. The algorithm proceeds in two
phases. The first phase uses three modules. It starts with initiation round (IR),
which implements a rendezvous among the fragments over change specifications.
Next, module ICBBN computes the local change region and shares its boundary
status (safe or unsafe) with peer fragments through event broadcasts. Incoming
boundary status from peers is concurrently handled through module RcvBN.
The second phase uses two modules. Here, the conflicts between local and peer
decisions are resolved iteratively, till termination condition is reached.

ICBBN ConflctR
Initial CR, Broadcast
Conflict Resolution
IR Boundary Notifications
Initiation Round
TermNtn
Receive Boundary Termination end
Notifications
RcvBN

Fig. 7. Phases of the Algorithm
A. Pradhan and R.K. Joshi: Distributed Change Region Detection 165

EVOLVE_ EBBM1 ........other k-2 EBBMk EVOLVE_
Broadcast_medium_1 broadcast mediums........ Broadcast_medium_k
color EVOLVE is
EVOLVE
(eid,c) EVOLVE (eid,c) INT x INT;

(eid,c) (eid,c) var eid: INT,
EVOLVE_ EVOLVE_ represents
substrate_1 substrate_k evolution id;
... to other
(eid,c)
notification ... to other var c: INT,
(eid,c)
buffers notification represents
buffers the number
of changing
fragments;
EVOLVE_ EVOLVE_ ........other EVOLVE_
Notification_buffer_1 Notification_buffer_2 k-3 notification Notification_buffer_k
ENB1 ENB2 buffers........ ENBk
EVOLVE EVOLVE EVOLVE

Fig. 8. CPN Model of the Substrate for EVOLVE event

Inter-Fragment Event Communication: Communication among the frag-
ments 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 com-
bination 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
166 PNSE’16 – Petri Nets and Software Engineering

EVOLVE_ enabled
Notification_buffer (n,x) ICBBN
PAIR [n=c,n>0]
ENB1 (ENB) INT
Out
c
EVOLVE 1 REN
(eid,c) c (n,c) Out
1`(0,0)
NewFrag
(n+1,c) enabled
f' NF
c FRAG RcvBN

INITIATE_ (f',eid,c) (eid,c) publish (eid,c) EVOLVE_
Notification_buffer Broadcast_medium
(eid,c) EVOLVE
(INB) (EBM)
EVOLVE EBBM1
EVOLVE
INITIATE

Fig. 9. Initiation Round (Module IR)

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 com-
putes 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 bound-
ary 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 ob-
served 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.

LocalCR PLACESET
s Boundary CR_B_
CR
intersect CRs Broadcast_medium
FRAG
1 s ShB crbset CRBBBM1
1`"yes" old PLACESET CR_B
fragment
publish CR_B
crset crbset
f
Out
enabled local (crset,safeset) ICBBN
ICBBN computeCR(f,f') result complete
In CRnSAFE safebset
f' publish SAFE_B
safeset
NewFrag new SAFE_B
safebset
fragment Boundary
SAFE SAFE_B_
FRAG s intersect SAFEs
LocalSafe Broadcast_medium
s ShB PLACESET
PLACESET SBBBM1

ShB is constant value, the list of boundary places in the old fragment.

Fig. 10. Initial CR, broadcast boundary notifications (Module ICBBN)
A. Pradhan and R.K. Joshi: Distributed Change Region Detection 167

intersect ShB (union s crbset) CRext

CR_ext PLACESET
CR_B_ crbset received s
1`[]
Notification_buffer CR_B 1
CRBNB1
(k-1)`() k is constant
CR_B value, the total
enabled RcvBN
Out number of
RcvBN complete
SAFE_B In participants
(k-1)`() in the algo

SAFE_B_ received s
1 1`[]
Notification_buffer safebset SAFE_B
SBNB1 SAFE_ext PLACESET
SFext
intersect ShB (union s safebset)

Fig. 11. Receive boundary notifications (Module RcvBN)

Receive boundary notifications (RcvBN): As shown in Fig. 11, set CR_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 CR_ext is updated. Similarly, set SAF E_ext stores and updates the
set of boundary places upon receiving SAFE_B notifications. Sets CR_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
(CR_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.

1 NOCC
NOCHANGE_ NOCBM1
1`[] INT
CRext counter NOCHANGE_
CR_ext 1`0
Broadcast_medium
1`0
1 x x+1
PLACESET
crx NOCHANGE Out
PLACESET
enabled 1`[] publish enabled
ConflctR NOCHANGE TermNtn
intersect
In crx sf
sf a
PLACESET
SAFE
LocalSafe rectifyCR(a) s intersect s ShB t publish
[not(a=[])] changed
CHANGE
PLACESET PLACESET
a s t

CBM1
a s PLACESET CHANGE_
PLACESET
Broadcast_medium

union crset (union a s) union safeset (union a s) CHANGE

crset safeset
LocalCR CR SAFE LocalSafe

PLACESET PLACESET

Fig. 12. Conflict Resolution (Module ConflctR)
168 PNSE’16 – Petri Nets and Software Engineering

aext CHANGE_ CNB1
Notification Notification_buffer CHANGE
Counter
(k-1)`() sf
recived
SAFE PLACESET
CHANGE LocalSafe
enabled choice of
TermNtn looping
crx union (intersect sf aext) crx
In Out
1
end
1`[] CR_ext PLACESET
CRext
[x