Some Theorems on Instability with Applications to Multiaccess Protocols
Wojciech Szpankowski, Vernon Rego
Operations Research · 1988 · Volume 36 · Issue 6
Abstract
An important question in stochastic modeling is whether a denumerable state Markov chain describing a system is stable or not. Adopting a general definition of stability, we discuss some conditions for instability. We extend slightly previous results on nonergodicity, and we present new criteria for moments of a chain to be infinite. Finally, we apply these instability conditions to study some multidimensional Markov chains that describe multiaccess protocols in a broadcast environment. In particular, we prove that the exponential backoff algorithm is unstable for λ > 0.461, and the decentralized dynamic control algorithm is unstable for λ > e −1 = 0.368.
Keywords
communications: instability of multiaccess protocols, probability, Markov processes: generalized drift, nonergodicity and instabilities of multidimensional Markov chains
Enable JavaScript for citation tools and additional paper interactions.