| EPSRC Reference: |
EP/K005162/1 |
| Title: |
Parameterized Algorithmics for the Analysis and Verification of Constrained Workflow Systems |
| Principal Investigator: |
Gutin, Professor G |
| Other Investigators: |
|
| 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 Date | Panel Name | Outcome |
|
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
|
|
Impacts |
|
| Description |
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk |
| Summary |
|
| 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: |
|