Some experimental results on placement techniques
Maurice Hanan, Peter K. Wolff, et al.
DAC 1976
We investigate stability of scheduling policies in queueing systems. To this day no algorithmic characterization exists for checking stability of a given policy in a given queueing system. In this paper we introduce a certain generalized priority policy and prove that the stability of this policy is algorithmically undecidable. We also prove that stability of a homogeneous random walk in ℒ+d is undecidable. Finally, we show that the problem of computing a fluid limit of a queueing system or of a constrained homogeneous random walk is undecidable. To the best of our knowledge these are the first undecidability results in the area of stability of queueing systems and random walks in ℒ+d. We conjecture that stability of common policies like First-In-First-Out and priority policy is also an undecidable problem.
Maurice Hanan, Peter K. Wolff, et al.
DAC 1976
Elena Cabrio, Philipp Cimiano, et al.
CLEF 2013
Ehud Altman, Kenneth R. Brown, et al.
PRX Quantum
S.M. Sadjadi, S. Chen, et al.
TAPIA 2009