Page 122 -

3 Advanced Synchronization 109
for a given OR-join should treat other OR-joins. Second, for workflows with infinite
loops (e.g., a continuous monitoring activity), the state space of a sound process
could potentially be infinite. Third, cancelation regions complicate the computation
of future states. A task that an OR-join is waiting for, that is, in the cancelation
region of some other task, may or may not be disabled. Such considerations make
state space analysis computationally expensive.

3.3.1 Different Interpretations and Implementations
of an OR-Join

Even though the OR-join construct is useful in process modeling, its formal seman-
tics are difficult to capture and to implement. Different approaches assign a different
(often only intuitive) semantics to this type of join, although they do share the com-
mon theme that synchronization is only to be performed for the active paths that are
being executed in a given workflow instance.
The Business Process Modeling Notation (BPMN) contains an OR-join like con-
struct called the inclusive OR-join gateway. The semantics of the OR-gateway in
BPMN 1.0 is given in the specification as “it will wait for (synchronize) all Tokens
that have been produced upstream. If an upstream Inclusive OR produces two out
of a possible three Tokens, then a downstream Inclusive OR will synchronize those
two Tokens and not wait for another Token, even though there are three incoming
Sequence Flow.” Note that Wohed et al. have argued that the OR-join gateway does
not capture the correct behavior for unstructured BPMN models. It is challenging to
select a suitable OR-join semantics and to implement it efficiently.
Several proposals have been put forward to formally define a semantics of
OR-joins in Event-driven Process Chains (EPCs) without introducing syntactic
restrictions. Van der Aalst et al. highlighted problems associated with the OR-
join semantics, especially those of vicious circles. It was suggested that any formal
OR-join semantics will impose some restrictions or will deviate from the informal
semantics to some extent. This led to a proposal by Kindler to define a nonlocal
semantics in EPCs (including the OR-join) in terms of a pair of transition relations
using techniques from fixed point theory. Their semantics can then be considered
as more general and precise. This approach is forward looking in determining when
an OR-join can fire as it generates the entire set of reachable states. Therefore, a
deadlock situation can be detected before it happens.
Many workflow systems also struggle with the semantics and implementation
of the OR-join. This is because its non-local semantics requires a synchronization
depending on an analysis of future execution paths, which requires some non-trivial
reasoning. Workflow management systems like InConcert, eProcess, and Web-
Sphere MQ Workflow have solved problems related to the OR-join using syntactical
restrictions. IBM WebSphere MQ Workflow (used as a basis for the BPEL standard)
appears to offer full support for the OR-join for acyclic workflows. Other systems
like Eastman and Domino Workflow also support an OR-join concept with non-local