Single-transmission multilateral interaction patterns

Description. A party expects to receive one among a set of messages. These messages may be structurally different (i.e. different types) and may come from different categories of partners. The way a message is processed depends on its type and/or the category of partner from which it comes.

Synonyms. Racing messages.

Example.

• A manufacturing process involves remote subcontractors and uses a pull-strategy to streamline its operations. Each step in the manufacturing process is undertaken by a subcontractor. A subcontractor signals intention to execute a step when it becomes available through a request. At the same time, progress is monitored by a quality assurance service. The service randomly issues quality check requests in addition to the pre-established quality checkpoints in the process. When a quality check request arrives, it is processed in full before processing any new quality check request or subcontractor intention. Similarly, when a subcontractor intention arrives, it is processed in full before processing any other check request or subcontractor intention. Thus, there are points in the process where quality checks and subcontractor intentions compete.
• The escalation service of an insurance company's call center may receive storm alerts from a weather monitoring service (which typically herald surges in demand), notifications of long waiting times from the queue management service, or notifications of low resourcing levels from the call center's HR manager. The receipt of any of these three types of messages by the escalation service triggers an escalation process (different processes apply to the various types of notifications). While an escalation process is running, subsequent storm alerts, queue saturation or low resourcing notifications are made available to the call center manager but will not trigger new escalations.

Issues/design choices.

• The incoming messages may be of different types.
• The processing that follows the message consumption (which we term the continuation) may be different depending on the consumed message.
• When one of the expected messages is received, the corresponding continuation is triggered. The remaining messages may or may not need to be discarded.
• Depending on the underlying communication infrastructure, several of the expected messages may be simultaneously available for consumption. In this case, two approaches may be adopted: (i) let the system make a non-deterministic choice, or (ii) provide a "ranking" among the competing messages. In any case, only one message is chosen for consumption.

Solution. This pattern is directly captured by the pick activity in BPEL. The pick activity simultaneously enables the consumption of several types of message events and allows at most one message event to be consumed. Specifically, a pick activity is composed of multiple branches, each of which has a corresponding handler which acts as the trigger of the branch. Occurrences of message events are consumed by onMessage handlers. An onMessage handler is associated with a type of message, identified by a partner link and a WSDL operation. When a message of the type associated to an onMessage handler is available for consumption, a message event may occur which is then immediately consumed by the handler. The pick enforces that at most one of its associated onMessage handlers will consume an event. Note that it is also possible to associate a timer with a branch of a pick activity through an onAlarm handler. The corresponding branch is taken if the timeout event occurs before any of the other branches is taken.

In the current version of BPEL, it is not possible to express a ranking among the competing types of message event handlers under a given pick. Although in the concrete syntax of BPEL the handlers under a pick are ordered, this order is not significant. Hence, should there be several onMessage handlers able to consume message events when the pick activity is executed, the system may choose any of them non-deterministically. What is needed to capture the fourth issue of this pattern is a way of ranking message events so that when several of them enter into a race, the one with highest ranking is chosen.

Related pattern.

• Deferred choice (van der Aalst et al. 2003). The deferred choice pattern corresponds to a point in a process where one among a set of branches needs to be taken, but the choice is not made by the process execution engine (as in a "normal choice"). Instead, several alternatives are made available to the environment and the environment chooses one of these alternatives. The "competing receives" pattern can be seen as a specialization of the deferred choice where the choice of branch is determined by the receipt of a message.

Description. A party sends messages to several parties. The messages all have the same type (although their contents may be different).

Synonyms. Multicast, scatter [Snir & Gropp 1998].

Examples.

• A purchasing service sends a call for tender to all known trading parties that provide a given type of product or service.
• An accreditation authority sends a notification to all registered candidates who have passed a certification test. Each of these notifications contains information that is specific to the recipient (e.g. test results).

Issues/design choices.

• The number of parties to whom the message is sent may or may not be known at design time. In the extreme case, it may only be known just before the interaction occurs.
• As for the one-to-one send, reliable delivery may or may not be required. In the case of reliable delivery, the individual send actions may result in faults and thus fault handling routines should be associated to each of the individual send actions. The logic of these fault handlers is application-dependent: some applications may choose to terminate the whole one-to-many send when one of the individual "send actions" fail, while others may simply record the failures that occur and proceed.

