The Curse of the First-In First-Out Queue Discipline (2012) [pdf](ctic.au.dk)
ctic.au.dk
The Curse of the First-In First-Out Queue Discipline (2012) [pdf]
http://ctic.au.dk/fileadmin/www.ctic.au.dk/New_Trends_in_Mechanism_Design_II/Abstracts/Lars_Peter_Oesterdal_abstract.pdf
7 comments
This is a game in which agents can choose their arrival time. Maybe it wouldn't work so well in a scenario where everyone is trying to get something done during lunch hour or after work.
[deleted]
I'm trying to relate this back to computer systems if its even possible, say comparing it to scheduling block requests from multiple processes to a block device, if the LIFO discipline maximizes welfare, I assume welfare in such system would be average response time, where response time here = queue time + service time of the block requests. When the block device is saturated and starts queuing, I guess one benefit would be that the block requests with the smallest waiting time would be served first, and improve responsiveness, but unless some kind of deadline is added you might have long tail where certain block requests don't get to be serviced.
But since the paper assume there's an opening time, perhaps then is not applicable for the block device example I gave above, maybe a more comparable example would be a traffic spike to a web application after some announcement, and how an http framework/library might 'choose' http requests to service. My understanding is that most framework/libraries just implicitly delegate to the OS process scheduler.
But since the paper assume there's an opening time, perhaps then is not applicable for the block device example I gave above, maybe a more comparable example would be a traffic spike to a web application after some announcement, and how an http framework/library might 'choose' http requests to service. My understanding is that most framework/libraries just implicitly delegate to the OS process scheduler.
Also for those who enjoyed this paper, I think you will also like CMU's Prof. Mor Harchol-Balter's book[1] on queuing theory applied for designing, and analyzing performance of, computer systems.
Personally, I don't know of any other book that covers so well the application of queuing theory to computer systems.
[1] http://www.cs.cmu.edu/~harchol/PerformanceModeling/book.html
Personally, I don't know of any other book that covers so well the application of queuing theory to computer systems.
[1] http://www.cs.cmu.edu/~harchol/PerformanceModeling/book.html
I consider this to be the key quote in understanding why the authors ultimately considered LIFO to be superior to FIFO:
"In our framework, we considered agent preferences to be identical and associated with a linear cost of waiting."
In my experience, this is not true. For me, waiting 20 minutes on hold does not have the same cost as waiting 1 minute 20 times throughout the day. It is likely the same for a business. Having 30 customers wait 1 minute is unlikely to lose a customer; having 1 customer wait 30 minutes and the others wait no time is likely to lose that 30-minute customer. Unfairness has its own cost as well. In my opinion, the invalid assumption of linear cost of waiting makes their framework invalid for application to humans.
"In our framework, we considered agent preferences to be identical and associated with a linear cost of waiting."
In my experience, this is not true. For me, waiting 20 minutes on hold does not have the same cost as waiting 1 minute 20 times throughout the day. It is likely the same for a business. Having 30 customers wait 1 minute is unlikely to lose a customer; having 1 customer wait 30 minutes and the others wait no time is likely to lose that 30-minute customer. Unfairness has its own cost as well. In my opinion, the invalid assumption of linear cost of waiting makes their framework invalid for application to humans.
For example, a queue in a post office. With FIFO every member has to wait for x units, where the unit is the time to handle one member and x is the size of the queue. With LIFO, most members have to wait for 1 units, but a few members have to wait on the order of x^2.
Someone correct me if my interpretation is incorrect.
I think LIFO queue would make an interesting experiment in a real world scenario, in contrast to FIFO used almost everywhere. Just make sure there is a maximum time limit set for those who are stuck in the back of the queue. This way most members get out quickly, and a few have to wait for whatever is the maximum time limit or close to that.
Someone correct me if my interpretation is incorrect.
I think LIFO queue would make an interesting experiment in a real world scenario, in contrast to FIFO used almost everywhere. Just make sure there is a maximum time limit set for those who are stuck in the back of the queue. This way most members get out quickly, and a few have to wait for whatever is the maximum time limit or close to that.
Perhaps 70% could be LIFO and 30% FIFO. This will give an incentive for people to visit when there is no queue at all, but everyone will eventually get served. The problem would be to uniquely identify someone to avoid cheating.
I'm glad science has come up with a new theory of how to make me even angrier while waiting in line at the airline check-in desk :)
The obvious strategy is to avoid entering the LIFO queue until right before a servicer is about to open up. Which then implies a FIFO queue will form for whoever is able to best enter the LIFO queue immediately before a dequeue. If the LIFO queue manager insists on adding people to the queue before they want, then that simply moves the "event horizon" further away and the FIFO will form there.
In the event they attempt track your face or otherwise make the event horizon stateful, then bring a disguise.
Frankly, I'd be happy if more places simply used a single queue to reduce variance, and if people waiting more than a few minutes were compensated for their time to avoid the moral hazard of intentional understaffing.