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

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

Ihtisham Ali, Susmit Bagchi
Copyright: © 2019 |Pages: 30
DOI: 10.4018/IJGHPC.2019010105
(Individual Articles)
No Current Special Offers


Workflow is an essential mechanism for the automation of processes in distributed transactional systems, including mobile distributed systems. The workflow modeling enables the composition of process activities along with respective conditions, data flow and control flow dependencies. The workflow partitioning methods are used to create sub-partitions by grouping processes on the basis of activities, data flow and control flow dependencies. Mobile distributed systems consisting of heterogeneous computing devices require optimal workflow decomposition. In general, the workflow partitioning is a NP-complete problem. This article presents a comparative study and detailed analysis of workflow decomposition techniques based on graphs, petri nets and topological methods. A complete taxonomy of the basic decomposition techniques is presented. A detailed qualitative and quantitative analysis of these decomposition techniques are explained. The comparative analysis presented in this article provides an insight to inherent algorithmic complexities of respective decomposition approaches. The qualitative parametric analysis would help in determining the suitability of workflow applicability in different computing environments involving static and dynamic nodes. Furthermore, the authors have presented a novel framework for workflow decomposition based on multiple parametric parameters for mobile distributed systems.
Article Preview

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.

Complete Article List

Search this Journal:
Volume 16: 1 Issue (2024)
Volume 15: 2 Issues (2023)
Volume 14: 6 Issues (2022): 1 Released, 5 Forthcoming
Volume 13: 4 Issues (2021)
Volume 12: 4 Issues (2020)
Volume 11: 4 Issues (2019)
Volume 10: 4 Issues (2018)
Volume 9: 4 Issues (2017)
Volume 8: 4 Issues (2016)
Volume 7: 4 Issues (2015)
Volume 6: 4 Issues (2014)
Volume 5: 4 Issues (2013)
Volume 4: 4 Issues (2012)
Volume 3: 4 Issues (2011)
Volume 2: 4 Issues (2010)
Volume 1: 4 Issues (2009)
View Complete Journal Contents Listing