Ensuring reliability in B2B services: Fault tolerant inter-organizational workflows

Abstract

In the age of Business-to-Business (B2B) collaboration, ensuring reliability of workflows underlying inter-organizational business processes is of significant importance. There are, however, quite a few challenges towards achieving seamless operation. Such challenges arise from heterogeneity in infrastructure and coordination mechanism at participant organizations, as well as time and cost associated with recovery from failure. Our research presents foundations for a reliable scheme for recovery from failure of workflow processes spanning through multiple business entities. First, a system model is adapted from the mobile computing literature that serves to establish the requirements to be enforced by each participating organization. In our model, we adopt the Maximal Sequence Path (MSP) approach from Yoo et al. (Lecture Notes in Artificial Intelligence 2132:222–236, 2001), as a means of decomposing workflows into mobile agent-driven processes that communicate via web services at each organization. This decomposition ensures defining logical points within the dynamics of a workflow instance for locating accurate and consistent states of the system for recovery in case of a failure. Then, a set of algorithms for various business scenarios are developed and presented as practical solutions. These algorithms are shown to create checkpoints such that the system is always in a globally consistent state. As such, these algorithms constitute a set of standards that can be incorporated in business process management suites that support reliable inter-organizational collaboration.

Appendices

Appendix A: Skeletal proof

1.1 Background: System model rules for each node in a workflow

• 1. If (state = ‘Receive’) then wait for a message. If it is a ‘new unit of work’ message, then send an acknowledgement to the source and switch to state = ‘Process’. If it is an acknowledgement message, checkpoint the processed unit of work, send and receive messages. (Note: If more than one message arrives simultaneously, they will be placed into the FIFO queue)

• 2. If (state = ‘Process’) perform the specified task, and upon completion switch to state = ‘Send’

• 3. If (state = ‘Send’) then send the processed unit of work message to the workflow engine or the next node, and then switch to state = ‘Receive’

(Note: Idle nodes are presumed to be in the ‘Receive’ state)

1.2 Step 1: Correctness of checkpoints

For an inter-organizational workflow to recover to a globally consistent state when using checkpoints, there must be a set of rules for each node to follow to create independent checkpoints. Those rules are given above. The intent is that when there is a failure, checkpoints can be assembled to enable reconstruction of a global state with integrity guarantees. When using checkpoints, some rework may need to be done when there is a failure, but the most important property of a recovery process is to guarantee a globally consistent state. As is true of most related proofs regarding failure and recovery algorithms, it is impossible to consider all possible failure scenarios in all possible workflow contexts, particularly those with combinations of failures. Therefore, we focus in this skeletal proof on what might be referred to as a normal workflow context, characterized as follows:

• 1. The workflow is presumed to be complete and capable of being compiled into a tractable set of MSPs,

• 2. A node cannot alter an MSP for a given workflow,

• 3. It is assumed that a legal or correct agent at each node operates on a unit of work, that

• 4. It is assumed that the writing of a checkpoint proceeds without failure or the node will be deemed as failing, and

• 5. It is assumed that the last non-failed node in an MSP with a failure will have an available checkpoint.

Now, suppose there is some arbitrary checkpoint approach, implying that every node in a workflow follows its own state-transition rules to independently checkpoint its local state. Then, it is not possible to state with certainty that a checkpoint in a node (e.g., B) that follows in the workflow from another node in that workflow (e.g., A) creates a checkpoint at a time after the subsequent node completes its work (e.g., B checkpoints before A since the checkpoint time at A is arbitrary). We can say that in this arbitrary context, it is not guaranteed that an earlier checkpoint at the node ‘depends on’ a later checkpoint at a node.

In the node rules stated above, there is not an arbitrary checkpoint—instead, the rules guarantee a recoverable checkpoint. This is because for a particular workflow instance, if a unit of work is checkpointed by some node A and passed on to a node B according to the flow designated in the MSP, then processed by B and checkpointed by B, then checkpoint a (amount of information logged at node A after task is completed at A and delivered to node B) is said to be included in checkpoint b (a + amount of information logged at node B after the task is completed at B and delivered to the next node). This is because the system model assumes that all completed work at a node, i.e., the payload, is cumulative—the work of a node prior in the MSP is passed on to subsequent nodes in the MSP.

This ‘depends on’ relationship (denoted ‘>’) is an important criterion of checkpoint-based recovery approaches; therefore, in the scenario above b > a. Following is a formal definition of the ‘depends on’ relationship (‘>’) between checkpoints at nodes:

A node’s checkpoint, ckpt_a > ckpt_b if there exist messages m and m’ such that receive(m’) belongs to ckpt_a, send(m) belongs to ckpt_b, send(m) → receive(m’), where → represents “happened before” relationship.

This means that the ‘depends on’ relationship refers to the timing of the checkpoints. If a checkpoint depends on another checkpoint, then the latter was created at a point in time prior to the former. Simply, this implies that since ckpt_a > ckpt_b then if ckpt_a is in the global checkpoint, then ckpt_b is also in the global checkpoint in order to maintain consistency of the global checkpoint.

Following is a discussion and proof of this important property for our system model. First, let us define several variables. For a particular workflow instance, assume the following conditions hold:

• 1. The entire workflow is composed of r MSPs. For any particular MSP j, 1<=j<= r

