Pattern 7 (Structured Synchronizing Merge)

FLASH animation of Structured Synchronizing Merge pattern

Description

The convergence of two or more branches (which diverged earlier in the process at a uniquely identifiable point) into a single subsequent branch such that the thread of control is passed to the subsequent branch when each active incoming branch has been enabled. The Structured Synchronizing Merge occurs in a structured context, i.e. there must be a single Multi-Choice construct earlier in the process model with which the Structured Synchronizing Merge is associated and it must merge all of the branches emanating from the Multi-Choice. These branches must either flow from the Structured Synchronizing Merge without any splits or joins or they must be structured in form (i.e. balanced splits and joins).

Synonyms

Synchronizing join, synchronizer.

Examples

Depending on the type of emergency, either or both of the despatch-police and despatch-ambulance tasks are initiated simultaneously. When all emergency vehicles arrive at the accident, the transfer-patient task commences.

Motivation

The Structured Synchronizing Merge pattern provides a means of merging the branches resulting from a specific Multi-Choice (or OR-split) construct earlier in a process into a single branch. Implicit in this merging is the synchronization of all of the threads of execution resulting from the preceding Multi-Choice.

Overview

As already indicated, the Structured Synchronizing Merge construct provides a means of merging the branches from a preceding Multi-Choice construct and synchronizing the threads of control flowing along each of them. It is not necessary that all of the incoming branches to the Structured Synchronizing Merge are active in order for the construct to be enabled, however all of the threads of control associated with the incoming branches must have reached the Structured Synchronizing Merge before it can fire.

One of the difficulties associated with the use of this pattern is knowing when the Structured Synchronizing Merge can fire. The Structured Synchronizing Merge construct must be able to resolve the decision based on local information available to it during the course of execution. Critical to this decision is knowledge of how many branches emanating from the preceding Multi-Choice are active and require sychronization. This is crucial in order to remove any potential for the "vicious circle paradox" [Kin06] to arise where the determination of exactly when the merge can fire is based on non-local semantics which by necessity includes a self-referencing definition and makes the firing decision inherently ambiguous.

Addressing this issue without introducing non-local semantics for the Structured Synchronizing Merge can be achieved in several ways including (1) structuring of the process model following a Multi-Choice such that the subsequent Structured Synchronizing Merge will always receive precisely one trigger on each of its incoming branches and no additional knowledge is required to make the decision as to when it should be enabled, (2) by providing the merge construct with knowledge of how many incoming branches require synchronization and (3) by undertaking a thorough analysis of possible future execution states to determine when the Synchronizing Merge can fire.

The first of these implementation alternatives forms the basis for this pattern and is illustrated in Figure 7. The assumption associated with this alternative is that the merge construct always occurs in a structured context, i.e. it is always paired with a distinct preceding Multi-Choice. It is interesting to note that the combination of the Structured Synchronizing Merge and the preceding Multi-Choice (together with the intervening tasks) forms a structured component that is compositional in form and can be incorporated in other structured processes whilst retaining the overall structural form. This approach involves adding an alternate "bypass" path around each branch from the multi-merge to the Structured Synchronizing Merge which is enabled in the event that the normal path is not chosen. The "bypass" path is merged with the normal path for each branch prior to the Structured Synchronizing Merge construct ensuring that it always gets a trigger on all incoming branches and can hence be implemented as an AND-join construct.

Figure 7: Structured synchronizing merge pattern

The second implementation alternative forms the basis for the Local Synchronizing Merge (WCP37) pattern. It can be facilitated in several distinct ways. One option [Rit99] is based on the immediate communication from the preceding Multi-Choice to the Local Synchronizing Merge of how many branches require synchronization. Another option (illustrated in Figure 8) involves the introduction of true/false tokens following a multi-merge indicating whether a given branch has been chosen or not.

Figure 8: Local synchronizing merge pattern

The third implementation alternative - undertaking a complete execution analysis to determine when the merge construct should be enabled - forms the basis for the General Synchronizing Merge (WCP38) pattern.

Context

There are two context conditions associated with the use of this pattern: (1) once this Structured Synchronizing Merge has been activated and has not yet been reset, it is not possible for another signal to be received on the activated branch or for multiple signals to be received on any incoming branch. In other words, all input places to the Structured Synchronizing Merge (i.e. p4 and p5) are safe and (2) once the Multi-Choice has been enabled none of the tasks in the branches leading to the Structured Synchronizing Merge can be cancelled before the merge has been triggered. The only exception to this is that it is possible for all of the tasks leading up to the Structured Synchronizing Merge to be cancelled.

Implementation

The Structured Synchronizing Merge can be implemented in any process language which supports the Multi-Choice construct and can satisfy the context conditions discussed above. It is directly supported in WebSphere MQ, FLOWer, FileNet, BPMN, BPEL, XPDL and EPCs.

Issues

One consideration that arises with the implementation of the OR-join is providing a form that is able to be used in arbitrary loops and more complex process models which are not structured in form. The Structured Synchronizing Merge cannot be used in these contexts.

Solutions

Both the Local Synchronizing Merge (WCP37) and the General Synchronizing Merge (WCP38) are able to be used in unstructured process models. The latter is also able to be used in arbitrary loops. The Local Synchronizing Merge tends to be more attractive from an implementation perspective as it is less computationally expensive than the General Synchronizing Merge.

Evaluation Criteria

Full support for this pattern in an offering is evidenced by the availability of a construct which when placed in the proper context will synchronize all active threads emanating from the corresponding Multi-Choice.

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.