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.