Dynamics and random structures


Control of queuing networks

One of the classical problems in queuing theory is to schedule customers/jobs in an optimal way. These problems are known as the scheduling problems. They arise in a wide variety of applications, in particular, whenever there are different customer classes present competing for the same resources. In a recent work “Ergodic control of multi-class M/M/N+M queues in the Halfin-Whitt regime”, Ari Arapostathis, Anup Biswas and Guodong Pang solved an ergodic control problem for multi-class many server queuing networks. The optimal solution of the queuing control problem can be approximated by that of the corresponding ergodic diffusion control problem in the limit. The proof technique introduces a new method of spatial truncation for the diffusion control problem.

Dynamic games with asymmetric information

In the paper, Deepanshu Vasal considered a general finite-horizon non-zero-sum dynamic game with asymmetric information with N selfish players, where there exists an underlying state of the system that is a controlled Markov process, controlled by players’ actions. In each period, a player makes both private and common observations about the state of the system. An appropriate notion of equilibrium for such processes includes Perfect Bayesian equilibrium (PBE) which consists of a strategy and a belief profile of the players. Such equilibrium strategies and beliefs are coupled together across time and thus computing equilibria for such games is equivalent to solving a fixed-point equation which grows double exponentially with time, rendering such problems intractable. In this paper, a sequential decomposition methodology is presented to compute structured perfect Bayesian equilibria (SPBE) of this game. In general, these equilibria exhibit signaling behavior, i.e. players’ actions reveal part of their private information that is payoff relevant to other users.

Metastability of queuing networks with mobile servers

In a paper entitled Metastability of Queuing Networks with Mobile Servers, A. Rybko, S. Shlosman, A. Vladimorov and F. Baccelli study symmetric queuing networks with moving servers and FIFO service discipline. The mean-field limit dynamics demonstrates unexpected behavior which is attributed to the meta-stability phenomenon. Large enough finite symmetric networks on regular graphs are proved to be transient for arbitrarily small inflow rates. However, the limiting non-linear Markov process possesses at least two stationary solutions. The mean-field analysis is based on the Non Linear Markov Process developed for this type of queuing networks in Queuing Networks with Varying Topology – A Mean-Field Approach.

Moving user time series in SNR stochastic geometry

With Pranav Madadi, F. Baccelli, and G. de Veciana analyzed the temporal variations in the Shannon rate experienced by a user moving along a straight line in a cellular network represented by a Poisson-Voronoi tessellation. We consider a network that is shared by static users distributed as a Poisson point process and analyzed the time series of the final shared rate and the number of users sharing the network. The paper On Shared Rate Time Series for Mobile Users in Poisson Networks was focused on the noise limited case.

Poisson Hail

Consider a queue where the server is the Euclidean space, the customers are random closed sets (RACS) of the Euclidean space. These RACS arrive according to a Poisson rain and each of them has a random service time (in the case of hail falling on the Euclidean plane, this is the height of the hailstone, whereas the RACS is its footprint). The Euclidean space serves customers at speed 1. The service discipline is a hard exclusion rule: no two intersecting RACS can be served simultaneously and service is in the First In First Out order (only the hailstones in contact with the ground melt at speed 1, whereas the other ones are queued; a tagged RACS waits until all RACS arrived before it and intersecting it have fully melted before starting its own melting). We prove that this queue is stable for a sufficiently small arrival intensity, provided the typical diameter of the RACS and the typical service time have finite exponential moments.

In Shape Theorems For Poisson Hail on a Bivariate Ground, H. Chang, S. Foss and F. Baccelli have extended this Poisson Hail model to the situation where the service speed is either zero or infinity at each point of the Euclidean space. Tools pertaining to sub-additive ergodic theory are used to establish shape theorems for the growth of the ice-heap under light tail assumptions on the hailstone characteristics. The asymptotic shape depends on the statistics of the hailstones, the intensity of the underlying Poisson point process and on the geometrical properties of the zero speed set.

Spatial birth and death processes

Spatial point processes involving birth and death dynamics are ubiquitous in networks. Such dynamics are particularly important in peer-to-peer networks and in wireless networks. In the paper “Mutual Service Processes in R^d, Existence and Ergodicity”, Fabien Mathieu (Bell Laboratories), Ilkka Norros (VTT) and François Baccelli proposed a way to analyze the long term behavior of such dynamics on Euclidean spaces using coupling techniques. This line of though is continued by Mayank Manjrekar on other classes of processes like hard core spatial birth and death processes.

Spatial Birth-Death Wireless Networks

In this paper, Abishek Sankararaman and François Baccelli introduce a new form of spatial dynamics motivated by ad-hoc wireless networks. They study a birth death process where particles arrive in space as a Poisson process in space and time, and depart the system on completion of file transfer. The instantaneous rate of file transfer of any link is given by the Shannon formula of treating interference as noise. As the instantaneous interference seen by a link is dependent on the configuration of links present, this dynamics is an example of one where dynamics shapes geometry and in turn the geometry shapes the dynamics. In this paper, the authors establish a sharp phase-transition for stability of such dynamics. Moreover, whenever such dynamics is stable, they prove that the steady state is a clustered point process. Through simulations, they also argue that such dynamics cannot be simplified to any form of non-spatial queuing type dynamics. Lately, this paper with Sergey Foss extended the dynamics on grids to show a similar stability phase-transition in the case of infinite network, i.e. in an infinite grid.


