Parameterized Algorithmics for the Analysis and Verification of Constrained Workflow Systems

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.

The proposed research on constrained workflows will have direct
impact on the suppliers of business planning software, and the
academic community working in the broad area of algorithmics. In
the longer term, it will have an indirect impact on all large
organisations which have to plan and execute complex workflows.

All organisations, both public and private, have to allocate people
and resources to organizational processes in order to meet their
business objectives. The complexity of such allocation problems
often arises from the need to satisfy a variety of business rules.
Business rules come from general legal frameworks and provide for
the conformance to regulations; they can also emerge from day to
day planning or logistical requirements; and they can be put in
place to ensure secure working practices.

In all cases, not only do we need to solve all current workflow
problems efficiently, we have to assume that workflow requirements
might change unexpectedly with the introduction of new rules or
changes to staffing. Hence we need to find the most effective
algorithms possible for solving this class of problems. In order to
ensure that industry becomes aware of advances that we make either
in the modelling of, or the solution to, workflow problems we will
be organising an expert advisory group. This group of industrial
advisors will help us to focus on relevant issues and also
promulgate our research out into industry.

As well as the annual meetings of the advisory group we will be
organising a focused two day workshop to discuss the theoretical
and practical results of the project in the final year of the
grant. The workshop will naturally include a session with talks
from invited speakers from industry research laboratories as well
as theoretical talks. We expect the industrial speakers to include
representatives from IBM Research (Zurich), SAP Research (Sofia
Antipolis) and BAE Systems (Chelmsford). We are also confident of
attracting leading theoreticians to the workshop.

In addition to the industrial focus we will, naturally, be working
towards a better understanding of the underlying theoretical issues
that arise in solving complicated workflow problems. This research
will have a broad base as the research team comprises experts on
algorithmics, security and constraint satisfaction. All the
investigators are well-known within their respective research
communities and are well placed to discuss relevant advances with
colleagues at home and abroad.

We are confident this group will produce key new results on the
complexity of algorithms which are of interest to a wide variety of
academic and industrial researchers. We expect that industrial
partners will see savings on personnel as we are able to plan with
fewer specialised staff. We also expect that there will be
significant time efficiencies made by being able to plan online and
quickly to adapt to changing requirements and circumstances.