On the Undecidability of Computing Stationary Distributions and Large Deviation Rates for Constrained Random Walks

References

• Bertsimas D., Nino-Mora J. Optimization of multiclass queueing networks with changeover times via the achievable region method: Part I, the single-station case. Math. Oper. Res. (1999) 24:306–330Link, Google Scholar
• Bertsimas D., Nino-Mora J. Optimization of multiclass queueing networks with changeover times via the achievable region method: Part II, the multi-station case. Math. Oper. Res. (1999) 24:331–361Link, Google Scholar
• Bertsimas D., Gamarnik D., Katz-Rogozhnikov D. On deciding stability of queueing networks under priority scheduling policy. . In preparationGoogle Scholar
• Bertsimas D., Gamarnik D., Tsitsiklis J. Performance of multiclass Markovian queueing networks via piecewise linear Lyapunov functions. Ann. Appl. Probab. (2001) 11(4):1384–1428Crossref, Google Scholar
• Bertsimas D., Paschalidis I., Tsitsiklis J. Optimization of multiclass queueing networks: Polyhedral and nonlinear characterization of achievable performance. Ann. Appl. Probab. (1994) 4:43–75Crossref, Google Scholar
• Blondel V. D., Tsitsiklis J. N. A survey of computational complexity results in systems and control. Automatica (2000) 36(9):1249–1274Crossref, Google Scholar
• Blondel V. D., Bournez O., Koiran P., Papadimitriou C. H., Tsitsiklis J. N. Deciding stability and mortality of piecewise affine systems. Theoret. Comput. Sci. (2001) 225(1–2):687–696Crossref, Google Scholar
• Blum L., Cucker F., Shub M., Smale S.Complexity and Real Computation (1997) (Springer-Verlag, New York) Google Scholar
• Bramson M. A stable queueing network with unstable fluid model. Ann. Appl. Probab. (1999) 9(3):818–853Crossref, Google Scholar
• Dai J. G. On the positive Harris recurrence for multiclass queueing networks: A unified approach via fluid models. Ann. Appl. Probab. (1995) 5:49–77Crossref, Google Scholar
• Dai J. G. A fluid-limit model criterion for instability of multiclass queueing networks. Ann. Appl. Probab. (1996) 6:751–757Crossref, Google Scholar
• Dai J. G., Hasenbein J. J., Vate J. H. Vande. Stability and instability of a two-station queueing network. Ann. Appl. Probab. (2004) 14:326–377Crossref, Google Scholar
• Fayolle G. On random walks arising in queueing systems: Ergodicity and transience via quadratic forms as Lyapunov functions—Part II. Queueing Systems (1989) 5:167–183Crossref, Google Scholar
• Fayolle G., Malyshev V. A., Menshikov M. V.Topics in the Constructive Theory of Countable Markov Chains (1995) (Cambridge University Press, Cambridge, UK) Crossref, Google Scholar
• Gamarnik D. On deciding stability of constrained homogeneous random walks and queueing systems. Math. Oper. Res. (2002) 27(2):272–293Link, Google Scholar
• Hooper P. The undecidability of the Turing machine immortality problem. J. Symbolic Logic (1966) 2:219–234Crossref, Google Scholar
• Hopcroft J., Ullman J.Formal Languages and Their Relation to Automata (1969) (Addison-Wesley, Boston, MA) Google Scholar
• Ignatiouk-Robert I. Sample path large deviations and convergence parameters. Ann. Appl. Probab. (2001) 11(4):1292–1329Crossref, Google Scholar
• Ignatiouk-Robert I. Large deviations for processes with discontinuous statistics. Ann. Probab. (2005) 33(4):1479–1508Crossref, Google Scholar
• Ignatyuk I. A., Malyshev V. A. Classification of random walks in ℤd+. Selecta Mathematica (1993) 12:129–194Google Scholar
• Ignatyuk I. A., Malyshev V. A., Scherbakov V. V. Boundary effects in large deviation problems. Russ. Math. Surv. (1994) 49:41–99Crossref, Google Scholar
• Kleinrock L.Queueing Systems (1975) (John Wiley & Sons, New York) Google Scholar
• Kumar P. R., Meyn S. P. Stability of queueing networks and scheduling policies. IEEE Trans. Automatic Control (1995) 40:251–261Crossref, Google Scholar
• Kumar S., Kumar P. R. Performance bounds for queueing networks and scheduling policies. IEEE Trans. Automatic Control (1994) 8:1600–1611Crossref, Google Scholar
• Kurkova I. A., Suhov Yu. M. Malyshev’s theory and JS-queues. Asymptotics of stationary probabilities. Ann. Appl. Probab. (2003) 13(4):1313–1354Crossref, Google Scholar
• Malyshev V. A. Analytic method in the theory of two-dimensional random walks. Sib. Math. J. (1972) 13(6):1314–1327Google Scholar
• Malyshev V. A. Classification of two-dimensional positive random walks and almost linear semimartingales. Dokl. Akad. Nauk SSSR (1972) 202:526–528Google Scholar
• Malyshev V. A. Asymptotic behaviour of stationary probabilities for two-dimensional positive random walks. Sib. Math. J. (1973) 14(1):156–169Crossref, Google Scholar
• Malyshev V. A. Networks and dynamical systems. Adv. Appl. Probab. (1993) 25:140–175Crossref, Google Scholar
• Menshikov M. V. Ergodicity and transience conditions for random walks in the positive octant of space. Soviet. Math. Dokl. (1974) 217:755–758Google Scholar
• Meyn S. P. Transience of multiclass queueing networks and their fluid models. Ann. Appl. Prob. (1995) 5:946–957Crossref, Google Scholar
• Meyn S. P., Tweedie R. L.Markov Chains and Stochastic Stability (1993) (Springer-Verlag, London, UK) Crossref, Google Scholar
• Meyn S. P., Tweedie R. L. Computable bounds for geometric convergence rates of Markov chains. Ann. Appl. Probab. (1994) 4:981–1011Crossref, Google Scholar
• Rybko A., Stolyar A. On the ergodicity of stochastic processes describing open queueing networks. Problemi Peredachi Informatsii (1992) 28:3–26Google Scholar
• Shwartz A., Weiss A.Large Deviations for Performance Analysis (1995) (Chapman and Hall, London, UK) Google Scholar
• Sipser M.Introduction to the Theory of Computability (1997) (PWS Publishing Company, Boston, MA) Google Scholar