This paper considers a parallel system of queues fed by independent arrival streams, where the service rate of each queue depends on the number of customers in all of the queues. Necessary and sufficient conditions for the stability of the system are derived, based on stochastic monotonicity and marginal drift properties of multiclass birth and death processes. These conditions yield a sharp characterization of stability for systems where the service rate of each queue is decreasing in the number of customers in other queues, and has uniform limits as the queue lengths tend to infinity. The results are illustrated with applications where the stability region may be nonconvex.
Consider $N$ particles moving independently, each one according to a subcritical continuous-time Galton–Watson process unless it hits $0$, at which time it jumps instantaneously to the position of one of the other particles chosen uniformly at random. The resulting dynamics is called Fleming–Viot process. We show that for each $N$ there exists a unique invariant measure for the Fleming–Viot process, and that its stationary empirical distribution converges, as $N$ goes to infinity, to the minimal quasi-stationary distribution of the Galton–Watson process conditioned on non-extinction. Nous considérons $N$ particules indépendantes. Chaque particule suit l’évolution d’un processus de Galton–Watson sous-critique jusqu’au moment où elle touche $0$. À cet instant, cette particule choisit uniformément au hasard la position d’une des autres particules et y saute. Ce processus est appelé Fleming–Viot. Nous montrons que pour chaque entier $N$, il existe une unique mesure invariante pour le processus de Fleming–Viot, et que la mesure empirique stationnaire converge vers la loi quasi-stationnaire minimale d’un processus de Galton–Watson conditionné à ne pas mourir.
1 June 2012 in IEEE/ACM Transactions on Networking
We investigate the scheduling of a common resource between several concurrent users when the feasible transmission rate of each user varies randomly over time. Time is slotted, and users arrive and depart upon service completion. This may model, for example, the flow-level behavior of end-users in a narrowband HDR wireless channel (CDMA 1xEV-DO). As performance criteria, we consider the stability of the system and the mean delay experienced by the users. Given the complexity of the problem, we investigate the fluid-scaled system, which allows to obtain important results and insights for the original system: 1) We characterize for a large class of scheduling policies the stability conditions and identify a set of maximum stable policies, giving in each time-slot preference to users being in their best possible channel condition. We find in particular that many opportunistic scheduling policies like Score-Based, Proportionally Best, or Potential Improvement are stable under the maximum stability conditions, whereas the opportunistic scheduler Relative-Best or the cμ-rule are not. 2) We show that choosing the right tie-breaking rule is crucial for the performance (e.g., average delay) as perceived by a user. We prove that a policy is asymptotically optimal if it is maximum stable and the tie-breaking rule gives priority to the user with the highest departure probability. We will refer to such tie-breaking rule as myopic. 3) We derive the growth rates of the number of users in the system in overload settings under various policies, which give additional insights on the performance. 4) We conclude that simple priority-index policies with the myopic tie-breaking rule are stable and asymptotically optimal. All our findings are validated with extensive numerical experiments.
We consider a matching system where items arrive one by one at each node of a compatibility network according to Poisson processes and depart from it as soon as they are matched to a compatible item. The matching policy considered is a generalized max-weight policy where decisions can be noisy. Additionally, some of the nodes may have impatience, that is, leave the system before being matched. Using specific properties of the max-weight policy, we construct a simple quadratic Lyapunov function. This allows us to establish stability results, to prove exponential convergence speed toward the stationary measure, and to give explicit bounds for the stationary mean of the largest queue size in the system. We finally illustrate some of these results using simulations on toy examples. Funding: N. Soprano-Loto is partially supported by Aristas, MathAmSud [Grant RSPSM (Random Structures and Processes in Statistical Mechanics)], and ANR (Agence Nationale de la Recherche) [Grant PRC (Projets de Recherche Collaborative) MATCHES (CE40)].
Several recent experiments have established by measuring the Mandel parameter that the number of Rydberg excitations in ultracold gases exhibits sub-Poissonian statistics. This effect is attributed to the Rydberg blockade that occurs due to the strong interatomic interactions between highly excited atoms. Because of this blockade effect, the system can end up in a state in which all particles are either excited or blocked: a jamming limit. We analyze appropriately constructed random-graph models that capture the blockade effect, and derive formulae for the mean and variance of the number of Rydberg excitations in jamming limits. This yields an explicit relationship between the Mandel parameter and the blockade effect, and comparison to measurement data shows strong agreement between theory and experiment.