[drivebycomment]

Classical misunderstanding of queueing. If you have a perfect control over an arrival, you can consider it as already queued. I.e. bank customers or grocery store checkout customers or online http requests for a service all arrive at random interval. You don't have a control over their arrival timing.

[cormacrelf]

This is not helped by the language used in the post. This was supposed to be an introduction to queuing, people shouldn’t come away with their classic misunderstandings completely intact.

> When a system has steady-state 100% utilization, its queue will grow to infinity. (Emph mine.)

This is clearly false, there are clearly counterexamples where the queue does not grow that way. You don’t have control over the arrival rate etc but it could just be your lucky day. It would be more accurate to say you can’t guarantee that either the queue length or wait time are finite. Author didn’t include the words “assume the worst case” or anything like that. I feel like that’s a pretty crucial piece of framing that’s missing.

[marcosdumay]

The author didn't assume the worst case, he just didn't set the timeframe. Every queue with random arrive times that has processors operating at 100% of their capacity is guaranteed to eventually grow indefinitely (as in, you can name any size, it will become larger than it).

But on practice you also can not maintain 100% workload indefinitely either.

[cormacrelf]

Random dice rolls don’t preclude rolling 1 again and again forever, right? There’s an assumption here about the distribution of arrival times that hasn’t been stated.

[Jtsummers]

The model (M/M/1) is set up using the averages, not worst or best case. If you roll a die infinite times and get infinite 1s, then you have either got a loaded die (in which case its distribution is not the generally assumed uniform distribution from 1 to n, but just 1) or are extremely lucky, but the situation is still far from average.

> There's an assumption here about the distribution of arrival times that hasn't been stated.

Yes, it has, but not as explicitly as you may like. The author explicitly stated that they were considering an M/M/1 queue:

https://en.wikipedia.org/wiki/M/M/1_queue

And in the "What about 90%?" section specifically calls out what distributions they're using (which are the same as the ones you'd expect from that page on M/M/1 queues).

For the system under discussion, the average arrival rate is the first parameter, and the average processing rate is the second parameter. If you decide to only consider the case where everyone shows up half as often as the average, then you've changed the distribution being considered. Similarly, if you decide to only consider the case where tasks are completed twice as fast, then you've, again, changed the distribution.

Queuing theory isn't generally about picking a specific circumstance and saying, "Look, you can get really lucky and clear the queue in 10 minutes instead of 10 years, even though on average we would never expect that." The primary motivation (in applying it) is to consider the average circumstances. On average, if your arrival rate in an M/M/1 queue is the same as or faster than your processing rate, your queue size will grow indefinitely. Sure, you could get lucky and have a really slow day for customers and a really on-their-game worker, it is statistically possible, but over an arbitrarily large period of time we'd expect the arrival time to be too high for the processing time, and the queue to grow.

[cormacrelf]

Yes, I understand that, at least at a high level. I’m making a narrow point that the article didn’t teach us this and it actually was essential to understanding the claim. Quoting the article again:

> I won’t go into the M/M/1 part, as it doesn’t really end up affecting the Important Thing I’m telling you about. What does matter, however, is that ‘∞’.

This turned out to be wrong. It does end up affecting the Important Thing and the discussion was severely incomplete without it.

[setr]

The steady state is like Big-O notation; it’s already talking about the edge (as time grows to infinity). A single day deviation doesn’t really matter — your queue might shrink and grow a little day-to-day, but on average it’ll grow more than it shrinks, and you’re ultimately fucked.

If your utilization looked like 100% on one day, 0% on another, and flipping back and forth (allowing the queue to clear) then by definition your steady state isn’t 100%, its more like 50%.

And of course if your time bound is limited, or your potential customers is limited, then naturally everything is limited. But like big-O, the notion is to describe what happens when your inputs grows to infinity