We use cookies on this site. By browsing our site you agree to our use of cookies. Close this message Find out more

Home > Computer Science home > News > EPSRC Grant "Parameterized Algorithmics for the Analysis and Verification of Constrained Workflow Systems" starts
More in this section News articles

EPSRC Grant "Parameterized Algorithmics for the Analysis and Verification of Constrained Workflow Systems" starts

Posted on 23/01/2013

Prof Gregory Gutin, principal investigator

A new EPSRC grant on "Parameterized Algorithmics for the Analysis and Verification of Constrained Workflow Systems" started on the 1st Feb. 2013 and will last for three years.

Many business processes (or workflows) can be modeled as a set of computational steps. 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 al 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 the main objective of the grant research.  More specifically,  the workflow satisfiability problem (WSP) will be examined 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 only in the parameters that comprise the input to the problem. If those parameter are small in practice and the exponential function of the parameters is not growing too fast, then an FPT algorithm will be efficient.

Gregory Gutin is the principal investigator of this grant, and David Cohen (also from Computer Science) and  Jason Crampton (Information Security Group)  are co-investigators. There are two RAs working on the grant: Mark Jones (currently completing his PhD in our department) and Andrei Gagarin (currently in Canada).  An Expert Advisory Group is being formed, which will include industry experts from BAE Systems (Chelmsford), IBM Research (Zurich), Intel (Swindon) and SAP Research (Sophia-Antipolis).


Comment on this page

Did you find the information you were looking for? Is there a broken link or content that needs updating? Let us know so we can improve the page.

Note: If you need further information or have a question that cannot be satisfied by this page, please call our switchboard on +44 (0)1784 434455.

This window will close when you submit your comment.

Add Your Feedback