And what if items are processed at exactly the same rate they are added? Something is missing from this thesis. There must be an additional assumption at play beyond what is stated in the article.
The assumption you're looking for is there but relatively inconspicuous. He mentioned a M/M/1/∞ queue but then didn't go into the details about the M/M/1 part. From the Wikipedia page[0]:
> an M/M/1 queue represents the queue length in a system having a single server, where arrivals are determined by a Poisson process...
So the arrival times are not arriving at any fixed rate, but according to a Poisson distribution. In the article he did reference this fact right before the first plot:
> (For the wonks: I used a Poisson arrival process and exponentially distributed processing times)
And then finally, he answered this question more directly in the comments to the article:
> What’s to prevent the system from bouncing between “1 task in processor & 1 task in queue” and “1 task in processor & 2 tasks in queue” while maintaining 100% utilization?
> Nothing! That could totally happen in a queueing system. However, the arrival process would need to be tuned quite precisely to the processing rate. You would need to watch the status of the processor and, when a task finishes, only then insert a new task into the queue. But this implies a shell game: if you always have a task ready to put into the queue when it needs to be padded back out, then isn’t that task in a sense already “queued”?
> Instead, in queueing theory we usually assume a random arrival process: sometimes a minute may pass between arrivals into the queue; sometimes only a second. So the system can’t bounce for arbitrarily long between 1-in-queue and 2-in-queue states. Eventually, one of two things will randomly occur:
> 1. From the 1-in-queue state, the active task finishes processing before a new task arrives, bringing queue size to 0.
> 2. From the 2-in-queue state, a new task arrives in the queue before the active task finishes, causing the queue size to grow to 3.
Of course I know what was missing. My comment was more about making the implicit more explicit. I am not the only one who immediately thought of the above as a counter-example to the bold text (repeated twice) in the article.
It's not just the arrival rate that is a poisson distribution, but it's also the processing time being a poisson distribution that really sets the table for the scenario the article is addressing. For me, it's easier to understand in a grocery store situation, where customers arrive in a poisson distribution at the checkout line, and that each cart has a poisson distribution on how long it takes to process the items in the cart. That second level of variance is key to the queue buildup, especially as the grocer checker reaches 100% utilization.
Theoretically I think that’s possible. In a practical setting it is not since task arrival times are of a probability distribution; this means that utilization is not 100% and therefore queues do not grow to infinity. Given the author’s point about ~80% and above being bad, I imagine the immediate processing scenario to still be pathological.
> an M/M/1 queue represents the queue length in a system having a single server, where arrivals are determined by a Poisson process...
So the arrival times are not arriving at any fixed rate, but according to a Poisson distribution. In the article he did reference this fact right before the first plot:
> (For the wonks: I used a Poisson arrival process and exponentially distributed processing times)
And then finally, he answered this question more directly in the comments to the article:
> What’s to prevent the system from bouncing between “1 task in processor & 1 task in queue” and “1 task in processor & 2 tasks in queue” while maintaining 100% utilization?
> Nothing! That could totally happen in a queueing system. However, the arrival process would need to be tuned quite precisely to the processing rate. You would need to watch the status of the processor and, when a task finishes, only then insert a new task into the queue. But this implies a shell game: if you always have a task ready to put into the queue when it needs to be padded back out, then isn’t that task in a sense already “queued”?
> Instead, in queueing theory we usually assume a random arrival process: sometimes a minute may pass between arrivals into the queue; sometimes only a second. So the system can’t bounce for arbitrarily long between 1-in-queue and 2-in-queue states. Eventually, one of two things will randomly occur:
> 1. From the 1-in-queue state, the active task finishes processing before a new task arrives, bringing queue size to 0.
> 2. From the 2-in-queue state, a new task arrives in the queue before the active task finishes, causing the queue size to grow to 3.
[0]: https://en.wikipedia.org/wiki/M/M/1_queue