On deciding stability of scheduling policies in queueing systems

Abstract

We investigate stability of certain scheduling policies in a queueing system. To the day no algorithmic characterization exists for checking stability of a given policy in a given queueing system. In this paper we propose a certain generalized priority policy and prove that the stability of this policy is algorithmically undecidable. To the best of our knowledge this is the first undecidability result in the area of stability of queueing systems. We conjecture that stability of other common policies like First-In-First-Out and priority policy is also an undecidable problem. We also prove that stability of a homogeneous random walk in Z+d is undecidable.