We consider applications in the Internet/Web environment. The types of applications we have in mind are to do with the automation of so called 'business processes' of organizations that are increasingly using the Internet for their day to day functioning. The domain of electronic commerce is a good example: here automation of business processes would include system support to help consumer-to-business as well as business-to-business interactions for buying and selling of goods. Unfortunately, the Internet frequently suffers from failures which can affect both the performance and integrity of applications run over it.

A number of factors need to be taken into account in order to make these applications fault-tolerant. First, most such applications are rarely built from scratch; rather they are constructed by composing them out of existing applications and protocols. It should therefore be possible to compose an application out of component applications in a uniform manner, irrespective of the languages in which the component applications have been written and the operating systems of the host platforms. Application composition however must take into account individual site autonomy and privacy requirements. Second, the resulting applications can be very complex in structure, containing many temporal and data-flow dependencies between their constituent applications. However, constituent applications must be scheduled to run respecting these dependencies, despite the possibility of intervening processor and network failures. Third, the execution of such an application may take a long time to complete, and may contain long periods of inactivity (minutes, hours, days, weeks etc.), often due to the constituent applications requiring user interactions. It should be possible therefore to reconfigure an application dynamically because, for example, machines may fail, services may be moved or withdrawn and user requirements may change. Fourth, facilities are required for examining the application’s execution history (e.g., to be able to settle disputes). So, a durable ‘audit trail’ recording the interactions between component applications needs to be maintained. Taken together, these are challenging requirements to meet!

Distributed objects plus ACID transactions provide a foundation for building high integrity applications. However, it has long been realised that ACID transactions by themselves are not adequate for structuring long-lived applications [1]. Top-level transactions are most suitably viewed as "short-lived" entities, performing stable state changes to the system. Long-lived top-level transactions may reduce the concurrency in the system to an unacceptable level by holding on to resources for a long time; further, if such a transaction aborts, much valuable work already performed could be undone. In short, if an application is composed as a collection of transactions, then during run time, the entire activity representing the application in execution is frequently required to relax some of the ACID properties of the individual transactions. The entire activity can then be viewed as a non-ACID ‘extended transaction’. Much research work has been done on developing extended transaction models [e.g. 2]. Nevertheless, most of these techniques have not found any widespread usage, the main reason being lack of flexibility [3].

As observed in [3], transactional workflow systems with scripting facilities for expressing the composition of an activity (a business process) offer a flexible way of building application specific extended transactions. Our approach is in the similar vain: we have implemented an application composition and execution environment as a transactional workflow system that enables sets of inter-related tasks to be carried out and supervised in a dependable manner. Currently available workflow systems are not scalable, as their structure tends to be monolithic. Further, they offer little support for building fault-tolerant applications, nor can they inter-operate, as they make use of proprietary platforms and protocols. Our system represents a significant departure from these; our system architecture is decentralized and open: it has been designed and implemented as a set of CORBA services to run on top of a given ORB [4].

The workflow system’s structure is shown in fig. 1. Here the big box represents the structure of the entire distributed workflow system (and not the software layers of a single node); the small box represents any node with a Java capable browser. The most important components of the system are the two transactional services, the workflow repository service and the workflow execution service. These two facilities make use of the CORBA Object Transaction Service (OTS). In our system, application control and management tools required for functions such as monitoring and dynamic reconfiguration etc., (collectively referred to as administrative applications) themselves can be implemented as workflow applications. Thus the administrative applications can be made fault-tolerant without any extra effort. Graphical user interface to the these administrative applications has been provided by making use of Java applets which can be loaded and run by any Java capable Web browser.

Fig. 1: Workflow management system structure.

Workflow Repository Service: The repository service stores workflow schemas and provides operations for initializing, modifying and inspecting schemas. A schema is represented according to the model briefly discussed below in terms of tasks, compound tasks, genesis tasks and dependencies. We have designed a scripting language that provides high-level notations (textual as well graphic) for the specification of schemas. The scripting language has been specifically designed to express task composition and inter-task dependencies of fault-tolerant distributed applications whose executions could span arbitrarily large durations [5]. We next describe the task model that enable flexible ways of composing an application

Fig. 2: A task

Fig. 3: A Workflow schema indicating inter-task dependencies.

To allow applications to be recursively structured, the task model allows a task to be realized as a collection of tasks, this task is called a compound task. A task can either be a simple task (primitive task) or a compound task composed from simple and compound tasks.

The task model also supports a specialised form of compound task called a genesis task to specify workflow applications that contain recursive executions [4, 6]. Its main purpose is to enable dynamic (on demand) instantiation of schema; this provides an efficient way of managing a very large workflow, as only those parts that are strictly needed are instantiated.

In summary, the task model has the following notable features:

Workflow Execution Service: The workflow execution service coordinates the execution of a workflow instance: it records inter-task dependencies of a schema in persistent atomic objects and uses atomic transactions for propagating coordination information to ensure that tasks are scheduled to run respecting their dependencies. The dependency information is maintained and managed by task controllers. Each task within a workflow application has a single dedicated task controller. The purpose of a task controller is to receive notifications of outputs of other task controllers and use this information to determine when its associated task can be started. The task controller is also responsible for propagating notifications of outputs of its task to other interested task controllers. Each task controller maintains a persistent, atomic object, TaskControl that is used for recording task dependencies. The structure is shown in fig. 4. For example, task controller tc₃ will co-ordinate with tc₁ and tc₃ to determine when t₃ can be started and propagate to tc₄ and tc₅ the results of t₃.

Fig. 4: Tasks and task controllers.

In short, our system provides a very flexible and dependable task coordination facility that need not have any centralized control. Because the system is built using the underlying transactional layer, no additional recovery facilities are required for reliable task scheduling: provided failed nodes eventually recover and network partitions eventually heal, task notifications will be eventually completed. In addition, the system automatically records the application's execution history (audit trail): this is maintained in the committed states of TaskControl objects of the application.

Another important aspect of our system that is discussed in detail elsewhere is that the system directly provides support for dynamic modification of workflows [6]. Briefly, the TaskControl objects maintain the inter-task dependency information of an application (as indicated above) and make this information available through transactional operations for performing changes (such as addition and removal of tasks as well as addition and removal of dependencies between tasks). The use of transactions ensures that changes to schemas and instances are carried out atomically with respect to normal processing.

Currently available workflow systems are not scalable, as their structure tends to be monolithic. Further, they offer little support for building fault-tolerant distributed applications. System such as ours, Coyote [7] and ORBWork [8] represent new generation of (research) systems that can work in distributed environments and provide support for fault tolerance.

Our system has been structured to provide dependability at application level and system level. Support for application level dependability has been provided through flexible task composition discussed earlier that enables an application builder to incorporate alternative tasks, compensating tasks, replacement tasks etc., within an application to deal with a variety of exceptional situations. Support for system level dependability has been provided by recording inter-task dependencies in transactional shared objects and by using transactions to implement the delivery of task outputs such that destination tasks receive their inputs despite finite number of intervening machine crashes and temporary network related failures; this also provides a durable audit trail of task interactions. Thus our system naturally provides a fault-tolerant ‘job scheduling’ environment that maintains a durable history of application interactions.

The system described here has been fully implemented.

This work has been supported in part by grants from Nortel Technology and Engineering and Physical Sciences Research Council, ESPRIT LTR Project C3DS (Project No. 24962) and ESPRIT Project MultiPLECX (Project No. 26810).