Solution. A natural approach to address this pattern is to use the "one-to-one send" pattern described above as a basic building block. Thus, a number of one-to-one send actions are scheduled in parallel or sequentially depending on the capabilities of the underlying language. For example:

• In BPEL the individual send actions would have to be scheduled sequentially. This can be achieved through a while loop in which one message is sent at each iteration, with an associated fault handler if necessary. The sequential nature of this solution is problematic when the individual send actions are blocking, since the second and subsequent send actions need to wait for all the preceding ones to complete before starting. Note that if the number of parties is known at design time, it is possible to capture this pattern through a parallel block (i.e. a flow activity) such that each thread contains a one-to-one send action with its associated fault handler.
• In certain proprietary extensions of BPEL, such as Oracle BPEL, special constructs are provided to capture the situation where an arbitrary number of executions of a given activity need to be performed in parallel, such that this number is only determined when these parallel executions are started (see for example the FlowN construct in Oracle BPEL). The pattern can be directly captured using such a construct, whereby the activity given as paraemter to the construct is a send action and its associated fault handler if necessary. Note that two similar constructs (namely bundle and parallel foreach) have been proposed for introduction into the BPEL standard, but neither of these proposals has been adopted for various technical reasons (see Issues 4 and 147 in the list of issues available from the OASIS BPEL TC web page).
  
• In WSCI and BPML, a construct known as "spawn" is provided to start an instance of a sub-process asynchronously. By embedding the "spawn" within a "while" loop, it is possible to start a number of "send sub-processes", each of which would be responsible for sending one of the messages and dealing with any possible fault. These sub-processes would execute in parallel and return back to the parent process upon completion through a "signal". These signals can then be gathered by a dedicated activity in the parent process.

Related patterns.

• Broadcast. While the terms broadcast and multicast are sometimes used interchangeably, the term broadcast is most appropriately used where a message is sent to an open set of parties, i.e. the sender does not know who the recipients will be. Prospective recipients must either subscribe with a broker to receive that type of message (as in publish/subscribe messaging middleware) or access the message from a message board or equivalent mechanism. Typically, a broadcast is achieved by sending the message to a broker or message board service, which then pushes it or makes it available to the final recipients. Thus, a broadcast can be expressed as a one-to-one send from the sender to the broker, possibly followed by a one-to-many send from the broker to the final recipients.
• Multiple instances with a priori runtime knowledge (MIRT) (van der Aalst et al. 2003). In this pattern, several instances of a task are created and allowed to execute in parallel with synchronization occurring when all instances have completed. The number of task instances to be created is only known at runtime, just before the instantiation starts. The one-to-many send can be expressed by composition of the MIRT pattern and the one-to-one send pattern discussed above. The FlowN construct of Oracle BPEL (see discussion above) is a realization of the MIRT pattern.

Description. A party receives a number of logically related messages that arise from autonomous events occurring at different parties. The arrival of messages needs to be timely so that they can be correlated as a single logical request. The interaction may complete successfully or not depending on the set of messages gathered.

Synonyms. Event aggregation [Luckham 2002], gather [Snir & Gropp 1998].

Examples.

• Multi-part order. A printer operating in a high-demand market allows a streamlining of job preparation whereby documents belonging to the same job can be supplied directly by different parties (as with legislative documents by governments requiring quick turn-around). The first notification carries the job requirements including the delivery time and location. This and subsequent messages provide document content. Several interactions take place between the printer and the primary partner to mark-off the production steps, e.g. typesetting preview and payment. The printer's policy has a deadline for collection of all source documents in order to meet production deadlines. If the sources are not available by this deadline, the interaction fails, otherwise it succeeds. (More complex variant of the purchase order example given in (Luckam 2002) page 78).
• Batched requests. A group buying service receives requests for buying different types of items. When a request for buying a given type of product is received, and if there are no other pending requests for this type of item, the service waits for other requests for the same type of item. If at least three requests have been received within five days, a "group request" is created and an order handling process is started. If on the other hand less than three requests are received within the five days timeframe, the requests are discarded and a fault notification is sent back to the corresponding requestors.
• Event filtering prior to persistence. Investment consultants subscribe to a stock market watch service which broadcasts significant trading events. This allows the consultants to provide timely recommendations to their customers for changes in share portfolios. Events are correlated into composite events per fund manager. Because investment consultants are typically small enterprises (or smaller units of large enterprises), they cannot afford large databases in order to persist the high-volumes of incoming events prior to correlation. Rather they apply correlation rules as the events become available. If the individual events successfully correlate within the relevant timeframe into a significant composite event, an escalation is triggered. Otherwise the events are ignored.

