Some Theorems on Instability with Applications to Multiaccess Protocols

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⁻¹ = 0.368.