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.
Product/Language |
Version |
Score |
Motivation |
---|---|---|---|
Staffware | 10 | - | Not supported. The wait step synchronizes flows and all other steps get enabled after receiving the first trigger. |
Websphere MQ | 3.4 | + | Supported by specifying start conditions on an activity. |
FLOWer | 3.51 | + | Supported inside static, dynamic and sequential subplans. Each plan model is directed acyclic graph of nodes representing various plan elements and actions. Nodes with multiple incoming arcs wait for their predecessors to be completed or skipped (called "refused"). If all preceding nodes are skipped or all incoming arcs have a guard evaluating to false, a node is skipped. Otherwise normal processing is resumed. Note that the approach is similar to passing true and false tokens. True tokens correspond to arcs that evaluate to true and get triggered by completed nodes. False tokens correspond to arcs that evaluate to false or arcs that are skipped (i.e., the preceding node is "refused"). The join semantics is that if a node has at least one true token as input it becomes enabled. If all input tokens are false it is skipped (i.e., labeled as "refused"). |
COSA | 5.1 | - | Processes are not inherently structured. |
iPlanet | 3.0 | - | Not supported. Process models are not necessarily structured. |
SAP Workflow | 4.6c | - | Not supported for two reasons. First of all, it is not possible to create optional parallel branches other than explicitly skipping the branches that are not selected. Second, the join construct of a fork is unaware of the number of truly active branches. Therefore, any Synchronizing merge needs to be rewritten as a mix of forks and conditions. |
FileNet | 3.5 | + | Directly supported by a collector step used a join in the structure. |
BPEL | 1.1 | + | Supported by links within the <flow> construct. |
Websphere Integration Developer | 6.0 | + | Supported by links within the <flow> activity. |
Oracle BPEL | 10.1.2 | + | Supported by links within a <flow> construct. |
BPMN | 1.0 | + | Supported through the OR-join gateway. |
XPDL | 2.0 | + | Supported by the OR-join construct. |
UML ADs | 2.0 | - | Not supported. The specific configuration of the Join-Spec condition to achieve this is unclear. |
EPC (implemented by ARIS toolset 6.2) | + | Supported by the OR-join connector. However, as described in [Kin06], the OR-join connector creates a paradox when combined with loops (i.e. the "vicious circle"). The desirable semantics would be to wait until no new folder can reach the OR-join. However, one connector may depend on the other and vice versa. The ARIS simulator uses a rather odd solution for this dilemma: the OR-join connector has a time-out mechanism attached to it. The join waits for a prespecified time and then consumes all folders that are there. | |
jBPM | 3.1.4 | - | jBPM does not support it, as it does not support multi choice, which is a prerequisite for this pattern. |
OpenWFE | 1.7.3 | - | OpenWFE does not support it, as it does not fully support multi choice, which is a prerequisite for this pattern. |
Enhydra Shark | 2 | - | Enhydra Shark does not directly support this pattern. Shark provides a workaround solution in which the behaviour is achieved by introducing an XOR split for each outgoing branch of the corresponding OR-split where a choice is made between executing this branch or not. Each XOR-split has a corresponding XOR-join and all these XOR-joins are linked to an AND-join which achieves the required synchronization (See Figure 1) |