On Deciding Stability of Constrained Homogeneous Random Walks and Queueing Systems

Consider a network of queueing stations in which jobs arrive with
some deterministic rate and require deterministic processing times.
Such a network is defined to be stable if the queue lengths remain bounded,
or, equivalently, the trajectory of the underlying dynamical system
does not diverge to infinity. To the day no algorithmic characterization
exists for checking stability of queueing systems, and only partial
results are available.

We prove that for a certain class of queueing systems stability is an
algorithmically undecidable property. As an intermediate step we prove that
stability of constrained random walks in a non-negative orthant is an undecidable
property. The results are obtain by a reduction from a certain version of
a Turing Halting Problem.