EPSRC logo

Details of Grant 

EPSRC Reference: EP/K005162/1
Title: Parameterized Algorithmics for the Analysis and Verification of Constrained Workflow Systems
Principal Investigator: Gutin, Professor G
Other Investigators:
Cohen, Professor D Crampton, Professor J
Researcher Co-Investigators:
Project Partners:
Department: Computer Science
Organisation: Royal Holloway, Univ of London
Scheme: Standard Research
Starts: 01 February 2013 Ends: 30 April 2016 Value (£): 602,797
EPSRC Research Topic Classifications:
Fundamentals of Computing
EPSRC Industrial Sector Classifications:
No relevance to Underpinning Sectors
Related Grants:
Panel History:
Panel DatePanel NameOutcome
18 Jul 2012 EPSRC ICT Responsive Mode - July 2012 Announced
Summary on Grant Application Form
Many business processes (or workflows) can be modeled as a set of

computational tasks or steps. Some of these steps may be performed by a human

agent (a "user") or a software agent operating under the control of a user.

There may be some flexibility in the order in which those steps may be

completed: one step, for example, can be performed in parallel with some

other step(s), while another step may be required to be performed before some

other step(s). In addition to such "control flow" constraints on a business

process, we may wish to impose restrictions on the users who perform the

steps in the workflow. Some steps, for example, may be commercially sensitive

and must be performed by a senior member of the user population. Requirements

of this nature can be captured in an authorization policy stating which users

are allowed to perform which steps. It is comparatively easy to ensure that

such policies are enforced. However, we may wish to impose more complex rules

on the business process. We might require, for example, that the same user

does not perform a particularly sensitive combination of steps; this is

sometimes known as the "two-man rule" for "four-eyes rule".

The combined effect of all these constraints on a business process is that it

may not be possible to allocate users to steps in such a way that all

constraints are satisfied simultaneously. It is known that determining

whether a workflow specification (defining the control flow and authorization

constraints) is satisfiable is a hard computational problem. Moreover, it is

clearly important to determine whether a workflow specification is

satisfiable; there is no point in defining a workflow specification that is

not satisfiable. An algorithm for deciding the satisfiability of a workflow

specification (a static analysis) must run in a reasonable amount of time.

The development of efficient algorithms to determine workflow

satisfiability will be one of the objectives of the proposed

research. In particular, we will examine the workflow

satisfiability problem (WSP) from the perspective of

fixed-parameter tractability. A hard computational problem, such as

the WSP, admits no algorithm with run-time polynomial in the size

of the input to the problem. Informally, fixed-parameter tractable

(FPT) problems are hard problems for which there exist algorithms

whose run-time is exponential in only one of the parameters that

comprise the input to the problem. If that parameter is small in

practice and the exponential function of the parameter is not

growing too fast, then an FPT algorithm will be efficient. Wang and

Li (2010) have shown that a restricted form of WSP is FPT, but

their algorithm is too slow to be of practical value. We will

develop faster FPT algorithms that can be used in practice.

Many workflow specifications of practical relevance do not have the

form studied by Wang and Li. Thus, another objective of this

project is to understand what other forms of WSP are FPT. This

objective includes the study of richer types of constraints and

more complex control flow patterns. Once we have an understanding

of what forms of WSP are FPT we will then evaluate the performance

of FPT algorithms against existing solutions.

A novel aspect of our proposal is to view WSP as a type of

constraint satisfaction problem (CSP). Despite the fact that WSP

exhibits features that make it unusual as a CSP, we expect that

complexity results, techniques and algorithms for CSP will still

provide new tools for tackling WSP. We believe that the

investigators' expertise and experience in workflow modelling,

algorithmics, parameterized complexity and constraint satisfaction

will yield fascinating insights into difficult theoretical problems

and provide practical and relevant tools that could be deployed in

commercial business information systems.

Key Findings
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Potential use in non-academic contexts
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Description This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Date Materialised
Sectors submitted by the Researcher
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Project URL:  
Further Information:  
Organisation Website: