Abstract: The First-Come-First-Serve multi-server queue is a fundamental building block of many models in operations management and operations research. In 1962, John Kingman proved a simple and explicit bound for the steady-state number of jobs waiting in queue in the special case when there is only one server (Kingman (1962)). His now famous bound is a simple function of a few moments of the inter-arrival and service distributions, and scales like 1/(1-p) as the traffic intensity p approaches 1. The existence of an equally simple, explicit, and general bound for the multi-server setting which similarly scales as 1/(1-p) has been an open question for over fifty years (Daley (1997), Gupta et al. (2010)).
In Goldberg and Li (2017), we answer this question affirmatively, proving the first multi-server analogue of Kingman's bound. Our main results are bounds for the tail of the steady-state queue length and the steady-state probability of delay, where the strength of our bounds (e.g. in the form of tail decay rate) is a function of how many moments of the inter-arrival and service distributions are assumed finite. Our simple and explicit bounds scale gracefully even when the number of servers grows large and the traffic intensity converges to one simultaneously, as in the Halfin-Whitt scaling regime, which is popular in the analysis of service systems.
Our proofs proceed by explicitly analyzing the bounding process which arises in the stochastic comparison bounds of Gamarnik and Goldberg (2013) and Goldberg (2016) for multi-server queues. Along the way we derive several novel results for suprema of random walks with stationary increments and negative drift, pooled renewal processes, and various other quantities which may be of independent interest.

References
Daley, D.J.: Some results for the mean waiting-time and workload in GI/GI/k queues. In: Dshalalow, J.H. (ed.) Frontiers in Queueing: Models and Applications in Science and Engineering, Boca Raton, FL, USA, pp. 3559 (1997).
Gamarnik, D., and D. Goldberg: Steady-state GI|G|n queue in the HalfinWhitt regime. The Annals of Applied Probability 23.6 (2013): 2382-2419.
Goldberg, D.: On the steady-state probability of delay and large negative deviations for the GI|GI|n queue in the Halfin-Whitt regime. arXiv preprint arXiv:1307.0241 (2016). https://arxiv.org/abs/1307.0241v2 .
Goldberg, D., and Y. Li: Simple and explicit bounds for multi-server queues with universal 1/(1-rho) scaling." arXiv preprint arXiv:1706.04628 (2017).
Gupta, V., M. Harchol-Balter, J. G. Dai, and B. Zwart: On the inapproximability of M/G/K: why two moments of job size distribution are not enough."Queueing Systems 64.1 (2010): 5-48.
Kingman, J. F. C.: On queues in heavy traffic. Journal of the Royal Statistical Society. Series B (Methodological) (1962): 383-392.