  In this work, we consider a computational model of a distributed system
formed by a set of servers in which jobs, that are continuously arriving, have
to be executed. Every job is formed by a set of dependent tasks (i.~e., each
task may have to wait for others to be completed before it can be started),
each of which has to be executed in one of the servers. The arrival of jobs and
their properties is assumed to be controlled by a bounded adversary, whose only
restriction is that it cannot overload any server. This model is a non-trivial
generalization of the Adversarial Queuing Theory model of Borodin et al., and,
like that model, focuses on the stability of the system: whether the number of
jobs pending to be completed is bounded at all times. We show multiple results
of stability and instability for this adversarial model under different
combinations of the scheduling policy used at the servers, the arrival rate,
and the dependence between tasks in the jobs.
