IS16: Stochastic Stability

Organizer: Sergey Foss (Heriot-Watt University)

Poisson Hail on a Wireless Ground

Sergey Foss

In the talk, we will present a new model which incorporates three key ingredients of a large class of wireless communication systems: (1) spatial interactions through interference – see e.g. \([1]\), (2) dynamics of the queueing type, with users joining and leaving – see e.g. \([2]\), and (3) carrier sensing and collision avoidance as used in, e.g., WiFi – see e.g. \([3]\). In systems using (3), rather than directly accessing the shared resources upon arrival, a customer is considerate and waits to access them until nearby users in service have left. This new model can be seen as a missing piece of a larger puzzle that contains such dynamics as spatial birth-and-death processes, the Poisson-Hail model, and wireless dynamics as key other pieces. It is shown that, under natural assumptions, this model can be represented as a Markov process on the space of counting measures. The main results are then two-fold. The first is on the shape of the stability region and, more precisely, on the characterization of the critical value of the arrival rate that separates stability from instability. The second is of a more qualitative or perhaps even ethical nature. There is evidence that for natural values of the system parameters, the implementation of sensing and collision avoidance stabilizes a system that would be unstable if immediate access to the shared resources would be granted. In other words, for these parameters, renouncing greedy access makes sharing sustainable, whereas indulging in greedy access kills the system.

The talk is based on a joint paper with François Baccelli and Ke Feng \([4]\).

Bibliography

\([1]\) F. Baccelli and S. Foss. "Poisson Hail on a Hot Ground." Journal of Applied Probability, vol. 48, no. A, 2011, pp. 343–366.

\([2]\). C. Preston, “Spatial birth and death processes.” Advances in Applied Probability, vol. 7, no. 3, 1975, pp. 465–466.

\([3]\) A. Sankararaman, F. Baccelli and S. Foss. "Interference Queueing Networks on Grids." The Annals of Applied Probability, vol. 29, no. 5, 2019, pp. 2929–2987.

\([4]\) F. Baccelli, Ke Feng and S. Foss. "Poisson Hail on Wireless Ground."
\(\text{https://arxiv.org/pdf/2501.10712}\)

Stability analysis of two-class retrial systems with constant retrial rates and general service times

Konstantin Avrachenkov

We establish stability criterion for a two-class retrial system with Poisson inputs, general class-dependent service times and class-dependent constant retrial rates. We also characterize an interesting phenomenon of partial stability when one orbit is tight but the other orbit goes to infinity in probability. All theoretical results are illustrated by numerical experiments. Possible generalizations will also be discussed.

The talk is based on a joint paper with Evsey Morozov and Ruslana Nekrasova \[1\].

Bibliography

\([1]\) Avrachenkov, K., Morozov, E., and Nekrasova, R., Stability analysis of two-class retrial systems with constant retrial rates and general service times. Performance Evaluation, v.159, 2023. https://arxiv.org/abs/2110.09840

The random timestep Euler method and its continuous dynamics

Jonas Latz

ODE solvers with randomly sampled timestep sizes appear in the context of chaotic dynamical systems, differential equations with low regularity, and, implicitly, in stochastic optimisation. In this work, we propose and study the stochastic Euler dynamics – a continuous-time Markov process that is equivalent to a linear spline interpolation of a random timestep (forward) Euler method. We understand the stochastic Euler dynamics as a path-valued ansatz for the ODE solution that shall be approximated. We first obtain qualitative insights by studying deterministic Euler dynamics which we derive through a first order approximation to the infinitesimal generator of the stochastic Euler dynamics. In the context of linear ODEs, these determinstic Euler dynamics describe the dynamics of the expectation of the stochastic Euler dynamics. Then we show convergence of the stochastic Euler dynamics to the ODE solution by studying the associated infinitesimal generators and by a novel local truncation error analysis. Next we prove stability by an immediate analysis of the random timestep Euler method and by deriving Foster–Lyapunov criteria for the stochastic Euler dynamics; the latter also yield bounds on the speed of convergence to stationarity. The paper ends with a discussion of second-order stochastic Euler dynamics and a series of numerical experiments that appear to verify our analytical results.

Bibliography

\([1]\) Jonas Latz. “The random timestep Euler method and its continuous dynamics." arXiv eprints, 2408.01409, 2024.