Pattern 9 (Structured Discriminator)

FLASH animation of Structured Discriminator pattern

Description

The convergence of two or more branches into a single subsequent branch following a corresponding divergence earlier in the process model such that the thread of control is passed to the subsequent branch when the first incoming branch has been enabled. Subsequent enablements of incoming branches do not result in the thread of control being passed on. The Structured Discriminator construct resets when all incoming branches have been enabled. The Structured Discriminator occurs in a structured context, i.e. there must be a single Parallel Split construct earlier in the process model with which the Structured Discriminator is associated and it must merge all of the branches emanating from the Structured Discriminator. These branches must either flow from the Parallel Split to the Structured Discriminator without any splits or joins or they must be structured in form (i.e. balanced splits and joins).

Synonyms

1-out-of-M join.

Examples

When handling a cardiac arrest, the check_breathing and check_pulse tasks run in parallel. Once the first of these has completed, the triage task is commenced. Completion of the other task is ignored and does not result in a second instance of the triage task.

Motivation

The Structured Discriminator pattern provides a means of merging two or more distinct branches in a process into a single subsequent branch such that the first of them to complete results in the subsequent branch being triggered, but completions of other incoming branches thereafter have no effect on (and do not trigger) the subsequent branch. As such, the Structured Discriminator provides a mechanism for progressing the execution of a process once the first of a series of concurrent tasks has completed.

Overview

The operation of the Structured Discriminator pattern is illustrated in Figure 10. The () notation indicates a simple untyped token. Initially there is such a token in place p2 (which indicates that the Discriminator is ready to be enabled). The first token received at any of the incoming places i1 to im results in the Discriminator being enabled and an output token being produced in output place o1. An untyped token is also produced in place p3 indicating that the Structured Discriminator has fired but not yet reset. Subsequent tokens received at each of the other input places have no effect on the Structured Discriminator (and do not result in any output token in place o1). Once one token has been received each input place, the Structured Discriminator resets and can be re-enabled once again. This occurs when m-1 tokens have accumulated at place p1 allowing the reset transition to be enabled. Once again, the combination of the Structured Discriminator and the preceding Parallel Split can also be considered as a structured component that is compositional in form and can be incorporated in other structured processes whilst retaining the overall structural form.

Figure 10: Structured discriminator pattern

There are two possible variants of this pattern that can be utilized in non-structured contexts. Both of which improve the applicability of the Structured Discriminator pattern whilst retaining its overall behaviour. First, the Blocking Discriminator (WCP28) removes the requirement that each incoming branch can only be enabled once between Structured Discriminator resets. It allows each incoming branch to be triggered multiple times although the construct only resets when one triggering has been received on each input branch. It is illustrated in Figure 11.

Figure 11: Blocking discriminator pattern

The second alternative, the Cancelling Discriminator (WCP29), improves the efficiency of the pattern further by preventing any subsequent tasks in the remaining incoming branches to the Cancelling Discriminator from being enabled once the first branch has completed. Instead the remaining branches are effectively put inot a "bypass mode" where any remaining tasks are "skipped" hence expediting the reset of the construct. It is illustrated in Figure 12.

Figure 12: Cancelling discriminator pattern

Context

There are two context conditions associated with the use of this pattern: (1) once the Structured Discriminator 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 paces to the Structured Discriminator (i.e. i1 to im) are safe and (2) there is a corresponding Parallel Split and once this has been enabled none of the tasks in the branches leading to the Structured Discriminator can be cancelled before it has been triggered. The only exception to this is that is it possible for all of the tasks leading up to the Structured Discriminator to be cancelled. It is interesting to note that a corollary of these context criteria is that correct behaviour of the pattern is assured and relies only on local information available to the Structured Discriminator at runtime.

Implementation

The Structured Discriminator can be directly implemented in iPlanet by specifying a custom trigger condition for a task with multiple incoming routers which only fires when the first router is enabled. BPMN and XPDL potentially support the pattern with a COMPLEX-Join construct however it is unclear how the IncomingCondition for the join is specified. UML 2.0 ADs shares a similar problem with its JoinNode construct. SAP Workflow provides partial support for this pattern via the fork construct although any unfinished branches are cancelled once the first completes.

Issues

One issue that can arise with the Structured Discriminator is that failure to receive input on each of the incoming branches may result in the process instance (and possibly other process instances) stalling.

Solutions

The alternate versions of this pattern provide potential solutions to the issue. The Blocking Discriminator allows multiple execution threads in a given process instance to be handled by a single Discriminator (although a subsequent thread can only trigger the construct when inputs have been received on all incoming branches and the Blocking Discriminator has reset). The Cancelling Discriminator only requires the first thread of control to be received in an incoming branch. Once this has been received, the remaining branches are effectively put into "bypass" mode and any remaining tasks in those branches that have not already been commenced are skipped (or cancelled) allowing the discriminator to be reset as soon as possible.

Evaluation Criteria

Full support for this pattern is demonstrated by any offering which provides a construct which satisfies the description when used in a context satisfying the context assumptions. It rates as partial support if the Structured Discriminator can reset without all tasks in incoming branches having run to completion.

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.
Websphere MQ 3.4 - Not supported. The evaluation of start conditions for an activity only occurs when all preceding activities have completed.
FLOWer 3.51 - Not supported. Dynamic subplans can have an auto complete condition however this is only evaluated when all subplans have completed.
COSA 5.1 - The discriminator can be modelled by using true conditions in input arcs and extending the network. Unfortunately, the resulting diagram is too complex.
iPlanet 3.0 + Supported through the use of a customised trigger condition for an activity that only fires when the first incoming router is activated.
SAP Workflow 4.6c +/- This is supported by the fork construct which allows for the specification of the number of branches that needs to be complete or some other end condition, i.e. a fork can start 10 branches and terminate 9 branches upon completion of the first branch. Note that all remaining branches are cancelled hence this construct only achieves partial support.
FileNet 3.5 - Not supported: no means for resetting are available.
BPEL 1.1 - Not supported. There is no dedicated language construct and links cannot be used in conjunction with an OR joinCondition as the join requires the status of all incoming links to be known before evaluation, not just the identification of the first positive link.
Websphere Integration Developer 6.0 - Not supported. There is no dedicated language construct and links cannot be used in conjunction with an OR joinCondition as the join requires the status of all incoming links to be known before evaluation, not just the identification of the first positive link.
Oracle BPEL 10.1.2 - Not supported. There is no dedicated language construct and links cannot be used in conjunction with an OR joinCondition as the join requires the status of all incoming links to be known before evaluation, not just the identification of the first positive link.
BPMN 1.0 +/- Although support for this pattern is referred to in the BPMN 1.0 specification, it is unclear how the IncomingCondition expression on the COMPLEX-join gateway is specified.
XPDL 2.0 +/- Although the COMPLEX-join gateway appears to offer support for this pattern, it is unclear how the IncomingCondition expression is specified.
UML ADs 2.0 +/- The specific configuration of the Join-Spec condition to achieve this is unclear.
EPC (implemented by ARIS toolset 6.2) - Not supported as there is no notion of ignoring subsequent folders and then resetting.
jBPM 3.1.4 - jBPM does not support this pattern
OpenWFE 1.7.3 + OpenWFE supports structured discriminator through the <concurrence> construct with the attribute settings count = "1" and remaining = "forget".
Enhydra Shark 2 - Enhydra Shark does not directly support this pattern. A work around implementing the behaviour of the pattern is proposed in (Shark), see Figure 3.