L.P. Parida, I. Rigoutsos, et al.
SODA 2000
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.
L.P. Parida, I. Rigoutsos, et al.
SODA 2000
David Gamarnik
ACM COLT 1998
David Gamarnik
FOCS 1998
David Gamarnik
ACM COLT 1999