Dynamics and random structures

Topics

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.

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.

Members

Lewis Bowen

Department of Mathematics, UT Austin
lpbowen@math.utexas.edu
Read More »

Thibaud Taillefumier

Department of Mathematics and Department of Neuroscience
taillef@math.utexas.edu
512 475 8145
Read More »

Natasa Dragovic

Department of Mathematics
ndragovic@math.utexas.edu
Read More »

Virag Shah (Postdoctoral Fellow 2016)

ECE dept., UT Austin
virag@utexas.edu
Read More »

Ari Arapostathis

Department of Electrical and Computer Engineering, UT Austin
ari@ece.utexas.edu
512 590 4224
Read More »

Sanjay Shakkottai

Department of Electrical and Computer Engineering, UT Austin
shakkott@austin.utexas.edu
512 471 5376
Read More »

Pranav Madadi

Department of Electrical and Computer Engineering, UT Austin
ee10b024@iith.ac.in
Read More »

Ngoc Mai Tran

Department of Mathematics, UT Austin
ntran@math.utexas.edu
Read More »

Abishek Sankararaman

Department of Electrical and Computer Engineering, UT Austin
abishek@utexas.edu
Read More »

Mayank Manjrekar

Department of Mathematics, UT Austin
mmanjrekar@math.utexas.edu
Read More »

Gustavo de Veciana

Department of Electrical and Computer Engineering, UT Austin
gustavo@ece.utexas.edu
512 471 1573
Read More »

François Baccelli

Department of Mathematics and Deparment of Electrical and Computer Engineering, UT Austin
baccelli@math.utexas.edu
512 471 17 54
Read More »

Antonio Sodre

Department of Mathematics, UT Austin
asodre@math.utexas.edu
Read More »

Publications

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
2017-04-14_1000789

Metastability of Queuing Networks with Mobile Servers

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

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
2016-10-16_1000749

Iterated Gilbert Mosaics and Poisson Tropical Plane Curves

Francois Baccelli and Ngoc Tran https://arxiv.org/abs/1610.08533
2016-05-20_1000948

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
2016_1000586

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
2016_1000816

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
2016_1000818

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
2016_1000824

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
2015-10-21_1000150

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
2015-01-22_1000165

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
2014-04-19_1000152

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

Ari Arapostathis, Anup Biswas and Luis Caffarelli Arxiv 2014
Download PDF
2014-04-08_1000146

Mutual Service Processes in R^d, Existence and Ergodicity

François Baccelli, Fabien Mathieu and Ilkka Norros ArXiv 2014
Download PDF
2014-02-28_1000830

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
2013-11-15_1000291

Queuing Networks with Varying Topology – A Mean-Field Approach

François Baccelli, Alexandre Rybko and Senya Shlosman Arxiv 2013
Download PDF
2000-01-01_1001035

Interference Queuing Networks on Grids

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