Dice and Queues

It's not explicitly mentioned in the article, but the arrival rate and queue sizes are related via Little's Law [0] — the average number of people in a system is equal to the arrival rate multiplied by the mean wait time, regardless of the arrival distribution, service distribution, or service order (e.g. FIFO, LIFO, random).

I was fortunate enough to take some great queueing theory classes in college, and fondly remember flailing about in Simio [1] trying to get a bank teller simulation to work. Really useful stuff to learn, although it did make me incredibly susceptible to Factorio and similar games.

[0] https://en.wikipedia.org/wiki/Little%27s_law

[1] https://www.youtube.com/watch?v=xCzAhKtucck

> In an ideal world, we wouldn’t need queues. Who likes waiting in lines after all? This would only be possible if the arrival rate of items in a queue was less than or equal to the departure rate and there were no variability in either. Not likely to happen in the real world.

It's not only possible if there's no variability. It's only possible if the arrival rate is always less than number of available processing slots, which can be engineered in a number of ways. (e.g. ensuring that the number of processing units is oversupplied, i.e. exceeds the maximum arrival rate + departure rate; or altering number of processing units dynamically so that utilisation never exceeds 80%.)

However, these approaches are generally not the lowest cost approaches, and so are only used when queueing is incredibly undesirable, e.g. when the cost of maintaining the queue exceeds the cost of holding the spare capacity.

One example for oversupply is airports - most airports have enough gates that incoming aircraft never have to queue, despite that meaning that many gates are empty for most of the day.

For dynamically adjusting capacity examples include listening thread pools for network applications which can spin up new waiting threads whenever the pool free count drops below a certain threshold (the threshold being decided based on the maximum arrival rate). Or a cloud service which spins up new servers whenever cpu utilisation exceeds 80%.

A simulation of queue behavior where you can intuitively get a feeling of what happens: https://queuewiz.queuemetrics.com/

How does this compare to the widely used Completely Fair Queue scheduler that Linux uses for block devices?

Enjoyed the read - thanks for sharing! Found a small typo here:

> For the service rate (λ), we can keep things simple and assume that our server can service 10 items per minute with zero variation.

I think it's supposed to be mu and not lambda

I disliked that they don't explain the logic in the ```arrivals()``` function, but it is because in a uniform distribution from 0 to 1 (which is what ```random()``` is), the probability that a value falls below 1/6 is exactly 1/6, i.e.:

P(random() < 1/6) ~= 1/6 .

Which is how they simulate a dice landing a "6". This explanation could be included in the text.

intereresting read. I might be wrong but I think the central limit theorem is what's contributing to the binomial distribution of arrivals approaching a normal distribution due to the summation of qi-1 + arrivals().

Over many iterations (minutes, hours), you accumulate the effects of these random additions. As a result, even though the distribution is binomial (or approximated Poisson), its behavior for large enough values and sums of multiple minutes becomes approximately gaussian due to CLT.

Does anyone have any good resources they'd recommend for learning queueing theory? I'd like to learn it

That was a nice read. Do you recommend any books for one who wants to get into queue theory?