7 ms·
Another fun surprising result from queuing theory is that if you have a buffer of pending RPC's that have some deadline, it is better to service them in a "unfa
by jinpan 7y ago
Another fun surprising result from queuing theory is that if you have a buffer of pending RPC's that have some deadline, it is better to service them in a "unfair" LIFO order, as opposed to a fairer FIFO order. [0] goes into more gory details.
In the bank example from the article, LIFO would dramatically shorten the median wait time (~5 minutes), at the cost of really upsetting customers [1]. In the case of a support queue, where the waiters are blind to each other, this cost could be reconsidered ...
[0] https://arxiv.org/pdf/1008.4895.pdf https://arxiv.org/pdf/1008.4895.pdf
[1] from the article, "We really, really hate it when someone shows up after us but gets served before us.
- pstuart 7y agoI thought the queuing algorithm for banks was to line up transactions so the largest go through first to increase the opportunity for overdraft fees.
- ahmedalsudani 7y agoDebits first, credits last—just as the lord commanded.
- gumby 7y agoBy the way "debit" means "given" -- as in you "give" the money to the bank. "credit" means the money is being taken from them. Tells you a lot about their attitude to your money!
- irishsultan 7y agoDebit comes from a latin verb that means to owe, and credit from a verb that means to trust. So a debit card is for the money that the bank owes you, and a credit card is for money that the bank trusts you will pay them back.
- dullgiulio 7y agoSure, which implies the money I store in the bank is debit they owe me. But worded that way I might be induced to think I deserve some kind of interest payment...
- jtms 7y agoIt doesn’t just imply it, that is exactly what it is. The bank is loaning your money out and then some (multiplied by whatever the current reserve ratios are). They quite literally don’t have the money you deposited, but just owe it back to you if you ask for it. That’s one of the ways a bank makes money.
- WorldMaker 7y agoIt's easy to forget in an era where checking and savings accounts have interest rates so low the average person earns no interest on their cash.
- c3534l 7y agoThat's the etymological fallacy. Debit and credit just mean left and right side of the ledger.
- awshepard 7y agoI heard from a customer service rep at a bank that they did that based on customer feedback. The general reasoning being that large amounts were most likely to be things like housing payments and car payments, where missing payments would incur larger charges from those companies, and/or put housing or transportation at risk.
- ulucs 7y agoAfter a while people would grow wise of this tactic and start redialing after waiting for some time. We could build a whole lot of efficient and beautiful systems, if only not for the people...
- SilasX 7y agoExactly. I've never had the time to dig into it, but these LIFO-optimality results always strike me as being non-physical or introducing some implicit hard-to-model effects.[1] Like you say, people can just re-enter the queue, or (in meatspace) form a meta-queue that vies for entering the moment it has an open slot, reproducing FIFO all over again. Furthermore, you get a lot of pro-cooperation effects (necessary for queues to work at all) by giving people "skin in the game" in the form of valuing their place in line. Once people lose nothing by inventing a new name and re-entering the line, that's all gone, and they no longer have an incentive not to be disruptive, which throws off disproportionate negative utility onto the rest of the system. One day, I promise, I will unpack this result. [1] My comment from 2015 expressing similar reservations: https://news.ycombinator.com/item?id=10182781 https://news.ycombinator.com/item?id=10182781
- papln 7y agoWhat's wrong with degrading from LIFO to a random queue due to client retry, when you're starting from a FIFO that is already failing client expectations?
- SilasX 7y agoNothing, if it's just used for that (narrow, least-bad, degraded) situation. I was addressing the more general point that LIFO queues have some actionable superiority over FIFO in the general case because of the theoretical results cited in the literature.
- gpderetta 7y agoSpherical customers in a vacuum.
- 7y ago
- deleted 7y ago[deleted]
- macleginn 7y agoThe paper also suggests that they should turn some customers away altogether to achieve lower MWT, which makes this method even less appealing ("We must drop a small fraction of packets in order to dramatically improve delay for the remaining ones. <...> [Our] experiments, combined with those of [10] suggest strongly that the drop rate scaling may be inconsequential in many real world applications.")
- radomir_cernoch 7y agoThis explains a lot when applied to replying to e-mails.
- burtonator 7y agoThis isn't really unsurprising though. The problem is that your outliers are going to rise significantly. You're basically trading some higher latency for lower median latencies.
- jules 7y agoThat's just a result of your loss function. If you consider going over the deadline by a lot equally bad as going over the deadline a little, then of course. This doesn't apply to people waiting.