On deciding stability of constrained homogeneous random walks and queueing systems

• 成果类型: Article
• 署名作者: Gamarnik, D
• 署名单位: International Business Machines (IBM); IBM USA
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.27.2.272.321
• 发表日期: 2002
• 页码: 272-293
• 关键词: fluid; instability; networks

摘要

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 F-+(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 F-+(d). We conjecture that stability of common policies like First-In-First-Out and priority policy is also an undecidable problem.