Page 126 -

3 Advanced Synchronization 113
to the OR-join. We first check if M contains tokens for one or more conditions in
P i .If itis false, oj is not enabled at M. We also check if all conditions in P i are
marked. If so, oj is enabled at M and an unnecessary call to the expensive algorithm
is avoided. Otherwise, the following algorithm is invoked to determine whether oj
should be enabled at M .
The YAWL net is first converted into a reset net using the transformation rules
given in Sect. 3.2
A set of larger markings X that mark more input conditions in P i is generated
for the reset net. This set of markings represents possible enabling markings for
the OR-join
For each marking x in X, we generate a set of backwards coverable markings
X using the backwards firing rule for reset nets. If M (or a smaller marking)
0
is found in X , this indicates that it is possible to cover the marking x in future
0
reachable markings of M and hence, oj should wait to synchronize. In that case,
the algorithm returns FALSE
If M is not coverable by any of the markings generated by markings in X,then
the algorithm returns TRUE
As one can imagine, this algorithm could potentially be called multiple times for
a particular OR-join as the state of the workflow changes. Hence, it can become
very time consuming and may be intractable for YAWL nets with large state spaces.
Similarly, its efficiency becomes a major issue when running a workflow with poten-
tially millions of active cases. Next, we present two optimization techniques that can
dramatically speed up this analysis.

3.4.2 Optimization

When analyzing an OR-join to determine if it can be enabled, it is possible to
consider only a portion of the net that is relevant to the analysis and refrain from
exploring those paths that do not affect the OR-join enabling behavior. To improve
the performance of the OR-join evaluation algorithm, two forms of restriction are
proposed: structural restriction and active projection. Structural restriction involves
removing from a net tasks and conditions that are not on the path to the OR-join task
under consideration. Active projection involves removing tasks and associated con-
ditions that could not be enabled from a given marking. Hence, active projection
enables us to stop exploring those parts of the net that can never be reached from a
given marking. As a YAWL net with OR-join tasks is translated into a reset net for
OR-join analysis, the restriction operations are also performed on the reset net.

3.4.3 Worked Example

Throughout this chapter, several examples have been presented, which indicate that
it is a non-trivial task to decide if an OR-join is enabled or not. Clearly, the algorithm
can be applied successfully to these situations. To illustrate its inner working in