Hostname: page-component-cd9895bd7-lnqnp Total loading time: 0 Render date: 2024-12-26T17:01:57.992Z Has data issue: false hasContentIssue false
  • English
  • Français

Stability conditions for some distributed systems: buffered random access systems

Part of: Stability

Published online by Cambridge University Press:  01 July 2016

Wojciech Szpankowski
Wojciech Szpankowski*
Affiliation:
Purdue University
*
* Postal address: Department of Computer Science, Purdue University, W. Lafayette, IN 47907, USA.
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider the standard slotted ALOHA system with a finite number of buffered users. Stability analysis of such a system was initiated by Tsybakov and Mikhailov (1979). Since then several bounds on the stability region have been established; however, the exact stability region is known only for the symmetric system and two-user ALOHA. This paper proves necessary and sufficient conditions for stability of the ALOHA system. We accomplish this by means of a novel technique based on three simple observations: applying mathematical induction to a smaller copy of the system, isolating a single queue for which Loynes' stability criteria is adopted, and finally using stochastic dominance to verify the required stationarity assumptions in the Loynes criterion. We also point out that our technique can be used to assess stability regions for other multidimensional systems. We illustrate it by deriving stability regions for buffered systems with conflict resolution algorithms (see also Georgiadis and Szpankowski (1992) for similar approach applied to stability of token-passing rings).

Keywords

ALOHAMULTIDIMENSIONAL MARKOV CHAINSSUBSTABILITYLOYNES SCHEMEMATHEMATICAL INDUCTION

MSC classification

Primary: 93D20: Asymptotic stability
Type
General Applied Probability
Information
Advances in Applied Probability , Volume 26 , Issue 2 , June 1994 , pp. 498 - 515
Copyright
Copyright © Applied Probability Trust 1994 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

This research was supported in part by NSF grants NCR-9206315 and CCR-9201078, by AFOSR grant 90–0107, and in part by NATO Collaborative Grant 0057/89. This paper was revised while the author was visiting INRIA, Rocquencourt, France, and he wishes to thank INRIA (projects ALGO, MEVAL and REFLECS) for generous support.

References

Anantharam, V. (1991) The stability region of the finite-user slotted ALOHA protocol, IEEE Trans. Information Theory, 37, 535–540.CrossRefGoogle Scholar
Borovkov, A. A. (1976) Stochastic Processes in Queueing Theory. Springer-Verlag, New York.CrossRefGoogle Scholar
Breiman, L. (1968) Probability. Addison-Wesley, Reading, MA.Google Scholar
Capetanakis, J. (1979) Tree algorithms for packet broadcast channels. IEEE Trans. Information Theory 25, 505–515.Google Scholar
Falin, G. (1981) On ergodicity of a multiaccess system. Tech. Kibern. 4, 126–131.Google Scholar
Fayolle, G. (1989) On random walks arising in queueing systems: ergodicity and transience via quadratic forms as Lyapunov functions. Part I. Queueing Systems 5, 167–184.Google Scholar
Georgiadis, L. and Szpankowski, W. (1992) Stability of token passing rings. Queueing Systems, 11, 7–33.CrossRefGoogle Scholar
Georgiadis, L. and Szpankowski, W. (1993) Stability criteria for yet another class of multidimensional distributed systems. Proc. 11th Internat. Conf. on Analysis and Optimization Systems: Discrete Event Systems. Sophia Antipolis, France.Google Scholar
Georgiadis, L., Szpankowski, W. and Tassiulas, L. (1993) Stability analysis of scheduling policies in ring networks with spatial re-use. Proc. 31st Annual Allerton Conference, Monticello.Google Scholar
Loynes, R. (1962) The stability of a queue with non-independent inter-arrival and service times. Proc. Camb. Phil. Soc. 58, 497–520.Google Scholar
Malyshev, V. A. (1972) Classification of two-dimensional positive random walks and almost linear semimartingales. Dokl. Akad. Nauk SSSR 22, 136–138.Google Scholar
Malyshev, V. A. and Mensikov, M. V. (1981) Ergodicity, continuity and analyticity of countable Markov chains. Trans. Moscow Math. Soc., 1–18.Google Scholar
Mensikov, M. V. (1974) Ergodicity and transience conditions for random walks in the positive octant of space. Soviet. Math. Dokl. 15, 1118–1121.Google Scholar
Meyn, S. and Tweedie, R. L. (1992) Criteria for stability of Markovian processes I: Discrete time chains. Adv. Appl. Prob. 24, 542–574.Google Scholar
Nain, P. (1985) Analysis of a two-mode ALOHA network with infinite capacity buffer. Proc. Internat. Seminar on Computer Networking and Performance Evaluation, Tokyo, pp. 49–64. North-Holland, Amsterdam.Google Scholar
Paterakis, M., Georgiadis, L., and Papantoni-Kazakos, P. (1987) On the relationship between the finite and the infinite population models for a class of RAA's. IEEE Trans. Commun. 35, 1239–1240.Google Scholar
Rao, R. and Ephremides, A. (1989) On the stability of interacting queues in multiple access system. IEEE Trans. Inf. Theory 34, 918–930.Google Scholar
Rosenkrantz, W. (1989) Ergodicity conditions for two dimensional Markov chains on the positive quadrant. Prob. Theory Rel. Fields 83, 309–319.CrossRefGoogle Scholar
Szpankowski, W. (1986) Bounds for queue lengths in a contention packet broadcast system. IEEE Trans. Commun. 34, 1132–1140.CrossRefGoogle Scholar
Szpankowski, W. (1988) Stability conditions for multi-dimensional queueing systems with computer applications. Operat. Res. 36, 944–957.Google Scholar
Szpankowski, W. (1990) Towards computable stability criteria for some multidimensional stochastic processes. In Stochastic Analysis of Computer and Communication Systems, ed. Takagi, H., pp. 131–172. Elsevier North-Holland, Amsterdam.Google Scholar
Tsybakov, B. and Mikhailov, W. (1978) Free synchronous packet access in a broadcast channel with feedback. Probl. Pered. Inf. 14, 259–280.Google Scholar
Tsybakov, B. and Mikhailov, W. (1979) Ergodicity of slotted ALOHA system. Probl. Pered. Inf. 15, 73–87.Google Scholar
Tweedie, R. L. (1976) Criteria for classifying general Markov chains. Adv. Appl. Prob. 8, 737–771.CrossRefGoogle Scholar
Vaninskii, K. and Lazareva, B. (1988) Ergodicity and nonrecurrence conditions of a homogeneous Markov chain in the positive quadrant. Probl. Pered. Inf. 24, 105–110.Google Scholar
Walrand, J. (1988) An Introduction to Queueing Networks. Prentice Hall, Englewood Cliffs, NJ.Google Scholar