Large Deviations Without Principle: Join the Shortest Queue




Shwartz, Adam (Haifa, Israel)
adam@ee.technion.ac.il
(joint work with Ad Ridder, Vrij University, Amsterdam)

The theory of large deviations is an important tool in calculating probabilities of rare events. This theory was applied to several queueing systems, including the two-dimensional symmetric ``Join the Shortest Queue'' system and some variants. The calculation of probabilities of rare events usually proceeds as follows:

1. Formulate the practical question as a large-deviation question,

2. Show the validity of the large-deviations principle,

3. Characterize the rate function, and

4. Calculate the desired probability.

However, for the original JSQ system, 2 is not currently known, except for the symmetric, 2-dimensional case.

We show that tools from the theory of large deviations can be applied, even though the principle does not. We calculate the most likely path as well as the probability of overflow and the most likely path to overflow for the original JSQ system in any dimension (2 or larger).