Issues/design choices:

• Since messages originate from autonomous parties, a mechanism is needed to determine which incoming messages should be grouped together (i.e. correlated). This correlation may be based on the content of the messages (e.g. product identifier).
• Correlation of messages should occur within a given timeframe. The receiver should avoid waiting indefinitely.
• The number of messages to be received may or may not be known at design time or run-time. Instead, after a certain condition is fulfilled, the received messages are processed without waiting for subsequent related messages (i.e. proceed when X amount of orders for a given product have been received).
• In some cases, a timeout occurs before any message is received.

Solution, The first issue implies that the payload of the messages received should contain a piece of information that determines with which other messages it should be grouped (i.e. in which group should it be placed). At an abstract level, this can be captured through a function Group: Message → GroupID, which associates a "group identifier" to a message. Messages with the same group identifier are to be correlated. When a message of the expected type is received, its group ID is inspected and one of three options may be taken: (i) a new group is created for the message if no group for that group ID exists; (ii) the message is added to an existing group; (iii) the message may be discarded because the group ID is not valid (e.g. the group existed before but it is no longer accepting new messages). The latter option entails that the recipient should maintain a list of invalid group IDs (or equivalently a set of valid ones).

Because the number of messages to be received is not necessarily known in advance, it is necessary to incorporate, in one way or another, a notion of stop condition in the solution to this pattern. In the general case, the stop condition may be expressed as a predicate over the set of messages received. The stop condition is evaluated each time a message is received (and in particular, when the first message of a group arrives). As soon as the stop condition evaluates to true, the interaction is considered to be complete. In a tender scenario, to capture that as soon as 5 bids have been received the interaction completes and subsequent bids are ignored, the corresponding stop condition would be |R| = 5, where R denotes the set of messages received and |...| denotes the cardinality of a set.

To be complete, a solution to the pattern should associate timers to message groups. The timer for a group is started when the group is created. In many usage scenarios of this pattern the group is created when the first message mapping to the corresponding group ID is received. To simulate the case where a group is explicitly created by the receiving service, the service may send a "dummy" message to itself with the corresponding group ID, thus forcing the creation of the group. This "dummy" message will have to be removed or abstracted away after the group is completely formed and when evaluating the stop and success conditions. In any case, when the timer expires, the group is considered to be complete and the corresponding group ID may be flagged as no longer valid. Note that it is possible that a timeout occurs even if no message (except for the "dummy" one) has been received.

When a timeout occurs, depending on the set of messages gathered at that point, the interaction may be considered to have succeeded or failed. For example, a tender may be considered as successful if there are at least 3 bids and at least one of them is below a given limit price. Thus, a generic solution to the pattern also needs to incorporate a notion of success condition which is evaluated when the interaction completes and determines whether the interaction is considered as successful or not. Again, the success condition can be expressed as a predicate over the set of messages received. In the example at hand, the success condition would be: |R| ≥ 3 and ∃ r ∈ R: Price(r) ≤ limitPrice. Note that in theory, it may happen that the stop condition evaluates to true (and thus the interaction stops), while the success condition evaluates to false, so the interaction is considered to have failed.

When a "group" completes successfully, the set of responses gathered for that group constitute the "output" or "product" of the interaction.

To further illustrate the solution, we consider the examples introduced above:

• For "multi-order", the "stop condition" is a conjunction of all document source types needed (each of which can be correlated against expected incoming document sources), the "success condition" is that all expected document sources should have arrived by the printer's deadline, a group is created when the first message for that group is received.
• For "batched requests", the "stop condition" and the "success predicate" are identical (at least three requests should be received), the timeframe is five days, groups are created when the first message for the group arrives, and correlation IDs are never flagged as invalid since it is always possible to process requests for a given type of product whether or not previous groups for the same type of product have been filled or not.
• For "event filtering prior to persistence", the "success predicate" and the "stop predicate" both have the composite event condition.

Related pattern.

