Storage of the single-server queues.

Efficient storage and maintenance of queues is a fundamental problem of computer science. In this paper, we study a stochastic model of linear storage devices with the M/M/1 queue as the underlying process of arrivals and departures. We present probabilistic bounds on the wasted space under the FIFO and processor-shared service disciplines and a large class of practical allocation policies.