Large deviations of queues sharing a randomly time-varying server (Q941712)

The paper considers a discrete-time model where multiple queues, each with its own exogenous arrival process, are served by a server whose capacity varies randomly and asynchronously with respect to different queues. It considers the following problem of controlling large deviations of the queues: find a scheduling rule, which is optimal in the sense of maximizing \(\min_i \left[\lim_{n \to \infty} \frac{-1}{n}\log P(a_i Q_i > n) \right]\), where \(Q_i \) is the length of the \(i\)-th queue in a stationary regime, and \(a_i > 0\) are parameters. The paper gives a characterization of the upper bound on this expression under any scheduling rate, and of the lower bound on it under the EXP (exponential) rule. It is proved that the two bounds match, thus proving optimality of the EXP rule. To overcome complications in analysis of the system in the large deviations regime, the author introduces and proves a refined sample path large deviations principle (refined Mogulskii theorem), which is of independent interest.