ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Consider a Markov queueing system where there are NN servers who serve at rate 1, and new customers arrive into the system at a constant rate of λ\lambda. When a new customer arrives, they choose to join the queue behind the server with the shortest existing length. If there is more than one queue with the shortest length, simply choose one uniformly at random. Let us assume that λ<N\lambda < N so we have a stationary distribution for this chain. Denote Q=(q1,q2,…)Q = (q_1, q_2, \ldots) as the stationary distribution of this process, where qiq_i is the number of queues with \emph{at least} ii people in the queue. This model is known as the Join the shortest queue (JSQ) model.

As a simplification to this process, suppose that when a new customer arrives, and \emph{all} of the server queues have 2 people, then this customer leaves straight away. Let Q2Q_2 denote the corresponding stationary distribution for this modified process. This is a commonly used approximation for the full JSQ model. Can we use Stein's method to explicitly bound the difference ∣Ef(Q)−Ef(Q2)∣|\mathbb{E} f(Q) - \mathbb{E} f(Q_2)| for suitable ff?

Consider another simplification of the full JSQ process, where an new customer joins the shortest of kk randomly chosen queues. Let Q3Q_3 denote the stationary distribution of this process. What can we say about ∣Ef(Q)−Ef(Q3)∣|\mathbb{E} f(Q) - \mathbb{E}f(Q_3)|?

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.