Pattern 38 (General Synchronizing Merge)

FLASH animation of General Synchronizing Merge pattern

Description

The convergence of two or more branches which diverged earlier in the process into a single subsequent branch such that the thread of control is passed to the subsequent branch when either (1) each active incoming branch has been enabled or (2) it is not possible that any branch that has not yet been enabled will be enabled at any future time.

Examples

Figure 56 provides an example of the General Synchronizing Merge pattern. It shares a similar fundamental structure to the examples presented in Figures 7 and 55 for the other forms of OR-join however the conditional feedback path from p4 to p1 involving F (which effectively embeds a "loop" within the process where cond3 evaluates to true) means that it is not possible to model it either in a structured way or to to use local information available to E to determine when the OR-join should be enabled.

Figure 56: General Synchronizing merge pattern

Motivation

This pattern provides a general approach to the evaluation of the General Synchronizing Merge (or OR-join) in process. It is able to be used in non-structured and highly concurrent processes including process models that include arbitrary looping structures.

Overview

This pattern provides general support for the OR-join construct that is widely utilised in modelling languages but is often only partially implemented or severely restricted in the form in which it can be used. The difficulty in implementing the General Synchronizing Merge stems from the fact that its evaluation relies on non-local semantics [vdADK02] in order to determine when it can fire. In fact it is easy to see that this construct can lead to the "vicious circle paradox" [Kin06] where two OR-joins depend on one another.

The OR-join can only be enabled when the thread of control has been received from all incoming branches and it is certain that the remaining incoming branches which have not been enabled will never be enabled at any future time. Determination of this fact requires a (computationally expensive) evaluation of possible future states for the current process instance.

Context

There are no specific context conditions associated with this pattern.

Implementation

FileNet is the only offering examined to support this pattern. An algorithm describing an approach to implementing the General Synchronizing Merge based on Reset-Nets is described in [WEvdAtH05] and has been used as the basis for the OR-join construct in the YAWL reference implementation [vdAtH05].

Issues

There are three significant issues associated with this pattern: (1) when determining whether an OR-join should be enabled in a given process instance, how should composite tasks which precede the OR-join be considered, (2) how should preceding OR-joins be handled and (3) how can the performance implications of OR-join evaluation (which potentially involves a state space analysis for the case in which the OR-join appears) be addressed.

Solutions

Solutions to all of these problems are described in [WEAH05]. It provides a deterministic means of evaluating whether an OR-join should be enabled based on an evaluation of the current execution state of preceding tasks. It considers composite tasks to function in the same way as atomic tasks - i.e. they are either enabled or not, - and there is no further consideration of the execution specifics of the underlying subprocess. Moreover it is assumed that they will continue executing and pass the thread of control onto subsequent tasks when complete. In terms of the second issue, any preceding OR-joins are all considered to function either as XOR-joins or AND-joins when determining if the task with which they are associated can be enabled. By doing this, the "vicious circle" problem is avoided. It also offers some potential solutions to the third issue involving the use of reduction rules which limit the size of the state space evaluation required in order to establish whether the OR-join should be enabled.

Evaluation Criteria

An offering achieves full support if it provides a construct that satisfies the description for the pattern.

Product Evaluation

To achieve a + rating (direct support) or a +/- rating (partial support) the product should satisfy the corresponding evaluation criterion of the pattern. Otherwise a - rating (no support) is assigned.