Hacker News new | past | comments | ask | show | jobs | submit login

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.




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.


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.


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.




Consider applying for YC's W25 batch! Applications are open till Nov 12.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: