A Comparative Study and Algorithmic Analysis of Workflow Decomposition in Distributed Systems

1. Introduction

Today’s scientific computations involve hundreds and thousands of execution steps which are not necessarily originated from a single origin. The computations can be distributed and shared by heterogeneous groups in an execution environment. The assembly and execution of computational steps are challenging tasks in heterogeneous distributed systems (Benoit et al., 2013). The workflow is a mechanism of describing the operational aspect of a work process denoting the function of the task along with its control flow pattern (Boutamina & Maamri, 2015). The formal definition of workflow is given as, “Workflows represent declaratively the components or codes that need to be executed in a complex application, as well as the data dependencies among those components” (Brezillon, 2011).

A workflow can be broadly categorized into two types such as: 1) abstract workflow and, 2) concrete workflow (Deelman et al., 2003). In the abstract workflow, dependencies among different tasks are being defined but are not bound to a particular service. While in the concrete workflow, distributed task dependencies are strictly bound to specific services. The workflow specification consists of three items: Process, Data, and Invocation (Ailamaki et al., 1998). Process is composed of workflow tasks and their internal relationships. It should be flexible enough to allow different forms of interrelationship e.g. tasks operating in series or in parallel, tasks providing input to or receiving input from other tasks etc. The data item is referred to the sets of input values and output values associated to a workflow. Invocation is the procedure that initiates the execution of each task at specific instant of time. There can be explicit invocation by a human to initiate a task or implicit invocation of tasks which starts after the execution of another task by satisfying a predefined condition.