• 2. The j-th MSP has n _j nodes. For any particular node k, 1<=k<=n _j , where n_j = the number of nodes in the j-th MSP

Lemma 1

If checkpoint P _jk represents checkpoint recorded at the k-th node of the j-th MSP of the workflow instance, it is not possible that P _jk depends on checkpoint P _j(k+1)

Lemma 1 Proof

Suppose, checkpoint P _jk depends on checkpoint P _j(k+1).

Since these nodes are subsequent nodes in the same MSP, in following the system model’s rules there must have been transfer of messages—a new-unit-of-work message and an acknowledgement message—between them, and the checkpoints contain records of the send and receive events. We denote the new-unit-of-work message by ‘m’ where the contents of m are as discussed in the system model. Since P _jk depends on P _j(k+1) :

• a) There is a record of the event “received m” in P _jk

• b) There is a record of the event “sent m” in the checkpoint P _j(k+1) , but not in P _jk , and,

• c) The event “received m” would have to have taken place before the “sent m”, and this is impossible given the rules send(m) → rec(m’).

However (a) and (b) together with the relationship rule, means that send(m) occurred after receive(m’) which violates (c). By contradiction, it is not possible that P _jk depends on checkpoint P _j(k+1).

Discussion

This proof shows that if we follow the system model rules and each node behaves according to these rules, it would be impossible for an incorrect checkpoint to be written (unless there is a failure). By incorrect, we mean that the checkpoint would contain information from future work that may or may not be completed. This type of anomaly would result in an inconsistent state if we used the checkpoint information as a basis for restarting computation. Further, the system rules can now be unequivocally stated as a requirement for a web services-based docking station or WFE client.

1.3 Step 2: Proof of a globally consistent state

Next, we must show that a set of correct checkpoints can be used to construct a globally consistent state. Let us we more precisely define ‘local’ and ‘global’ checkpoints: A local checkpoint, P _jk , is a log written at a node where the node follows the state-transition rules such that a log of the processed unit of work—along with the send and receive messages at that node—are completely written after a message containing that payload is forwarded to the next node in the MSP. Suppose further that P _jk includes the next node’s acknowledgement of receipt of the message sent by the current node. Then, a global checkpoint, P _JK is the set of all possible local checkpoints relevant to a particular workflow instance being coordinated by a central workflow engine at some point in time.

It follows that the total number of checkpoints for an entire workflow instance is less than or equal to P _JK where:

$$ {{\text{P}}_{\text{JK}}} = \sum\limits_{{{\text{j = 1}}}}^{\text{r}} {\sum\limits_{{{\text{k = 1}}}}^{{{{\text{n}}_{\text{j}}}}} {{{\text{P}}_{\text{jk}}}} } . $$

We must show that:

Lemma 2

The collection of correct local checkpoints, P _JK , forms a consistent global checkpoint.

Proof

If, by contradiction, we do not have global consistency then:Assume a message m has been sent from a node A to another node B in the same MSP for the same workflow instance such that:

• 1. The event ‘send m’ is not in the global checkpoint, in other words, A sends m before writing a checkpoint, and then A continues work.

• 2. Then the event ‘receive m’ is included in the global checkpoint (‘receive m’ is in the log at node B) after node B gets done with its work, at a point in time before node A gets done with its processing, and then A checkpoints.

From 1 and 2 and the algorithm given, this implies that the checkpoint where ‘receive m’ is in the log (node B) < the checkpoint with ‘send m’ in the log (node A). The symbol ‘<’is used to imply that the checkpoint at node B contains less than the total amount of work, and node B’s checkpoint comes before node A’s. (Conclusion I)

Fig. 14

Fig. 14

Lemma 2

However, since there is a checkpoint in a node (in the above case, node B) where the ‘receive m’ is in the log, then there would have to be message in the checkpoint of the prior node (in the above case A) containing both a send and that receive, because the state-transition rule states that one can’t send m until the work has been completely processed, and receive m only after the send m. Basically, since the ‘unit of work’ is to be completed sequentially by a node in an MSP for a particular workflow instance, and the cumulative message moves from one node to a next as they were stated in the system model and state transition rule. Hence this implies the checkpoint at node A < the checkpoint at node B. (Conclusion II)

Since conclusions I and II lead are contradicting, it is shown that the state-transition rule results in global consistency of the generated logs (i.e., P _JK ). The state-transition rule then forms the foundation of reliable web-services based IOW standards. Based on this rule, several variations can now be developed to accommodate different workflow situations, types of inter-organizational relationships, and to provide a foundation for recovery approach evaluations. Further, higher level web services-based standards embedded in inter-organizational workflow docking stations that follow the rules discussed here, write logs according to the algorithms stated, rely on engines capable of both decomposing workflows into MSPs and can initiate recovery procedures in the cases of node failure, and can recover to the latest feasible point of completion by relying on globally consistent logs.

Appendix B: Abbreviations used

ACID	Atomicity, Consistency, Isolation, Durability
B2B	Business to Business
BPM	Business Process Management
CWFE	Centralized Workflow Engine
FIFO	First in First Out
MSP	Maximal Sequence Path
IOWS	Inter Organizational Workflow Systems
SOA	Service Oriented Architecture
WFE	Workflow Engine
WFI	Workflow Instance