Lewis Bowen

Department of Mathematics, UT Austin
Read More »

Thibaud Taillefumier

Department of Mathematics and Department of Neuroscience
512 475 8145
Read More »

Natasa Dragovic

Department of Mathematics
Read More »

Virag Shah (Postdoctoral Fellow 2016)

ECE dept., UT Austin
Read More »

Ari Arapostathis

Department of Electrical and Computer Engineering, UT Austin
512 590 4224
Read More »

Sanjay Shakkottai

Department of Electrical and Computer Engineering, UT Austin
512 471 5376
Read More »

Pranav Madadi

Department of Electrical and Computer Engineering, UT Austin
Read More »

Ngoc Mai Tran

Department of Mathematics, UT Austin
Read More »

Abishek Sankararaman

Department of Electrical and Computer Engineering, UT Austin
Read More »

Mayank Manjrekar

Department of Mathematics, UT Austin
Read More »

Gustavo de Veciana

Department of Electrical and Computer Engineering, UT Austin
512 471 1573
Read More »

François Baccelli

Department of Mathematics and Deparment of Electrical and Computer Engineering, UT Austin
512 471 17 54
Read More »

Antonio Sodre

Department of Mathematics, UT Austin
Read More »


2018-09-21_1001118 2018-01-10_1001050 2017-06-01_1000994

Spatial Birth Death Wireless Networks

Abishek Sankararaman and François Baccelli IEEE Transactions on Information Theory 63(6): 3964-3982 (2017)
Download PDF

Metastability of Queuing Networks with Mobile Servers

F. Baccelli, A. Rybko, S. Shlosman, A. Vladimirov https://arxiv.org/abs/1704.02521
Download PDF

On solutions of mean field games with ergodic cost

Ari Arapostathis, Anup Biswas, and Johnson Carroll Journal de Mathematiques Pures et Appliquees vol. 107, no. 5, pp. 205-251, 2017

Iterated Gilbert Mosaics and Poisson Tropical Plane Curves

Francois Baccelli and Ngoc Tran https://arxiv.org/abs/1610.08533

Shape Theorems For Poisson Hail on a Bivariate Ground

Francois Baccelli, Hector A. Chang-Lara, and Sergey Foss ArXiv 2016
Download PDF
2016-05-01_1000915 2016-01-14_1000623

Point-Shift Foliation of a Point Process

Francois Baccelli and Mir-Omid Haji-Mirsadeghi ArXiv 2016
Download PDF

Ergodic Diffusion Control of Multiclass Multi-Pool Networks in the Halfin–Whitt Regime

Ari Arapostathis and Guodong Pang Annals of Applied Probability vol. 26, no. 5, pp. 3110– 3153, 2016

Risk-sensitive control and an abstract Collatz-Wielandt formula

Ari Arapostathis, Vivek S. Borkar, and K. Suresh Kumar Journal of Theoretical Probability vol. 29, no. 4, pp. 1458-1484, 2016

The Dirichlet problem for stable-like operators and probabilistic representations

Ari Arapostathis, Anup Biswas, and Luis Caffarelli Communications in Partial Differential Equations vol. 41, no. 9, pp. 1472-1511, 2016

End-to-End Optimization of High Throughput DNA Sequencing

Eliza O'Reilly, Francois Baccelli, Gustavo de Veciana, Haris Vikalo Journal of Computational Biology 2016
Download PDF

Ergodic Control of Multi-class M/M/N+M Queues in the Halfin-Whitt Regime

Ari Arapostathis, Anup Biswas and Guodong Pang Annals of Applied Probability vol. 25, no. 6, pp. 3511-3570, 2015
Download PDF
2015-06-18_1000441 2015-04-28_1000153

Controlled Equilibrium Selection in Stochastically Perturbed Dynamics

Ari Arapostathis, Anup Biswas and Vivek Borkar Arxiv 2015
Download PDF

Resource Allocation: Realizing Mean-Variability-Fairness Tradeoffs

Vinay Joseph, Gustavo de Veciana and Ari Arapostathis IEEE Transactions on Automatic Control 60(1):19-33 January 2015
Download PDF

On a Class of Stochastic Differential Equations With Jumps and its Properties

Ari Arapostathis, Anup Biswas and Luis Caffarelli Arxiv 2014
Download PDF

Mutual Service Processes in R^d, Existence and Ergodicity

François Baccelli, Fabien Mathieu and Ilkka Norros ArXiv 2014
Download PDF

Convergence of the relative value iteration for the ergodic control problem of nondegenerate diffusions under near- monotone costs

Ari Arapostathis, Vivek S. Borkar, and K. Suresh Kumar vol. 52, no. 1, pp. 1–31, 2014

Queuing Networks with Varying Topology – A Mean-Field Approach

François Baccelli, Alexandre Rybko and Senya Shlosman Arxiv 2013
Download PDF

Interference Queuing Networks on Grids

Abishek Sankararaman, François Baccelli and Sergey Foss ArXiv 2017
Download PDF