  The workflow satisfiability problem is concerned with determining whether it
is possible to find an allocation of authorized users to the steps in a
workflow in such a way that all constraints are satisfied. The problem is
NP-hard in general, but is known to be fixed-parameter tractable for certain
classes of constraints. The known results on fixed-parameter tractability rely
on the symmetry (in some sense) of the constraints. In this paper, we provide
the first results that establish fixed-parameter tractability of the
satisfiability problem when the constraints are asymmetric. In particular, we
introduce the notion of seniority constraints, in which the execution of steps
is determined, in part, by the relative seniority of the users that perform
them. Our results require new techniques, which make use of tree decompositions
of the graph of the binary relation defining the constraint. Finally, we
establish a lower bound for the hardness of the workflow satisfiability
problem.
