Change Propagation
in Collaborative Processes Scenarios
Walid Fdhila, Stefanie Rinderle-Ma
University of Vienna, Austria,
Faculty of Computer Science
{walid.fdhila, stefanie.rinderle-ma}@univie.ac.at
Manfred Reichert
University of Ulm, Germany,
Institute of Databases and Information Systems
Abstract—Process flexibility and change constitute major chal-
lenges for process-aware information systems. This does not only
hold for centralized process scenarios, but also for collaborative
ones involving multiple distributed and autonomous partners.
If one partner adapts its private process, the applied change
might affect the processes of the other partners as well. Hence
the change must be propagated to concerned partners in a
transitive way. A fundamental challenge is then to find ways
of propagating the changes in a decentralized manner. Existing
approaches dealing with changes of collaborative processes are
limited with respect to the change operations considered and
their dependency on certain process specification languages.
By contrast, this paper presents a generic change propagation
approach based on the Refined Process Structure Tree. Our
approach is applicable independently of a particular process
specification language. Further, it considers a comprehensive set
of change patterns. Finally, it is shown that the provided change
propagation algorithms preserve structural dependencies for any
change pattern.
I. INTRODUCTION
Process flexibility and change have been identified as major
challenges in process management research for more than a
decade [1], [2], [3]. Driving forces necessitating the adap-
tation and evolution of implemented processes include, for
example, changes in law, exceptional situations, and process
optimization. Change support is not only crucial for centralized
processes (i.e., processes running entirely within one organi-
zation), but also for collaborative process scenarios involving
multiple partners [4]. Typically, these partners run their own
private processes and provide public views on them (i.e.,
local choreography models) to partners. Based on these public
views, a global choreography can be formed by exchanging
messages in a controlled manner in order achieve some
common goal. A characteristic example of a collaborative
processes is a supply chain consisting of the three partners
customer,producer, and supplier [4]. Based on their internal
or private processes, these partners provide local choreography
models to the outside communicating through interactions.
Centralized processes pose many challenges when changes
have to be applied to them. Existing approaches have focused
on aspects such as correctness of change [2], change reuse
The work presented in this paper has been conducted within the project
I743 funded by the Austrian Science Fund (FWF) and by the Deutsche
Forschungsgemeinschaft (DFG).
[5], and performance [6]. The same challenges hold for col-
laborative process scenarios. In fact, changes of collaborative
processes are by far more difficult to handle due to the
non-availability of the information required to perform, for
example, correctness checks. Specifically due to the absence of
a central coordinator, such as assumed in previous work [7], in-
formation on the partners’ private processes is not available to
others aggravating the correct application of process changes.
For example, assume a collaborative supply chain scenario
as outlined above. Let further a change become necessary
at the supplier’s side due an emerging internal policy and
assume that an additional notification message is required
from the producer and - in the sequel - from the customer.
This change would be first applied to the supplier’s internal
process. However, since the change affects both partners, it
has to be propagated to the respective partner processes as
well. In turn, this change propagation raises challenging issues:
(a) Which information must be propagated to partners? (b)
How to adapt the local choreographies in order to comply
with the change? (c) How to adapt the partners’ private
processes? (d) How to maintain correctness and consistency of
the global choreography as well as compatibility of the local
choreography models among each other?
So far, only few approaches have addressed these challenges
[4]. All these approaches are restricted with respect to the
formal specification language used and the set of change
operations considered. Furthermore, only the effects on direct
partners have been investigated so far, factoring out issues such
as transitive changes as well as issues related to the compatibil-
ity of the local choreography models as well as the consistency
of the global choreography after change propagation. In this
paper, we tackle change propagation in collaborative process
scenarios in a more holistic way. First of all, we base our con-
siderations on the Refined Process Structure Tree (RPST) [9].
RPST provides a process representation that is independent of
any specific process specification language on the one side and
enables us to formally specify and propagate changes on the
other side. Regarding process changes, we investigated well-
known process change patterns [10] and provide propagation
algorithms for the most common change operations such
as insert, delete or replace process fragments, and – at a
more semantic level – update of, for example, input/output
parameters. All considered change patterns operate on process
Book Trip Operation
book reserve
Traveler
TravelAgency
check and cash
TravelAgency
Acquirer
notificate failure
Acquirer
TravelAgency
notification failure
Acquirer
Airline
notificate failure
Acquirer
TravelAgency
credit card not
approved
TravelAgency
Traveler
ticket purshase
cancelled
Airline
Traveler
approval
Acquirer
TravelAgency
ticket
Airline
TravelAgency
payment ok
Acquirer
Airline
total value
TravelAgency
Traveler
Pu r c h a s e c o n f i r m a t i o n
Airline
TravelAgency
Fail
Ok
walidus fd 1 of 1 07.05.2012
Fig. 2. Global Choreography: Book Trip Operation []
collaboration
Traveler
book
reserve
credit card
not
app roved
total
value
ticket
purshase
cancelled
Travel Agency
book
reserve
total
value
check
and cash
ticket
app roval
notification
failure
credit card
not approved
Pu r s h as e
confirm ation
Airline
payment
ok
ticket
notification
failure
ticket
purchase
cancelled
Pu r s h as e
confirm ation
Acquirer
check
and cash
notification
failure
payment
ok
notification
failure
app roval
walidus fd 1 of 1 08.05.2012
Fig. 3. Book Trip Operation: Local Views
Book Trip Operation
book reserve
Traveler
TravelAgency
check and cash
TravelAgency
Acquirer
notificate failure
Acquirer
TravelAgency
notification failure
Acquirer
Airline
notificate failure
Acquirer
TravelAgency
credit card not
app roved
TravelAgency
Traveler
ticket purshase
cancelled
Airline
Traveler
app roval
Acquirer
TravelAgency
ticket
Airline
TravelAgency
payment ok
Acquirer
Airline
total value
TravelAgency
Traveler
Pu r c h a s e c o n f i r m a t i o n
Airline
TravelAgency
Fai l
Ok
walidus fd 1 of 1 07.05.2012
Fig. 2. Global Choreography: Book Trip Operation []
collaboration
Traveler
book
reserve
credit card
not
app roved
total
value
ticket
purshase
cancelled
Travel Agency
book
reserve
total
value
check
and cash
ticket
app roval
notification
failure
credit card
not approved
Pu r s h as e
confirmation
Airline
payment
ok
ticket
notification
failure
ticket
purchase
cancelled
Pu r s h as e
confirmation
Acquirer
check
and cash
notification
failure
payment
ok
notification
failure
app roval
walidus fd 1 of 1 08.05.2012
Fig. 3. Book Trip Operation: Local Views
AND-split/join
interaction
Chor eog rap h y t ask
Se n d er
Re ce i ve r
walid fdhila 1 of 1 08.08.2012
Book Trip Operation.bpmn
book reserve
Traveler
TravelAgency
check and cash
TravelAgency
Acquirer
payment ok
Acquirer
Airline
ticket
Airline
TravelAgency
Pu r c h a se co n f i r m a t i o n
Airline
TravelAgency
approval
Acquirer
TravelAgency
total value
TravelAgency
Traveler
credit card not
approved
TravelAgency
Traveler
ticket purshase
cancelled
Airline
Traveler
Airline failure
notification
Acquirer
Airline
TravelAgency failure
notification
Acquirer
TravelAgency
Ok
Fail
walid fdhila 1 of 1 07.08.2012
Book Trip Operation.bpmn
book reserve
Traveler
TravelAgency
check and cash
TravelAgency
Acquirer
payment ok
Acquirer
Airline
ticket
Airline
TravelAgency
Pu r c h a se co n f i r m a t i o n
Airline
TravelAgency
approval
Acquirer
TravelAgency
total value
TravelAgency
Traveler
credit card not
approved
TravelAgency
Traveler
ticket purshase
cancelled
Airline
Traveler
Airline failure
notification
Acquirer
Airline
TravelAgency failure
notification
Acquirer
TravelAgency
Ok
Fail
walid fdhila 1 of 1 07.08.2012
XOR-split/join Message received Message sent Interaction
Book Trip Operation.bpmn
book reserve
Traveler
TravelAgency
check and cash
TravelAgency
Acquirer
payment ok
Acquirer
Airline
ticket
Airline
TravelAgency
Pu r c h a se co n f i r m a t i o n
Airline
TravelAgency
approval
Acquirer
TravelAgency
total value
TravelAgency
Traveler
credit card not
approved
TravelAgency
Traveler
ticket purshase
cancelled
Airline
Traveler
Airline failure
notification
Acquirer
Airline
TravelAgency failure
notification
Acquirer
TravelAgency
Ok
Fail
walid fdhila 1 of 1 07.08.2012
Fig. 1. Global Choreography: Book Trip Operation [8]
fragments. The associated propagation algorithms are formally
defined and illustrated based on a use case. Furthermore, we
show that the change propagation results in compatible local
choreography models as well as a consistent global chore-
ography. Finally, we sketch the transition from the structural
considerations provided in this paper to semantic issues and
future challenges.
In Sect. 2 the problem space is introduced, followed by
fundamental definitions in Section 3. Section 4 provides the
change propagation algorithms. Our approach is evaluated in
Section 5. In Section 6 we discuss related work and Section
7 summarizes the paper.
II. MOTIVATION AND CHALLENGES
We illustrate change propagation issues along the booking
trip choreography example depicted in Figure 1. This example
is part of the choreography model described in [8]. It is mod-
eled in BPMN 2.0 and describes a collaboration between four
partners, i.e., traveler,travel agency,acquirer, and airline. The
traveler sends booking information to the travel agency which,
in turn, contacts the acquirer to request a credit check. If the
traveler has not enough credit, failure notifications are sent
to the travel agency and the airline partners which inform
the traveler about the reservation failure and the purchase
cancellation respectively. Otherwise, an approval is sent to the
travel agency and the airline is triggered to send the ticket
and the purchase confirmation.
Figure 2 depicts the public views (i.e., local choreography
models) of all participants involved in the choreography. Each
partner view includes only the interactions in which this
partner is involved as well as the control flow between them.
Figure 2 does not show the private view (i.e., orchestration) of
each partner that includes the internal activities. These local
views merged together lead to the global choreography model.
Now assume that partner acquirer wants to change the logic
of its private process. For instance, instead of sending two
failure notifications to airline and travel agency respectively,
he notifies only one of them. In Figure 2, fragment Fis
replaced by fragment F0 (XOR instead of AND). Then, for
some process instances, partner airline would wait indefinitely
for a failure notification if the acquirer chooses to send a
notification only to the travel agency. In this case, the acquirer
process instance would be blocked in this state and not ter-
minate. Hence, the described change affects the soundness of
the choreography model in terms of compatibility between the
distributed public views. To overcome this problem, the effects
of this local change in the acquirer process model should
be propagated to the concerned partners and the interactions
should be restructured consequently.
Generally, the challenges are as follows: How to compute
the impacts of this local change on the other partners and the
global choreography? How to propagate the effects of the local
change while preserving the soundness of the collaboration in
terms of consistency and compatibility [11]? How to deal with
transitive effects of changes? What if changes are made dy-
namically, i.e. during the execution of choreography instances?
How to manage the different versions of the choreography
model (used in monitoring) and the participants’ processes at
runtime?
III. PRELIMINARIES
As emphasized, this paper deals with change propagation in
collaborative processes. In practice, there are three different,
but overlapping viewpoints in a collaboration: orchestration,
behavioral interface, and choreography [12]. An orchestration
describes the internal business logic of private processes as
well as the communication actions in which a particular
partner engages. The behavioral interface (also called public
view or local choreography model) sketches the message
exchanges from the perspective of a single partner as well as
the sequencing between them. In other words, it represents
an abstraction of an orchestration’s internal actions. The
choreography (also called global model) gives a global
view of all interactions in the collaboration. It captures the
interactions in which the participating partners engage to
achieve a goal as well as the dependencies between these
interactions. In order to precisely define the notions of
orchestration, behavioral interface and choreography, we
collaboration
Traveler
book
reserve
credit card
not
approved
total
value
ticket
purshase
cancelled
Travel Agency
book
reserve
total
value
check
and cash
ticket
approval
TravelAgency
notification
failure
credit card
not approved
Pu r s h ase
confirmation
Airline
payment
ok
ticket
Airline
notification
failure
ticket
purchase
cancelled
Pu r s h ase
confirmation
Acquirer
check
and cash
payment
ok
approval
TravelAgency
notification
failure
Airline
notification
failure
Airline
notification
failure
TravelAgency
notification
failure
Fr ag ment F'
Fr ag ment F
St r u c t u r a l c h a n g e REPL A CE( F, F' ) :
AND pattern replaced by XOR pattern
Message exchange
walidus fd 1 of 1 23.05.2012
Fig. 2. Book Trip Operation: Local Views
need to adopt a model for representing control-flow relations
between activities and interactions. In this paper, we adopt
a structured representation of process models. In essence, a
process model is represented as a tree whose leaves represent
activities or interactions and whose internal nodes represent
either sequence (SEQ), parallel (PAR), choice (CHC), or
repeat loop (RPT) constructs. Structured process models are
very close to BPEL. As an advantage they are simpler to
analyze and easier to comprehend. Although it is possible
to express unstructured models both when using BPEL
and BPMN, recent work has shown that most unstructured
process models can be automatically translated into structured
ones [13].
Definition 1: [(Structured) Process Model]A process model
πpof partner p(private view) is a tree with the following structure
(we use the type definition syntax of the ML language [14]):
P rocess ::= Node
Node ::= Activity|ControlNode|Event
Activity ::= InternalActivity|InteractionActivity
InteractionActivity ::= Send(Message,Destination)
|Receive(Message,Sender)
ControlNode ::= SEQ([Node])|CHC ({Node})
|PAR({Node})|RPT(Node)
Event ::= Start |End
In this structuring of a process model, we consider an
interaction activity one-to-many-send (respectively one-from-
many-receive) as several interaction activities of type send
(respectively receive) executed in parallel. We define a
fragment as a non-empty subgraph of a process model with a
single entry and a single exit edge. In Definitions 2 and 3, we
refer to the same control nodes and events as in Definition 1.
Definition 2: [Local Choreography Model] A local chore-
ography model Lpof partner pstates the external behavior of
pand is also denoted public view. It includes the interactions
with other partners as well as the constraints between them
from the view point of this partner:
LocalModel ::= Node
Node ::= Send(Message,Destination)
|Receive(Message,Sender)
|ControlNode|Event
Definition 3: [Global Choreography Model] The global
choreography model Grepresents a global view of the inter-
actions between collaborating partners.
GlobalModel ::= Node
Node ::= I(Source,Destination,Message)
|ControlNode|Event
where Icorresponds to interaction between the partners
source and destination. We consider Pas the set of all
partners participating in the choreography, Πas the set of their
process models, and Las the set of their local models.
Figure 3 depicts the RPST model of the book trip operation’s
global choreography model as presented in Figure 1. Leaves
represent interactions and internal nodes represent the control
flow patterns used.
In order to support changes of collaborative processes, we
consider basic change operations since more complex change
patterns can be expressed by combining of these operations.
seq
Book Trip Operation
book reserve
Traveler
TravelAgency
check and cash
TravelAgency
Acquirer
notificate failure
Acquirer
TravelAgency
notification failure
Acquirer
Airline
notificate failure
Acquirer
TravelAgency
credit card not
approved
TravelAgency
Traveler
ticket purshase
cancelled
Airline
Traveler
approval
Acquirer
TravelAgency
ticket
Airline
TravelAgency
payment ok
Acquirer
Airline
total value
TravelAgency
Traveler
Pu r c h a se co n f i r m a t i o n
Airline
TravelAgency
Fail
Ok
walidus fd 1 of 1 07.05.2012
Fig. 2. Global Choreography: Book Trip Operation []
collaboration
Traveler
book
reserve
credit card
not
approved
total
value
ticket
purshase
cancelled
Travel Agency
book
reserve
total
value
check
and cash
ticket
approval
notification
failure
credit card
not approved
Pu r s h ase
confirmation
Airline
payment
ok
ticket
notification
failure
ticket
purchase
cancelled
Pu r s h ase
confirmation
Acquirer
check
and cash
notification
failure
payment
ok
notification
failure
approval
walidus fd 1 of 1 08.05.2012
Fig. 3. Book Trip Operation: Local Views
Book Trip Operation
book reserve
Traveler
TravelAgency
check and cash
TravelAgency
Acquirer
notificate failure
Acquirer
TravelAgency
notification failure
Acquirer
Airline
notificate failure
Acquirer
TravelAgency
credit card not
approved
TravelAgency
Traveler
ticket purshase
cancelled
Airline
Traveler
approval
Acquirer
TravelAgency
ticket
Airline
TravelAgency
payment ok
Acquirer
Airline
total value
TravelAgency
Traveler
Pu r c h a se co n f i r m a t i o n
Airline
TravelAgency
Fail
Ok
walidus fd 1 of 1 07.05.2012
Fig. 2. Global Choreography: Book Trip Operation []
collaboration
Traveler
book
reserve
credit card
not
approved
total
value
ticket
purshase
cancelled
Travel Agency
book
reserve
total
value
check
and cash
ticket
approval
notification
failure
credit card
not approved
Pu r s h as e
confirmation
Airline
payment
ok
ticket
notification
failure
ticket
purchase
cancelled
Pu r s h as e
confirmation
Acquirer
check
and cash
notification
failure
payment
ok
notification
failure
approval
walidus fd 1 of 1 08.05.2012
Fig. 3. Book Trip Operation: Local Views
Book Trip Operation
book reserve
Traveler
TravelAgency
check and cash
TravelAgency
Acquirer
notificate failure
Acquirer
TravelAgency
notification failure
Acquirer
Airline
notificate failure
Acquirer
TravelAgency
credit card not
approved
TravelAgency
Traveler
ticket purshase
cancelled
Airline
Traveler
approval
Acquirer
TravelAgency
ticket
Airline
TravelAgency
payment ok
Acquirer
Airline
total value
TravelAgency
Traveler
Pu r c h a se co n f i r m a t i o n
Airline
TravelAgency
Fail
Ok
walidus fd 1 of 1 07.05.2012
Fig. 2. Global Choreography: Book Trip Operation []
collaboration
Traveler
book
reserve
credit card
not
approved
total
value
ticket
purshase
cancelled
Travel Agency
book
reserve
total
value
check
and cash
ticket
approval
notification
failure
credit card
not approved
Pu r s h ase
confirmation
Airline
payment
ok
ticket
notification
failure
ticket
purchase
cancelled
Pu r s h ase
confirmation
Acquirer
check
and cash
notification
failure
payment
ok
notification
failure
approval
walidus fd 1 of 1 08.05.2012
Fig. 3. Book Trip Operation: Local Views
Book Trip Operation
book reserve
Traveler
TravelAgency
check and cash
TravelAgency
Acquirer
notificate failure
Acquirer
TravelAgency
notification failure
Acquirer
Airline
notificate failure
Acquirer
TravelAgency
credit card not
approved
TravelAgency
Traveler
ticket purshase
cancelled
Airline
Traveler
approval
Acquirer
TravelAgency
ticket
Airline
TravelAgency
payment ok
Acquirer
Airline
total value
TravelAgency
Traveler
Pu r c h a se co n f i r m a t i o n
Airline
TravelAgency
Fail
Ok
walidus fd 1 of 1 07.05.2012
Fig. 2. Global Choreography: Book Trip Operation []
collaboration
Traveler
book
reserve
credit card
not
approved
total
value
ticket
purshase
cancelled
Travel Agency
book
reserve
total
value
check
and cash
ticket
approval
notification
failure
credit card
not approved
Pu r s h as e
confirmation
Airline
payment
ok
ticket
notification
failure
ticket
purchase
cancelled
Pu r s h as e
confirmation
Acquirer
check
and cash
notification
failure
payment
ok
notification
failure
approval
walidus fd 1 of 1 08.05.2012
Fig. 3. Book Trip Operation: Local Views
Book Trip Operation
book reserve
Traveler
TravelAgency
check and cash
TravelAgency
Acquirer
notificate failure
Acquirer
TravelAgency
notification failure
Acquirer
Airline
notificate failure
Acquirer
TravelAgency
credit card not
approved
TravelAgency
Traveler
ticket purshase
cancelled
Airline
Traveler
approval
Acquirer
TravelAgency
ticket
Airline
TravelAgency
payment ok
Acquirer
Airline
total value
TravelAgency
Traveler
Pu r c h a se co n f i r m a t i o n
Airline
TravelAgency
Fail
Ok
walidus fd 1 of 1 07.05.2012
Fig. 2. Global Choreography: Book Trip Operation []
collaboration
Traveler
book
reserve
credit card
not
approved
total
value
ticket
purshase
cancelled
Travel Agency
book
reserve
total
value
check
and cash
ticket
approval
notification
failure
credit card
not approved
Pu r s h as e
confirmation
Airline
payment
ok
ticket
notification
failure
ticket
purchase
cancelled
Pu r s h as e
confirmation
Acquirer
check
and cash
notification
failure
payment
ok
notification
failure
approval
walidus fd 1 of 1 08.05.2012
Fig. 3. Book Trip Operation: Local Views
Book Trip Operation
book reserve
Traveler
TravelAgency
check and cash
TravelAgency
Acquirer
notificate failure
Acquirer
TravelAgency
notification failure
Acquirer
Airline
notificate failure
Acquirer
TravelAgency
credit card not
approved
TravelAgency
Traveler
ticket purshase
cancelled
Airline
Traveler
approval
Acquirer
TravelAgency
ticket
Airline
TravelAgency
payment ok
Acquirer
Airline
total value
TravelAgency
Traveler
Pu r c h a se co n f i r m a t i o n
Airline
TravelAgency
Fail
Ok
walidus fd 1 of 1 07.05.2012
Fig. 2. Global Choreography: Book Trip Operation []
collaboration
Traveler
book
reserve
credit card
not
approved
total
value
ticket
purshase
cancelled
Travel Agency
book
reserve
total
value
check
and cash
ticket
approval
notification
failure
credit card
not approved
Pu r s h as e
confirmation
Airline
payment
ok
ticket
notification
failure
ticket
purchase
cancelled
Pu r s h as e
confirmation
Acquirer
check
and cash
notification
failure
payment
ok
notification
failure
approval
walidus fd 1 of 1 08.05.2012
Fig. 3. Book Trip Operation: Local Views
Book Trip Operation
book reserve
Traveler
TravelAgency
check and cash
TravelAgency
Acquirer
notificate failure
Acquirer
TravelAgency
notification failure
Acquirer
Airline
notificate failure
Acquirer
TravelAgency
credit card not
approved
TravelAgency
Traveler
ticket purshase
cancelled
Airline
Traveler
approval
Acquirer
TravelAgency
ticket
Airline
TravelAgency
payment ok
Acquirer
Airline
total value
TravelAgency
Traveler
Pu r c h a se co n f i r m a t i o n
Airline
TravelAgency
Fail
Ok
walidus fd 1 of 1 07.05.2012
Fig. 2. Global Choreography: Book Trip Operation []
collaboration
Traveler
book
reserve
credit card
not
approved
total
value
ticket
purshase
cancelled
Travel Agency
book
reserve
total
value
check
and cash
ticket
approval
notification
failure
credit card
not approved
Pu r s h as e
confirmation
Airline
payment
ok
ticket
notification
failure
ticket
purchase
cancelled
Pu r s h as e
confirmation
Acquirer
check
and cash
notification
failure
payment
ok
notification
failure
approval
walidus fd 1 of 1 08.05.2012
Fig. 3. Book Trip Operation: Local Views
Book Trip Operation
book reserve
Traveler
TravelAgency
check and cash
TravelAgency
Acquirer
notificate failure
Acquirer
TravelAgency
notification failure
Acquirer
Airline
notificate failure
Acquirer
TravelAgency
credit card not
approved
TravelAgency
Traveler
ticket purshase
cancelled
Airline
Traveler
approval
Acquirer
TravelAgency
ticket
Airline
TravelAgency
payment ok
Acquirer
Airline
total value
TravelAgency
Traveler
Pu r c h a se co n f i r m a t i o n
Airline
TravelAgency
Fail
Ok
walidus fd 1 of 1 07.05.2012
Fig. 2. Global Choreography: Book Trip Operation []
collaboration
Traveler
book
reserve
credit card
not
approved
total
value
ticket
purshase
cancelled
Travel Agency
book
reserve
total
value
check
and cash
ticket
approval
notification
failure
credit card
not approved
Pu r s h as e
confirmation
Airline
payment
ok
ticket
notification
failure
ticket
purchase
cancelled
Pu r s h as e
confirmation
Acquirer
check
and cash
notification
failure
payment
ok
notification
failure
approval
walidus fd 1 of 1 08.05.2012
Fig. 3. Book Trip Operation: Local Views
Book Trip Operation
book reserve
Traveler
TravelAgency
check and cash
TravelAgency
Acquirer
notificate failure
Acquirer
TravelAgency
notification failure
Acquirer
Airline
notificate failure
Acquirer
TravelAgency
credit card not
approved
TravelAgency
Traveler
ticket purshase
cancelled
Airline
Traveler
approval
Acquirer
TravelAgency
ticket
Airline
TravelAgency
payment ok
Acquirer
Airline
total value
TravelAgency
Traveler
Pu r c h a se co n f i r m a t i o n
Airline
TravelAgency
Fail
Ok
walidus fd 1 of 1 07.05.2012
Fig. 2. Global Choreography: Book Trip Operation []
collaboration
Traveler
book
reserve
credit card
not
approved
total
value
ticket
purshase
cancelled
Travel Agency
book
reserve
total
value
check
and cash
ticket
approval
notification
failure
credit card
not approved
Pu r s h as e
confirmation
Airline
payment
ok
ticket
notification
failure
ticket
purchase
cancelled
Pu r s h as e
confirmation
Acquirer
check
and cash
notification
failure
payment
ok
notification
failure
approval
walidus fd 1 of 1 08.05.2012
Fig. 3. Book Trip Operation: Local Views
Book Trip Operation
book reserve
Traveler
TravelAgency
check and cash
TravelAgency
Acquirer
notificate failure
Acquirer
TravelAgency
notification failure
Acquirer
Airline
notificate failure
Acquirer
TravelAgency
credit card not
approved
TravelAgency
Traveler
ticket purshase
cancelled
Airline
Traveler
approval
Acquirer
TravelAgency
ticket
Airline
TravelAgency
payment ok
Acquirer
Airline
total value
TravelAgency
Traveler
Pu r c h a se co n f i r m a t i o n
Airline
TravelAgency
Fail
Ok
walidus fd 1 of 1 07.05.2012
Fig. 2. Global Choreography: Book Trip Operation []
collaboration
Traveler
book
reserve
credit card
not
approved
total
value
ticket
purshase
cancelled
Travel Agency
book
reserve
total
value
check
and cash
ticket
approval
notification
failure
credit card
not approved
Pu r s h ase
confirmation
Airline
payment
ok
ticket
notification
failure
ticket
purchase
cancelled
Pu r s h ase
confirmation
Acquirer
check
and cash
notification
failure
payment
ok
notification
failure
approval
walidus fd 1 of 1 08.05.2012
Fig. 3. Book Trip Operation: Local Views
Book Trip Operation
book reserve
Traveler
TravelAgency
check and cash
TravelAgency
Acquirer
notificate failure
Acquirer
TravelAgency
notification failure
Acquirer
Airline
notificate failure
Acquirer
TravelAgency
credit card not
approved
TravelAgency
Traveler
ticket purshase
cancelled
Airline
Traveler
approval
Acquirer
TravelAgency
ticket
Airline
TravelAgency
payment ok
Acquirer
Airline
total value
TravelAgency
Traveler
Pu r c h a se co n f i r m a t i o n
Airline
TravelAgency
Fail
Ok
walidus fd 1 of 1 07.05.2012
Fig. 2. Global Choreography: Book Trip Operation []
collaboration
Traveler
book
reserve
credit card
not
appr oved
total
value
ticket
purshase
cancelled
Travel Agency
book
reserve
total
value
check
and cash
ticket
appr oval
notification
failure
credit card
not approved
Pu r s h ase
confirmation
Airline
payment
ok
ticket
notification
failure
ticket
purchase
cancelled
Pu r s h ase
confirmation
Acquirer
check
and cash
notification
failure
payment
ok
notification
failure
appr oval
walidus fd 1 of 1 08.05.2012
Fig. 3. Book Trip Operation: Local Views
Book Trip Operation
book reserve
Traveler
TravelAgency
check and cash
TravelAgency
Acquirer
notificate failure
Acquirer
TravelAgency
notification failure
Acquirer
Airline
notificate failure
Acquirer
TravelAgency
credit card not
approved
TravelAgency
Traveler
ticket purshase
cancelled
Airline
Traveler
approval
Acquirer
TravelAgency
ticket
Airline
TravelAgency
payment ok
Acquirer
Airline
total value
TravelAgency
Traveler
Pu r c h a se co n f i r m a t i o n
Airline
TravelAgency
Fail
Ok
walidus fd 1 of 1 07.05.2012
Fig. 2. Global Choreography: Book Trip Operation []
collaboration
Traveler
book
reserve
credit card
not
approved
total
value
ticket
purshase
cancelled
Travel Agency
book
reserve
total
value
check
and cash
ticket
approval
notification
failure
credit card
not approved
Pu r s h ase
confirmation
Airline
payment
ok
ticket
notification
failure
ticket
purchase
cancelled
Pu r s h ase
confirmation
Acquirer
check
and cash
notification
failure
payment
ok
notification
failure
approval
walidus fd 1 of 1 08.05.2012
Fig. 3. Book Trip Operation: Local Views
Book Trip Operation
book reserve
Traveler
TravelAgency
check and cash
TravelAgency
Acquirer
notificate failure
Acquirer
TravelAgency
notification failure
Acquirer
Airline
notificate failure
Acquirer
TravelAgency
credit card not
approved
TravelAgency
Traveler
ticket purshase
cancelled
Airline
Traveler
approval
Acquirer
TravelAgency
ticket
Airline
TravelAgency
payment ok
Acquirer
Airline
total value
TravelAgency
Traveler
Pu r c h a se co n f i r m a t i o n
Airline
TravelAgency
Fail
Ok
walidus fd 1 of 1 07.05.2012
Fig. 2. Global Choreography: Book Trip Operation []
collaboration
Traveler
book
reserve
credit card
not
approved
total
value
ticket
purshase
cancelled
Travel Agency
book
reserve
total
value
check
and cash
ticket
approval
notification
failure
credit card
not approved
Pu r s h ase
confirmation
Airline
payment
ok
ticket
notification
failure
ticket
purchase
cancelled
Pu r s h ase
confirmation
Acquirer
check
and cash
notification
failure
payment
ok
notification
failure
approval
walidus fd 1 of 1 08.05.2012
Fig. 3. Book Trip Operation: Local Views
seq
seq
seq seq
F1
F11 F12
F112
F111 F121
F1211
F12111
Book Trip Operation
book reserve
Traveler
TravelAgency
check and cash
TravelAgency
Acquirer
notificate failure
Acquirer
TravelAgency
airline notif icat ion
failure
Acquirer
Airline
TravelAgency
notification failure
Acquirer
TravelAgency
credit card not
approved
TravelAgency
Traveler
ticket purshase
cancelled
Airline
Traveler
approval
Acquirer
TravelAgency
ticket
Airline
TravelAgency
payment ok
Acquirer
Airline
total value
TravelAgency
Traveler
purchase confirmation
Airline
TravelAgency
Fail
Ok
walidus fd 1 of 1 10.05.2012
Fig. 1. Global Choreography: Book Trip Operation [8]
choreography models as well as a consistent global chore-
ography. Finally, we sketch the transition from the structural
considerations provided in this paper to semantic issues and
future challenges.
In Sect. 2 the problem space is introduced, followed by
fundamental definitions in Section 3. Section 4 provides the
change propagation algorithms. Our approach is evaluated in
Section 5. In Section 6 we discuss related work and Sections
7 summarizes the paper.
II. MOTIVATION AND CHALLENGES
We illustrate change propagation issues along the booking
trip choreography example depicted in Figure 1. The latter is
part of the choreography example described in [8]. It is mod-
eled in BPMN 2.0 and describes a collaboration between four
partners, i.e., traveler,travel agency,acquirer, and airline. The
traveler sends booking information to the travel agency which,
in turn, contacts the acquirer to request a credit check. If the
traveler has not enough credit, failure notifications are sent
to the travel agency and the airline partners which inform
the traveler about the reservation failure and the purchase
cancellation respectively. Otherwise, an approval is sent to the
travel agency and the airline is triggered to send the ticket
and the purchase confirmation.
Figure 2 depicts the public views (i.e., local choreography
models) of all participants involved in the choreography. Each
partner view includes only the interactions in which this
partner is involved as well as the control flow between them.
Figure 2 does not show the private view (i.e., orchestration) of
each partner that includes the internal activities. These local
views merged together lead to the global choreography model.
Now assume that partner acquirer wants to change the logic
of its private process. For instance, instead of sending two
failure notifications to airline and travel agency respectively,
he notifies only one of them. In Figure 2, fragment Fis
replaced by fragment F0(XOR instead of AND). Then, for
some process instances, partner airline would wait indefinitely
for a failure notification if the acquirer chooses to send a
notification only to the travel agency. In this case, the acquirer
process instance would be blocked in this state and not ter-
minate. Hence, the described change affects the soundness of
the choreography model in terms of compatibility between the
distributed public views. To overcome this problem, the effects
of this local change in the acquirer process model should
be propagated to the concerned partners and the interactions
should be restructured consequently.
Generally, the challenges are as follows: How to compute
the impacts of this local change on the other partners and the
global choreography? How to propagate the effects of the local
change while preserving the soundness of the collaboration in
terms of consistency and compatibility [11]? How to deal with
transitive effects of changes? What if changes are made dy-
namically, i.e. during the execution of choreography instances?
How to manage the different versions of the choreography
model (used in monitoring) and the participants’ processes at
runtime?
III. PRELIMINARIES
As emphasized, this paper deals with change propagation in
collaborative processes. In practice, there are three different,
but overlapping viewpoints in a collaboration: orchestration,
behavioral interface, and choreography [12]. An orchestration
describes the internal business logic of private processes as
well as the communication actions in which a particular
partner engages. The behavioral interface (also called public
view or local choreography model) sketches the message
exchanges from the perspective of a single partner as well as
the sequencing between them. In other words, it represents
an abstraction of an orchestration’s internal actions. The
choreography (also called global model) gives a global
view of all interactions in the collaboration. It captures the
interactions in which the participating partners engage to
achieve a goal as well as the dependencies between these
interactions. In order to precisely define the notions of
orchestration, behavioral interface and choreography, we
need to adopt a model for representing control-flow relations
between activities and interactions. In this paper, we adopt
a structured representation of process models. In essence, a
Book Trip Operation
book reserve
Traveler
TravelAgency
check and cash
TravelAgency
Acquirer
notificate failure
Acquirer
TravelAgency
airline notification
failure
Acquirer
Airline
TravelAgency
notification failure
Acquirer
TravelAgency
credit card not
approved
TravelAgency
Traveler
ticket purshase
cancelled
Airline
Traveler
approval
Acquirer
TravelAgency
ticket
Airline
TravelAgency
payment ok
Acquirer
Airline
total value
TravelAgency
Traveler
purchase confirmation
Airline
TravelAgency
Fail
Ok
walidus fd 1 of 1 10.05.2012
Fig. 1. Global Choreography: Book Trip Operation [8]
choreography models as well as a consistent global chore-
ography. Finally, we sketch the transition from the structural
considerations provided in this paper to semantic issues and
future challenges.
In Sect. 2 the problem space is introduced, followed by
fundamental definitions in Section 3. Section 4 provides the
change propagation algorithms. Our approach is evaluated in
Section 5. In Section 6 we discuss related work and Sections
7 summarizes the paper.
II. MOTIVATION AND CHALLENGES
We illustrate change propagation issues along the booking
trip choreography example depicted in Figure 1. The latter is
part of the choreography example described in [8]. It is mod-
eled in BPMN 2.0 and describes a collaboration between four
partners, i.e., traveler,travel agency,acquirer, and airline. The
traveler sends booking information to the travel agency which,
in turn, contacts the acquirer to request a credit check. If the
traveler has not enough credit, failure notifications are sent
to the travel agency and the airline partners which inform
the traveler about the reservation failure and the purchase
cancellation respectively. Otherwise, an approval is sent to the
travel agency and the airline is triggered to send the ticket
and the purchase confirmation.
Figure 2 depicts the public views (i.e., local choreography
models) of all participants involved in the choreography. Each
partner view includes only the interactions in which this
partner is involved as well as the control flow between them.
Figure 2 does not show the private view (i.e., orchestration) of
each partner that includes the internal activities. These local
views merged together lead to the global choreography model.
Now assume that partner acquirer wants to change the logic
of its private process. For instance, instead of sending two
failure notifications to airline and travel agency respectively,
he notifies only one of them. In Figure 2, fragment Fis
replaced by fragment F0(XOR instead of AND). Then, for
some process instances, partner airline would wait indefinitely
for a failure notification if the acquirer chooses to send a
notification only to the travel agency. In this case, the acquirer
process instance would be blocked in this state and not ter-
minate. Hence, the described change affects the soundness of
the choreography model in terms of compatibility between the
distributed public views. To overcome this problem, the effects
of this local change in the acquirer process model should
be propagated to the concerned partners and the interactions
should be restructured consequently.
Generally, the challenges are as follows: How to compute
the impacts of this local change on the other partners and the
global choreography? How to propagate the effects of the local
change while preserving the soundness of the collaboration in
terms of consistency and compatibility [11]? How to deal with
transitive effects of changes? What if changes are made dy-
namically, i.e. during the execution of choreography instances?
How to manage the different versions of the choreography
model (used in monitoring) and the participants’ processes at
runtime?
III. PRELIMINARIES
As emphasized, this paper deals with change propagation in
collaborative processes. In practice, there are three different,
but overlapping viewpoints in a collaboration: orchestration,
behavioral interface, and choreography [12]. An orchestration
describes the internal business logic of private processes as
well as the communication actions in which a particular
partner engages. The behavioral interface (also called public
view or local choreography model) sketches the message
exchanges from the perspective of a single partner as well as
the sequencing between them. In other words, it represents
an abstraction of an orchestration’s internal actions. The
choreography (also called global model) gives a global
view of all interactions in the collaboration. It captures the
interactions in which the participating partners engage to
achieve a goal as well as the dependencies between these
interactions. In order to precisely define the notions of
orchestration, behavioral interface and choreography, we
need to adopt a model for representing control-flow relations
between activities and interactions. In this paper, we adopt
a structured representation of process models. In essence, a
Fig. 3. Book Trip Operation: Refined Process Structure Tree
Change operations are defined as follows.
Definition 4: [Change Patterns]
ChangeP attern ::= Structural |Semantical
Structural ::= REPLACE(oldFragment,newFragment)
|DELETE(fragment)
|INSERT (fragment,how,in,out)
how ::= P arallel |Choice |Sequence
Semantical ::= UPDATE(activity,attribute,newValue)
attribute ::= partner|role|Input|Output
where REPLACE replaces an existing fragment with a new one,
DELETE removes an existing fragment, INSERT adds a new
fragment into the process model between in and out, and UPDATE
modifies an attribute of a single activity.
Definition 5: [Change Operation] A change operation is a
tuple (δ,Σ) where δis the change pattern and Σis either the
process model, or the local or global choreography model to
be changed.
Definition 6: [Abstraction function] Abstraction function
abstrλ(π)is a projection of a process model πaccording
to criterion λ. It transforms the source process model πinto
a target model π0where π0includes only activities satisfy-
ing λ(e.g., the local choreography model is an abstraction
of its respective process model according to interaction
activities). A reduction function may be applied to eliminate
unnecessary control patterns after abstraction (e.g., a parallel
pattern between an activity and an empty transition may be
reduced to sequence) [15], [16]. For instance, depending on a
certain condition, a different value of a data element dis sent
to the same partner p. In the local view, this is reduced to only
one interaction which corresponds to the sending of data d.
Next, we extend Definition 6 to consider fragments as well
as local and global choreography models. We also assume that
λ=p0means the interactions with p0. Hence, abstrp0(Lp)is
the abstraction of Lpaccording to the interactions with p0.
Definition 7: [Complement function] If a∈pis an inter-
action activity with a partner p0, the complement of acalled
a∈p0is the opposite of aas follows.
•send(message, p0)=receive(message, p).
•receive(message, p0)=send(message, p).
If Fis a fragment that solely includes interaction activities,
Fcorresponds to a fragment with same structure where each
activity is replaced by its complement.
Lemma 1: abstrp0(F)∈ Lp=⇒abstrp0(F)∈
abstrp(Lp0)
The complement of the abstraction of a participant fragment
F ∈ Lpaccording to participant p0is a fragment of the
abstraction of Lp0according to p.
Proof: The proof of this lemma can be based on the
following compatibility properties of the collaboration [11].
•If a∈ Lpis an activity that interacts with partner p0,
then: ∃b∈ Lp0with b=a.
•If ai,aj∈ Lpare two activities that interact with the
same partner p0and β(ai, aj)is a function that returns
the minimal precedence relation between aiand aj(after
reduction), then: ∃bi, bj∈ Lp0with bi=ai,bj=ajand
β(ai, aj)=β(bi, bj)(bi-simulation property [11], [13]) .
Definition 8: [αfunction] Let πbe a process model and F
be a fragment with: ∀o∈ F =⇒o∈π, where odenotes an
object of type activity or control node. Then: Function απ(F)
returns the smallest fragment in the process structure tree of π
that contains all elements of F. This function is also used to
identify a fragment in a local or global choreography model.
IV. CHANGE PROPAGATION
This section introduces a global view of the proposed
approach and details the different steps to propagate changes
in collaborative processes.
Start Specify
change
Infer
interaction
changes
Update local
choreography
models
Select an
affected partner
Variant?
Compute
affected
partners
Do
Update global
choreography
model
Negotiate
changes
Compute changes
to propagate to
this partner
last
partner?
Update local
change
Find another
alternative
End
Yes
No
Yes No
No
Yes
Check
compatibility
and consitency
Propagate
changes
public2private
ok?
Yes
No
negociations
succeed?
Compute
public2private
changes
Fail
Succeed
Succeed
Fail abandon?
Yes
No
Fig. 4. Change Propagation - Major Steps
A. Overview
As afore mentioned, our objective is to support change
propagation in choreographies with multiple interacting part-
ner processes. Our approach relies on four major steps: (i)
identifying interactions affected by the change as well as the
partners involved, (ii) translating the initial change operation
into several change operations each related to a particular
partner, (iii) negotiating with the affected partners, and (iv)
checking consistency and compatibility of the changed chore-
ography. Figure 4 details the previous steps and outlines the
different actions to achieve a sound propagation.
Given a change operation on one partner orchestration, we
extract all interaction activities concerned by the change. Inter-
action activities are communication actions with other partners
(i.e., sending and receiving requests). If the list is empty (i.e.,
if the local change is restricted to the internal behavior), the
other business partners are not affected by the change and there
is no need for a new agreement on the global choreography.
Otherwise, the list of affected interactions is analyzed to iden-
tify all partners involved. For each of these partners, a relative
change computation is undertaken to gather the changes to be
propagated. The latter are computed according to the change
operation type. Then, a negotiation phase is launched with
each affected partner. If all negotiations succeed, we apply
consistency and compatibility checks to ensure the soundness
of the obtained models. If these models are sound, we update
the local and the global choreography models affected by the
change and, if necessary, adapt concerned orchestrations to
their new behavioral interfaces. Section IV-B is structured
according to the mentioned steps. It sketches the different
algorithms needed for propagating changes. Note that this
propagation strongly depends on the change operation type
(i.e., INSERT, DELETE, REPLACE and UPDATE).
B. Algorithms Enabling Change Propagation
Consider a change operation δon a process model πp.
To start, we abstract the changed fragment according to
its interaction activities; i.e., we look for the structural
or semantical changes that affect the interactions with the
other partners. According to the change operation type, a
particular procedure for decomposition is performed. This
decomposition transforms the initial change operation into
several change actions to be propagated to each affected
partner. Due to lack of space, here, we only consider the
UPDATE and the REPLACE change patterns. Note that
REPLACE can cover patterns INSERT and DELETE.
1) REPLACE Decomposition: Assume we want to replace
a fragment Fby a new fragment F0with a different structure
(e.g., in the book trip example depicted in Figure 1;
REP LACE(P AR(Airline notification failure,
TravelAgency notification failure),CHC(Airline no−
tification failure , T ravelAgency notification failure)
), πacquirer)). As described in Algorithm 1, the first step
computes all partners involved in Fand F0(e.g., Airline
and TravelAgency) and for each partner p0we abstract
from, the respective interaction activities (abstrp0(F)and
abstrp0(F0)) (e.g., in the example, Fand F0already include
interactions activities only). At this level, for a particular
partner, three possible scenarios can be identified: (i) a partner
involved in the original fragment Fis no longer present in
the new fragment F0(deletion of the interaction with this
partner), (ii) a partner involved in F0was not present in F
(adding a new interaction), and finally (iii) a partner present
in both fragments Fand F0, but with different structure
(updating the conversation with a partner). As a consequence
of these scenarios, the REPLACE pattern is translated into
a concatenation ∆of change patterns to propagate to the
affected partners.
(i) Deletion scenario: If a particular partner p0interacts
with the partner pin fragment Fand is not engaged in any
conversation with pin the new fragment F0, we delete the
respective interactions from their local choreography models.
To achieve this, we consider each interaction activity awith
p0to be deleted in F. Further, we search for the matching
activity ain p0and derive the change pattern DELETE(a, Lp0).
Note that this operation is not applied directly since there is a
negotiation phase. Besides, this deletion could have subsequent
effects on p0. Indeed, it is possible that other interactions
in p0semantically depend on the deleted interaction (e.g.,
supply chains scenarios). This is called transitivity effect and
it does not constitute a structural problem, but a semantical
one. In this section, we focus only on structural changes,
but resolve the transitivity effects separately in Section IV-C.
So, if activities to delete are synchronous (e.g., waiting
for a response or replying to a request), then we delete
the corresponding activities. For example, consider a buyer
that invokes a seller for a price request (i.e., send(seller,
price request), receive(buyer, price request)). If we delete this
interaction, we must delete the corresponding response to the
buyer as well (i.e., send(buyer, price response), receive(seller,
price response)). This could be achieved using the correlations
between activities (e.g., correlation sets known from BPEL).
Algorithm 1: Decomposition of Change Pattern
REP LACEπ(F,F0)
Input: - Set of all local choreography models1
L={Lp|p∈ P}
- Global choreography model G2
begin3
∆← ∅ //decomposition result4
P∆←List of all business partners involved in F ∪ F0
5
for (each partner p∈P∆)do6
FG←αG(F){smallest fragment including Fin G}7
if abstrp(F)6=abstrp(F0)then8
if abstrp(F) = ∅then9
in =T presetp(FG,G)10
out =T postsetp(FG,G)11
if (∃a∈ Lpbetween in and out)then12
∆←∆∧13
INSERTp(abstrp(F0), P arallel, Lp.in, Lp.out)
else14
∆←∆∧15
INSERTp(abstrp(F0), Sequence, Lp.in, Lp.out)
end16
else17
if abstrp(F0) = ∅then18
for (each a∈abstrp(F)) do19
∆←∆∧DELET Ep(a){reduction rules20
may apply when executing the changes}
if (ais synchronous) then21
∆←22
∆∧DELET Eπ(a0)∧DELET Ep(a0)
{a0and a0are the relative responses or23
requests of aand a}
end24
end25
else26
∆←∆∧27
REP LACEp(αp(abstrp(F)), γ(abstrp(F0),
αp(abstrp(F)))) {γis the merge function}28
for each a∈ F st a /∈ F0do29
∆←∆∧DELET Ep(a){if synchronous30
we do the same procedure as before}
end31
end32
end33
end34
end35
Output ∆;36
end37
(ii) Insertion scenario: If a particular partner p0has no
interactions with pin the old fragment F, but interacts with p
in the new fragment F0, we have to insert the new interactions
in the local choreography model of p0(Lp0). For this purpose,
we abstract F0according to partner p0, compute abstrp0(F0)
and lookup for the exact insertion position of the latter in Lp0.
In order to compute this position, while preserving structural
dependencies, we make use of the global choreography model.
Indeed, partner p0may have other interactions with poutside
the changed fragment For with other partners outside or
inside αG(F)in the global model G(where αG(F)is the
smallest fragment that encapsulates Fin the RPST of G).
Note that FGincludes all interactions of pwhich appear
in Fmerged with other interactions of different partners.
For example, consider the change scenario introduced in
Section II, where fragment Fis replaced by F0. The smallest
fragment containing the two activities of F(i.e., airline
and travel agency failure notifications) in the RPST of the
book trip global choreography model is F11 (cf. Figure 3).
The latter includes other interactions concerning the airline
and travel agency partners (i.e., credit card not approved and
ticket purchase cancelled).
Algorithm 2: Transitive Preset and Postset Computation:
T presetp(F, π)T postsetp(F, π)
Init: -T preset =start1
-T postset =end2
begin3
predecessor =F.F irstElement4
repeat5
predecessor ←predecessor.parent6
if predecessor =sequence then7
repeat8
childleft ←predecessor.Child.left.next {parse9
from right to left}
childright ←predecessor.Child.right.next10
{parse from left to right}
if ∃F0∈childleft st ∃ai∈ F0which invokes pthen11
T preset =abstrp(child)12
preset path = path between Fand T preset13
end14
if ∃F0∈childright st ∃ai∈ F0which invokes pthen15
T postset =abstrp(child)16
postset path = path between Fand T postset17
end18
until ;19
end20
until ((T preset 6=start ∧T postset 6=end)∨predecessor =21
rootElement) ;
end22
Output: T postset,T preset ;23
Once αG(F)is identified, we compute the transitive preset
and postset of αG(F)according to p0. The transitive postset
T postsetp0(αG(F),G) (preset T presetp0(αG(F),G))
represents the smallest fragment of Gcontaining interactions
of p0that could be executed just before (just after) αG(F).
These two variables are used to identify the insertion position
of abstrp0(F0) in Lp0. To compute these values we refer to
Algorithm 2. Given a fragment F, a process model π, and a
partner p, T presetp(F)is calculated as follows: Algorithm
2 first parses the RPST from Fto the root element, and for
each sequence element found, it parses the child elements
from the right to the left and checks whether a child contains
activities or interactions with p. If this applies, abstr(child)
represents the transitive preset. If no child element contains
interaction activities with p, we try to discover the upper
level in the tree and repeat the same procedure. The postset
is computed the same way except that we discover the
right part of the process tree. The transitive preset and
postset (in =T presetp0(αG(F),G)and out =T postsetp0(
αG(F),G)) represent the insertion position of the fragment
abstrp0(F0)in Lp0. If there are no activities between in and
out in the initial model, we insert abstrp0(F0)in sequence.
Otherwise, we insert it in parallel.
(iii) Replacement scenario: Finally, the last scenario is
when both fragments Fand F0contain interactions with
a partner p0, but with different structures (control flow).
This means that the dependencies between interactions have
changed and therefore the local view of p0should be updated
to conserve compatibility between the behavioral interfaces.
For instance, in the change operation example from Figure 2,
F0contains the same interaction with airline for sending the
failure notification, but with different structure (the latter could
be sent or not depending on the running instance). So, the
idea is to abstract the interactions with p0in F(abstrp0(F)),
identify abstrp0(F)in Lp0, and replace it with abstrp0(F0).
However, this is not possible if the smallest fragment in Lp0,
which contains the activities of abstrp(F0), includes other
interactions with different partners. For this purpose, we adopt
a merge algorithm to merge abstrp(F)with αp(abstrp(F0).
Indeed, merging process models has been widely studied and
many works were proposed [17], [18]. The key idea is to
merge different (and overlapping) process models into a single
model without restricting the behavior that was possible in
the original models. So, if we consider γas a merge function
then the problem could be solved by deleting the activities of
abstrp(F)from αp(abstrp(F)) and then merging abstrp(F0)
with the rest of activities in αp(abstrp(F)). The merge could
also lead to a semantic violation. For instance, if we refer
to our change scenario for the book trip operation, the change
propagation to the airline partner is depicted in Figure 5. Two
scenarios are possible: the modified fragment is inserted before
activity ticket purchase order or it is merged with it. The
first case is structurally correct in terms of dependencies, and
it conserves the compatibility between the interfaces. How-
ever, in case ticket purchase order semantically depends of
some parameters of activity airline notification failure,
the second scenario is considered to be more correct. This is
a semantic issue and should be validated by the target partner
affected. The latter should validate the proposed scenario
which goes with its semantics.
2) UPDATE Decomposition: As afore mentioned, the UP-
DATE pattern is used to update the attributes of a single
activity. This paper considers the update of attribute partner,
but this can be easily be generalized to consider other attributes
as well (e.g., input,output, etc.). For instance, we assume that
an interaction activity aof πpshould be updated to interact
with p00 instead of p0. In this case, we look at ain Lp0
and delete it. If the interaction is synchronous, we delete the
ChangePropagation
Airline
ticket
purchase
cancelled
Airline
notification
failure
Airline
Airline
notification
failure
ticket
purchase
cancelled
Se m a n t i c v i o l a t i o n i f t i c k e t _ p u r c h a s e
_cancel led d epend s sem an t i cally of
Airline_notification_failure
Transitive effects:
ticket_purschase_cancelled is
not always sent to Traveler
walidus fd 1 of 1 23.05.2012
(a) first scenario
ChangePropagation
Airline
ticket
purchase
cancelled
Airline
notification
failure
Airline
Airline
notification
failure
ticket
purchase
cancelled
Se m a n t i c v i o l a t i o n i f t i c k e t _ p u r c h a s e
_cancel led dep ends sem antical ly of
Airline_notification_failure
Transitive effects:
ticket_purschase_cancelled is
not always sent to Traveler
walidus fd 1 of 1 23.05.2012
(b) second scenario
Fig. 5. Airline: Change Propagation
corresponding activity to a(i.e., reply to a request or receive
a response) correlating inputs and outputs. We also update
the corresponding activity to ain Lpwith the new partner
p00. Then, we check whether or not p00 already exists in the
list of partners. In the latter case, we create a new public
view for p00 containing aand the corresponding activity a00 if
the communication is synchronous. If the partner p00 already
exists, we check where to insert aand possibly a0in Lp00 .
For this purpose, we use the global choreography model G
and compute the transitive preset and postset of a(in and
out) and a0(in0and out0) according to p00. If there are other
interactions with p00 between in and out, we compute their
dependencies with aand insert the latter in Lp0accordingly.
The same holds for a0if the communication is synchronous.
Algorithm 3: Decomposition of Change Pattern
UP DAT Eπ(a, attribute, newV alue)
Input: -Set of all business partners P1
- Set of all local choreography models L={Li, i ∈ P}2
- Global choreography model G3
begin4
if (attribute =partner)then5
p0←a.partner {oldpartner}6
p00 ←value {newpartner}7
if p00 /∈ P then8
Create(lp00 ){new local view}
9
Add(lp00 ,L)and Add(p00,P)
10
end11
∆←∆∧DELET Ep0(a)
12
∆←∆∧INSERTp00 (a, P arallel|Sequence, in, out){in
13 and out are computed as in previous algorithms}
if Synchronous then14
a0=Response(a)15
∆←∆∧DELET Ep0(a)16
∆←∆∧INSERTp00 (a0, P arallel|Sequence, in0, out0)
17
{in0and out0are computed as in previous algorithms}
if p0=∅then18
remove(p0,P)and remove(lp0,L)
19
end20
end21
else22
end23
end24
Output ∆;25
C. Delete pattern: dealing with transitivity
We now present a non-exhaustive list of use cases showing
the transitivity effects of the DELETE change pattern and the
solutions to cope with them. Note that this is a semantic issue
and can not be resolved using the propagation algorithms
presented so far and focusing on structural propagation.
For example, consider three partners p1,p2and p3with p1
invoking p2, which in turn, invokes p3. The latter returns the
intermediary result to p2, which applies data transformations
and sends the final result to p1. So, if p1decides to delete
its interaction with p2, we also must delete the subsequent
interaction between p2and p3which is just used to deliver the
final result. If a partner deletes an interaction, Semantically
this means that he is not able to afford this service anymore,
or he does not need the data anymore. The challenge is to
determine if an interaction is transitive according to another
one, to identify the transitivity effects, and to resolve them.
Case 1: If partner pis the final consumer of a data
element; he launches a communication in which he requires
a response. pincludes correlated send and receive patterns
S/R (non-blocking S/R pattern).
•pdeletes the send/receive patterns. This means that p
does not need the data anymore (since pis the final
consumer). We delete send and receive. In case where
all subsequent interactions with other partners are just
used to deliver this data, we delete them (e.g. supply
chain scenarios). It is possible that only a subset of
the subsequent interactions are used to deliver this data.
These are deleted only if they don’t have any other role
in the choreography.
Example: two concurrent request from A and B to the
same partner C. The latter does subsequent interactions
and then reply to both of them. If A deletes his interac-
tion, we should not delete the subsequent interactions of
C since they are still used to reply to B.
•pdeletes only the send pattern. Two scenarios: (i)
Another partner starts the communication instead of him
and then we just Update the correspondent send with
the new partner, or (ii) pis not responsible anymore for
informing the other partner to start the processing of the
response (the response starts automatically or under other
constraints) and then we Delete the corresponding send.
•pdeletes only the receive pattern. This means either he
does not need the data anymore or the data is transferred
to another partner. In the first case, we just delete the
corresponding receive and look for other interactions
correlated with this response (just used for delivering the
response). In the second case, we update the correspond-
ing receive with the new partner.
Case 2: Partner pis the final consumer of the data but is
not responsible for launching the first interaction (phas only
the receive). Then, if pdeletes the receive (does not need the
data anymore), we delete the corresponding receive as well
as all subsequent interactions used only to deliver this data.
All interactions that participate in delivering this data but have
another role in the choreography, are kept.
Case 3: pis the starting point, responsible for starting
a communication resulting in a response to another partner
(phas the send). Either (i) another partner is responsible for
starting this communication; then, we update the send with the
new partner, or (ii) the communication starts automatically or
under other constraints on the target partner; then we delete the
corresponding send. Subsequent interactions are not deleted
since we still need the final data to be delivered to the final
consumer.
Case 4: pis an intermediary partner in the conversation.
•phas correlated receive and send in sequence.preceives
a request, starts a subsequent interactions necessary for
delivering the final response to the requester.
–If pdeletes the send and the receive patterns,
this means that pis not able to afford the service
anymore, but we still need the final response to
the requester. In this case, we have two choices: (i)
looking for another partner who can do the work of
pto deliver this response; in this case, we update the
subsequent interactions as well as the interactions of
the root partner (the one who invoked pand the one
yo which pshould send the result) with this new
partner, (ii) deleting send and receive as well as
all subsequent interactions used only in the context
of this intermediary data and looking for another
partner or set of partner who fulfill this intermediary
task. Then we update the communications with the
root partners or p.
–If pdeletes only the send pattern, this means another
partner is responsible for starting this intermediary
communication or the subsequent interactions start
automatically or under other constraints. In the first
case, we update the corresponding receive with the
new partner, otherwise we just delete the receive.
–If pdeletes only the receive pattern, this means
that pcan not or do not want to do anymore the
operations just after the receive and related to the
delivery of the final data. (i) If no related operations
are necessary to deliver the intermediate data, we
update the receive to link it directly with root partner
(ii) If related operations are necessary, we look for
another partner which can fulfill the same tasks.
V. EVALUATION
In this paper, we assume that the initial public views of
the collaborative processes are compatible with each others
and that each private view is consistent with the respective
behavioral interface definition (i.e., the local choreography
model). We further assume the well-behavedness of the change
operation in terms of structure and semantics. In [11], the
authors distinguish between structural and behavioral compat-
ibility.
•Structural compatibility requires that for every message
that may be sent, the corresponding interaction partner is
able to receive it. In turn, for every message that can be
received, the corresponding partner must be able to send
such a message
•Behavioral compatibility considers behavioral dependen-
cies (i.e., control flow) between different message ex-
changes within one conversation.
In our propagation mechanism, structural compatibility is
preserved. Indeed, according to the change operation type,
for each affected partner we add, update, or remove the
complement of what has been changed in the modified process
(cf. Lemma 1). This means that for each send pattern in one
source partner there is the corresponding receive pattern with
the expected attributes in the process of the target partner.
Now, consider (δ, πp)being the change operation to be
applied to process model πpand (δ, Lp)the inferred change
to be applied to the local view of p.∆is the set of inferred
changes from (δ, Lp) to be propagated to its directly affected
partners. For each affected partner pi,(δi,Li)represents the
inferred change operation to be propagated to its public view
(∆=∧i=1..n(δi,Li), where nis the number of affected
partners). Note that the number of inferred structural changes
is finite since we only consider propagations to direct partners.
In turn, changes that might have structural effects on other
partners (transitive relations) are propagated to them by their
direct partners.
If (δ, Lp)is invariant, i.e., it does not affect the behavioral
interface of p, consistency and compatibility are preserved
over the collaborative processes. In addition, since processes
as well as the changed fragments are structured, consistency
and compatibility relations are reduced to those between the
fragments affected by the change.
•The INSERT pattern augments the process models of
the partners affected by the change with new activities.
Further, it does not affect the structural or behavioral
relations between the existing activities. However, some
direct precedence relations may be transformed into tran-
sitive ones. The decomposition of the INSERT pattern
results only in INSERT patterns in the public views of the
affected partners. According to one partner, the insertion
is done with respect to the direct and transitive dependen-
cies with the activities of the same partner. As explained
in Section IV, if Frepresents the fragment to be inserted
in Lp,abstri(F)is the fragment to be inserted in Li.
The latter has the same behavior as abstri(F)in terms of
control flow. Besides, the insertion position is computed
according to the transitive preset and postset of Fiwith
respect to partner i. This conserves the order between the
fragments and ensures the behavioral compatibility after
the propagation of the INSERT operation.
•The DELETE pattern reduces the process models of the
affected by the change. The reduction is done in a sym-
metric way on both sides: pand the partners affected. The
deletion of an activity on one side results in the deletion
of the corresponding aon the other side. Structural and
behavioral compatibilities are kept. However, this might
result in some issues, i.e., an activity might wait for a data
that would never arrive or send a message that might not
be used. The solution proposed in Section IV treats a set
of use cases where the correlated interactions are updated
or deleted accordingly. This does not affect structural and
behavioral compatibility of the propagation.
•As described, the propagation of the REPLACE pattern
results in three scenarios; insert, delete, or merge. The
merge may reduce or augment the target models of the
affected partners. Assume that the merge function γis
correct and idempotent and that it conserves the behavior
of the merged fragments. We consider Fiand F0
ias
the fragments to be merged. Then, the behavior of Fi
is included in the merge result γ(Fi,F0
i), which is also
compatible with the behavior of p(changed process) since
we merge the abstraction of the changed fragment (cf.
Lemma 1).
The consistency between the public views and the private
ones of the processes of the affected partners is checked if
the negotiations succeed. Each affected partner must adapt its
private process with respect to its modified public view. Using
consistency rules, each partner can then check locally whether
its local process model is consistent with its behavioral inter-
face. More details about consistency checking and validation
in choreographies can be found in [1], [8].
VI. RELATED WORK
[19] proposes four transfer rules to deal with dynamic
changes of distributed business processes. These rules use pro-
jection/protocol and lifecycle inheritance relations and check
whether a changed process is a subclass of the original one.
The suggested method only allows for changes that preserve
inheritance transformation rules, i.e., changes having internal
effects. Therefore, there is neither a need for change propa-
gation nor new agreement on the global protocols since only
inheritance-conforming changes are allowed. By contrast, our
method supports changes that affect the external behavior of a
process, and computes and propagates the respective changes
to the affected partners according to a negotiation phase.
In [7], the authors consider change propagation in decen-
tralized orchestrations where a centralized process model is
split into several distributed partitions. They mainly prop-
agate change operations made on the centralized model to
the respective derived decentralized partitions. They use the
decentralization function to compute the affected partitions and
infer the respective changes to the private and public views.
One organization controls the centralized and decentralized
models. Hence, it is easier to exactly compute the affected
regions and the changes to be applied. This is different from
the current work since changes are made by one partner
participating in the choreography and then propagated to the
other partners. In this work, we consider fully distributed
processes where no partner holds informations about another
partner’s private view (no centralized process model). Each
partner can only see the public parts of the other partners.
This leads to a negotiation phase between the affected partners
and could have transitive structural and semantical effects.
In contrast with the cited paper, in this work we take into
consideration the semantic issues (transitivity). This problem
is not considered when we propagate from a centralized to
its decentralized partitions since the changes are made on the
centralized model and considered to be correct. An approach
similar to [7] is also presented in [20].
In [4], the authors present DYCHOR, a framework address-
ing the challenge of change propagation in choreographies.
Changes are classified into additive and subtractive, and may
have variant or invariant impact on the interactions. DYCHOR
uses annotated finite state automata to model choreographies
and employs a set of operators to compute the changes to
be propagated. In our work, we propose four change patterns
which deal with more complex fragments instead of single
activities only. This leads to new challenges concerning se-
mantical or structural transitivity effects as well as negotiations
with the partners affected by the change. We sketched several
semantic transitive effects as well as the solutions to deal
with them. The model adopted in this paper makes change
propagation more easier since process models are structured
and only changed regions are affected. Hence, there is no
need for re-computing the whole public views of the processes
of affected partners, instead only the affected regions are
modified.
In [21], the authors address the problem of dynamic changes
and particularly version management of process models. In the
same context in [22], the authors propose an ontology based
framework for decentralized workflow change management
and define migration rules to adapt to changes in a dynamic
way. In [23], the authors deal with change propagation be-
tween semantically overlapping process models for which
elementary and complex correspondences have been identified.
All these approaches are different but complementary to our
work.
VII. CONCLUSION, DISCUSSION,AND OUTLOOK
This paper provides algorithms for propagating process
changes in collaborative scenarios involving multiple partners.
To stay independent of a particular process specification lan-
guage, RPST is used to define local and global choreogra-
phy models. The proposed propagation algorithms consider
typical process change patterns such as INSERT, DELETE,
REPLACE, and UPDATE, and are evaluated based on their
structural and behavioral compatibility.
Certain assumptions are made in this paper. First, the
proposed algorithms consider the application of one change
pattern at a time. However, in practical scenarios, several
change patterns might be applied in a combined manner
within a change transaction. To incorporate such complex
changes, optimizations on the change transactions as suggested
in [24] can be utilized to calculate the actual effects of
the change transaction. Second, change propagation might
become necessary in a transitive way, i.e., several partners
might be affected. This can be handled by applying the
change propagation procedure depicted in Fig. 4 in an iterative
way. However, it must be considered whether the transitive
propagation becomes cyclic. In this case, mechanisms such
as upper bounds on the number of iterations of propagating
changes including rollback mechanisms are conceivable.
Currently, we are integrating change propagation algorithms
into our cloud-based process execution engine CPEE (cpee.
org). We aim at testing and applying the proposed algorithms
in case studies, for example, within the automotive domain.
REFERENCES
[1] F. Casati, S. Ceri, B. Pernici, and G. Pozzi, “Workflow evolution,” Data
and Knowledge Engineering, vol. 24, no. 3, pp. 211–238, 1998.
[2] S. Rinderle, M. Reichert, and P. Dadam, “Correctness criteria for
dynamic changes in workflow systems: a survey.” Data and Knowledge
Engineering, vol. 50, no. 1, pp. 9–34, 2004.
[3] M. Reichert and B. Weber, Enabling Flexibility in Process-Aware
Information Systems - Challenges, Methods, Technologies. Springer,
2012.
[4] S. Rinderle, A. Wombacher, and M. Reichert, “Evolution of process
choreographies in DYCHOR,” in CoopIS’06. LNCS, 2006, pp. 273–290.
[5] S. Rinderle, B. Weber, M. Reichert, and W. Wild, “Integrating process
learning and process evolution - a semantics based approach,” in Int’l
Conference Business Process Management, 2005, pp. 252–267.
[6] S. Rinderle, M. Reichert, and P. Dadam, “Flexible support of team
processes by adaptive workflow systems.” Distributed and Parallel
Databases, vol. 16, no. 1, pp. 91–116, 2004.
[7] W. Fdhila, A. Baouab, K. Dahman, C. Godart, O. Perrin, and F. Charoy,
“Change propagation in decentralized composite web services,” in
CollaborateCom, 2011, pp. 508–511.
[8] F. M. Besson, P. M. Leal, and F. Kon, “Towards verification and valida-
tion of choreographies,” Department of Computer Science - University
of So Paulo, technical research report, 2011.
[9] J. Vanhatalo, H. Vlzer, and J. Koehler, “The refined process structure
tree,” in Business Process Management, vol. 5240, 2008, pp. 100–115.
[10] B. Weber, M. Reichert, and S. Rinderle-Ma, “Change patterns and
change support features - enhancing flexibility in process-aware infor-
mation systems.” Data and Knowledge Engineering, vol. 66, no. 3, pp.
438–466, 2008.
[11] G. Decker and M. Weske, “Behavioral consistency for B2B process
integration,” in CAiSE. Springer, 2007, pp. 81–95.
[12] A. Barros, M. Dumas, and P. Oaks, “Standards for web service choreog-
raphy and orchestration: Status and perspectives,” in Business Process
Management Workshops. Springer. LNCS, 2006, vol. 3812, pp. 61–74.
[13] A. Polyvyanyy, L. Garcia-Banuelos, and M. Dumas, “Structuring acyclic
process models,” Information Systems, vol. 37, no. 6, pp. 518–538, 2012.
[14] R. Milner, M. Tofte, and D. Macqueen, The Definition of Standard ML.
Cambridge, MA, USA: MIT Press, 1997.
[15] B. F. van Dongen, W. M. P. van der Aalst, and H. M. W. Verbeek,
“Verification of EPCs: Using reduction rules and petri nets,” in CAiSE.
Springer, 2005, pp. 372–386.
[16] R. Dijkman, “Diagnosing Differences between Business Process Mod-
els,” in Proceedings of the 6th Int’l Conference on Business Process
Management (BPM 2008). Springer, LNCS, 2008, pp. 261–277.
[17] M. L. Rosa, M. Dumas, R. Uba, and R. M. Dijkman, “Business process
model merging : An approach to business process consolidation,” ACM
Transactions on Software Engineering and Methodology, 2012.
[18] F. Gottschalk, W. M. Aalst, and M. H. Jansen-Vullers, “Merging event-
driven process chains,” in OTM ’08. Springer, 2008, pp. 418–426.
[19] W. M. P. van der Aalst and T. Basten, “Inheritance of workflows: an
approach to tackling problems related to change,” Theor. Comput. Sci.,
vol. 270, no. 1-2, pp. 125–203, 2002.
[20] M. Reichert and T. Bauer, “Supporting ad-hoc changes in distributed
workflow management systems.” in CoopIS’07, vol. 4803. Springer,
2007, pp. 150–168.
[21] J. M. K¨
uster, C. Gerth, and G. Engels, “Dynamic computation of
change operations in version management of business process models,”
in ECMFA’10. Springer, 2010, pp. 201–216.
[22] V. Atluri and S. A. Chun, “Handling dynamic changes in decentralized
workflow execution environments,” in DEXA’03, 2003, pp. 813–825.
[23] M. Weidlich, J. Mendling, and M. Weske, “Propagating changes between
aligned process models,” Journal of Systems and Software, vol. 85, no. 8,
pp. 1885 – 1898, 2012.
[24] S. Rinderle, M. Reichert, M. Jurisch, and U. Kreher, “On representing,
purging, and utilizing change logs in process management systems,” in
Business Process Management, 2006, pp. 241–256.
