OR-join semantics in YAWL

Workflow languages offer constructs for coordinating tasks. Among these constructs are various types of splits and joins. One type of join, which shows up in various incarnations, is the OR-join. Different approaches assign a different (often only intuitive) semantics to this type of join, though they do share the common theme that synchronisation is only to be performed for active threads. Depending on context assumptions this behaviour may be relatively easy to deal with, though in general its semantics is complicated, both from a definition point of view (in terms of formally capturing a desired intuitive semantics) and from a computational point of view (how does one determine whether an OR-join is enabled?).

Semantics - When is an OR-join task enabled?

An OR-join is used in situations when we need to model "wait and see" behaviour for synchronisation.

Consider a scenario where a telecommunication company provides home phone, internet and mobile services. A customer can select one, all three or any combination of two of these services. Depending on the service bundle selected, a discounted monthly price is calculated.

Figure 1: A YAWL net with an OR-split and an OR-join

In a process model, this can be represented by a customer registration task, followed by three individual tasks to sign up for different services (which can be done in any order), and finally price calculation task (see Figure 1). As it is possible for multiple services to be selected, we need a synchronising point before price calculation task. If that synchronising point is modelled as an AND-join, it is clear that the process cannot continue (i.e., deadlock) for a customer who decides not to subscribe to all three services. If it is modelled as an XOR-join (no synchronisation), the price calculation task would be performed multiple times, if a customer selects more than one service.

Therefore, there is a need for a more sophisticated synchronisation construct that is ``intelligent" enough to determine when certain activities should be synchronised and when the subsequent activity should go ahead. In this example, an OR-join waits for synchronisation if the customer has selected more than one service and carries out price calculation without delay if the customer has selected only one service.

Informal semantics

• Full synchronisation: There is at least a token each in all of the input conditions of an OR-join task . In Figure 1, there is at least one token each in conditions c4, c5 and c6.
• Partial synchronisation: If there is at least one token in one of its input conditions and it is not possible for more tokens to arrive in other (currently empty) input conditions in the future states (i.e, there is no need to wait/synchronise). In Figure 1, if a customer only selects home phone service (c4), then there is no need to synchronise.

On the other hand, consider a scenario where a customer decides on taking up home phone and internet subscriptions: i.e., a token each in c1 and c2. At the state where the home phone subscription is completed but internet subscription is not (a token in c4 and a token in c2), then the OR-join task is not enabled. Only at the state where both subscription tasks are complete (a token each in c4 and c5), the OR-join task will go ahead.

An OR-join is not enabled (waits before proceeding) if it is possible for tokens to arrive in currently empty input conditions in the future states.

Even though the OR-join construct is useful in business process modelling, its formal semantics are difficult to capture and to implement. The difficult question arises as to when an OR-join should wait for synchronisation and when it should go ahead. This decision cannot be made locally, that is, just by evaluating the current state of the workflow. The decision requires the awareness of the current state as well as possible future states of the workflow. One possible technique is to determine all possible future states of the workflow. This analysis becomes much more complicated when other complex control flow constructs such as cancellation, loops and multiple OR-joins are present in the process.

(Non-local) formal semantics

A general approach to OR-join semantics in the presence of cancellation features and without structural restrictions has been proposed in YAWL using reset net formalism. Reset nets are Petri-nets with reset arcs. A reset arc removes all tokens from a place when its transition fires. Through the behaviour of reset arcs, the behaviour of cancellation regions can be captured in a natural manner.

Characteristics of the OR-join semantics

• General: no syntactical restriction and closely matches the intuitive semantics
• Formal: the semantics is defined using reset nets formalism and decided using backwards coverability algorithm
• Decidable: the algorithm is applicable for workflows with cancellation, multiple OR-joins and loops

Multiple OR-joins

The informal semantics of an OR-join can be supported quite well when there is only one OR-join in a given net. However, when dealing with multiple OR-joins where one precedes the other, the semantics is not well-defined. The question arises as to ``how to treat other OR-joins in the workflow while we try to decide whether one OR-join should be enabled?".

Instead of ignoring other OR-join tasks during the analysis, two alternative treatments have been proposed for those OR-joins:

• XOR-joins (optimistic): It is considered optimistic as the analysis waits for synchronisation if the resulting XOR-join can be enabled.
• AND-joins (pessimistic): The treatment of an OR-join on the path to another OR-join as an AND-join is a pessimistic approach, as this approach now requires tokens in all input conditions of the AND-join and if it is not possible, the OR-join will be enabled.

In the YAWL implementation, the optimistic approach has been used as the treatment of other OR-joins as XOR-joins allows the most delay for possible synchronisation. The resulting OR-join semantics is well-defined in every circumstance. However, the interpretation of this semantics can sometime lead to a deadlock in the presence of vicious circles (see below) as both OR-joins will wait for each other to fire first.

A note on vicious circles

When OR-joins are in conflict, where both OR-joins are only waiting for each other to fire first so that they can become enabled, there is no satisfactory treatment for multiple OR-joins. As mentioned before, the XOR-join treatment during the analysis will result in deadlock.

Implementation

The proposed semantics has been implemented as part of a workflow environment together with two restriction techniques to improve the performance of the algorithm. As a YAWL net with OR-join tasks is translated into a reset net for OR-join analysis, the optimisation operations are also performed on the reset net.

Optimisation techniques

For an OR-join analysis, 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 behaviour. 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 conditions that could not be enabled from a given marking. Active projection enables us to stop exploring those parts of the net that can never be reached from a given marking.