Research Perspectives - Tools for Visualisation of Portfolios
EPSRC logo

EPSRC Database


Source RCUK EPSRC Data

EP/K005162/1 - Parameterized Algorithmics for the Analysis and Verification of Constrained Workflow Systems

Research Perspectives grant details from EPSRC portfolio

http://www.researchperspectives.org/gow.grants/grant_EPK0051621.png

Professor G Gutin EP/K005162/1 - Parameterized Algorithmics for the Analysis and Verification of Constrained Workflow Systems

Principal Investigator - Computer Science, Royal Holloway, Univ of London

Other Investigators

Professor D Cohen, Co InvestigatorProfessor D Cohen

Professor J Crampton, Co InvestigatorProfessor J Crampton

Scheme

Standard Research

Research Areas

Maths of Computing Maths of Computing

Theory of Computation Theory of Computation

Start Date

02/2013

End Date

01/2016

Value

£602,797

Similar Grants

Automatic generation of similar EPSRC grants

Similar Topics

Topic similar to the description of this grant

Grant Description

Summary and Description of the grant

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.

Structured Data / Microdata


Grant Event Details:
Name: Parameterized Algorithmics for the Analysis and Verification of Constrained Workflow Systems - EP/K005162/1
Start Date: 2013-02-01T00:00:00+00:00
End Date: 2016-01-31T00:00:00+00:00

Organization: Royal Holloway, Univ of London

Description: 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 ...