• Multiple instances with a priori runtime knowledge (MIRT). See discussion in the "Related patterns" paragraph of the previous pattern. Note that existing realizations of the MIRT pattern, such as the FlowN construct of Oracle BPEL (see discussion above) do not support arbitrary stop and success conditions as defined above. Instead, these conditions appear as lower and upper bounds on the number of task instances that are required to complete (i.e. the number of messages received).

Description. A party sends a request to several other parties, which may all be identical or logically related. Responses are expected within a given timeframe. However, some responses may not arrive within the timeframe and some parties may even not respond at all. The interaction may complete successfully or not depending on the set of responses gathered.

Synonyms. Scatter-gather [Snir & Gropp 1998], [Hohpe et al. 2003].

Example.

• RosettaNet Partner Interface Process (PIP) 3A3 - "Request Price and Availability". In this process, a buyer identifies a number of potential suppliers and sends a request for "price and availability" to each of them. Responses from all of these suppliers are then gathered and analysed. The number of potential suppliers is not known at design time.
• An insurance company outsources some aspects of its claims validation to its external search brokers. Brokers are typically small agencies and have variable demands. For efficiency, the insurance company sends search requests to all the brokers, and accepts the first three responses to undertake the search.

Issues/design choices.

• The number of parties to which messages are sent may or may not be known at design time.
• Responses need to be correlated to their corresponding request.
• The sender should avoid waiting indefinitely or "unnecessarily" for responses.
• It is possible that no response is received.
• Reliable delivery may or may not be required during sending. In the case of reliable delivery, the individual send actions may result in faults.

Solution. A solution to this pattern can be obtained by combining patterns one-to-many send and one-from-many receive through parallel composition (e.g. "flow" construct in BPEL). Since outgoing and incoming messages need to be correlated, it is necessary to include correlation data in the outgoing messages and retrieve these data from the incoming messages. BPEL provides a declarative mechanism, namely correlation sets, for correlating communication actions (e.g. correlating an invoke action with a receive action). Unfortunately, this mechanism can not be employed if the actions to be correlated are executed in different loops located in different branches of a flow activity, which is the case for this pattern since an a priori unknown number of invoke and receive actions need to be executed in an arbitrary order. Thus the correlation between the send and the receive actions implied by this pattern needs to be handled at the application level, i.e. by introducing actions that insert and extract the correlation data into/out of the incoming/outgoing messages.

The "stop condition" and the "success condition" for the one-from-many receive may involve both the set of requests (to be) sent (say RQ) and the set of responses gathered at a certain point (say RS). For example, to capture that as soon as 10 responses have been received the interaction stops and subsequent responses are ignored, the stop condition can be set to: |RS| = 10. Meanwhile, to ensure that at least 50% of the parties need to respond the success predicate should be set to: |RS| = 0.5 × |RQ|.

In the absence of a "stop condition" (i.e. if the stop condition is always false) the pattern can be expressed by combining several one-to-one send/receive through parallel composition, such that the resulting composition may be interrupted by a timeout. As discussed in the previous pattern, this would mean that the underlying language provides a mechanism for executing an a priori unknown number of activities in parallel, such as for example the "FlowN" construct in Oracle BPEL or the "spawn" construct in BPML. Such a mechanism is not present in standard BPEL and a workaround solution where the various one-to-one send/receive would be executed sequentially does not properly address the pattern.

In the case of reliable delivery, specific fault handling routines (i.e. fault handlers in BPEL) may be attached either to each individual send actions or to the whole set of send actions. A possible fault handling routine is to record that the message in question was not successfully delivered, so that this information can be taken into account in the stop and success conditions. In this way, it is possible to express success conditions such as "stop as soon as half of the parties who actually received a request have responded".

Related pattern.

• Scatter-gather (Hohpe & Woolf 2003). The scatter-gather pattern is a special case of the one-to-many send/receive. The scatter-gather assumes that all parties will respond in a timely manner and that all responses must be gathered and thus it does not address issues related to timeout, stop conditions, and success conditions.
• One-from-many receive/send. This is the dual of the one-to-many send/receive: A party receives messages from a number of other parties, correlates and processes them collectively, and constructs responses for all the parties. For example, a tendering service collects bids from various parties for a given period of time. At the end of this period, a winner is determined and all the parties who placed a bid are notified of the outcome. The issues and design choices are analogue to those of the one-to-many send/receive. The same holds for the solution which can be obtained by combining the "one-to-many receive" pattern with the "one-from-many send" through sequential composition.