7 ms·
Should the first in a queue be served last?
- paulhauggis 11y agoYou will then have the problem of everyone arriving late. It doesnt change anything. It just shifts the time.
- pkaye 11y agoWouldn't the people at the front of the line start leaving and coming back to the end?
- rabbyte 11y ago> It could be open to manipulation, with people leaving the queue and rejoining from the back in order to get served more quickly.
- Dylan16807 11y agoIs that even manipulation? You're not allowed to leave the line now as everyone after you hurts your standing? That sentence does not even come close to properly addressing it.
- rabbyte 11y agoIt's a quote from the article.
- Dylan16807 11y agoI know. pkaye mentioned one of the critical flaws with the plan, and you quoted the article as if he missed the part where it addressed the flaws. But it doesn't address them, it just says "maybe my plan doesn't make any sense, not my problem".
- rabbyte 11y agoI quoted the article where it concedes the point. Usually a system is only coherent within a set of assumptions, in this case the assumption is people can't easily rejoin or see their placement. That maybe doesn't hold for physical lines but the example the article goes into is an internet service where people have no control or awareness over their place in line. In any case, I'm just reiterating what the article says about this point, not sure what there was to disagree about.
- macspoofing 11y agoMaybe not. Maybe they wouldn't for the same reason why the last person doesn't generally just walk up to the front of the line. Social pressure.
- cornellwright 11y agoThe incentives don't quite work like that though. With normal FIFO queues you're free to abandon your place in line if, for example, you decide it's taking too long and you'd rather do something else. If later the line dies down you're free to go get back in line and you're not being a jerk. However if you get stuck too far back in the LIFO queue, then it's actually in your best interest to abandon it and come back later. But there's no socially appropriate way to do this. I think if you tried to do this in the real world it would quickly devolve into a mob. Random order would probably work better.
- Grue3 11y agoThere could be a machine that scans a person's boarding pass and assigns them a number. Then everyone is served by their number. And you can't get a different number if you try to scan your boarding pass again.
- im3w1l 11y agoThere is already a well known alternative to queues that minimizes wait time. Pre-assigned time slots.
- omginternets 11y agoPre-assigned time slots are really a specific optimization of a queue, and are only applicable when you know how long the work will take.
- lukev 11y agoOne thing the article doesn't mention is how this changes the final time to have all people processed. Wouldn't this result in (for example) flights leaving later, if people were in competition to arrive last?
- dominicgs 11y agoAbsolutely, the article presents the problem as trying to minimise the time that an individual wastes in a queue, not the problem of processing all of the people in the shortest time possible. In the airline example, the airline wants passengers to be at the gate before they begin boarding so that they can start looking for missing passengers as early as possible. I think we see this technique most often used by low cost carriers, and this is one of the many ways that they are able to turn aircraft around so quickly.
- dalke 11y agoIt does quote "In practice it would be very hard to implement a principle of serving the last in most physical queues where people physically queue up, for example when boarding an airplane. It's simply too difficult to manage for practical reasons." There's a real-world variation. At some airports people at the terminal go into a bus, which then takes them to a plane. This serves to mix and somewhat invert the queue, since the last people on the bus become the first to enter the plane. The question I have is, is there a change in the gate queuing behavior between flights that load directly at the gate, vs. one where people first enter a bus?
- joosters 11y agoThat might be tricky to measure, especially as it's not obvious whether your gate is going to be bus-loaded or just a walk to the plane.
- dalke 11y agoFor some gates it's obvious. When you're on the ground floor, with only roadway outside the door, then there will be an airside transfer bus. It's even more obvious when the neighboring gates also use buses.
- johnloeber 11y agoThis experiment has a startling result only because it runs counter to the established method of queueing. If instead of queues we had stacks (last in, first out), we would no doubt see people organize themselves into the stack in such ways that other time-wasting externalities would arise. I think the queue is a pretty good system to use, because it's effectively an auction for a spot at the top of the line, where you pay only with your time. This seems like it would balance incentives reasonably well. Come to think of it, it'd be interesting to see economic auction theory applied to queues.
- bsdlite 11y agoMaybe not exactly what you had in mind, but the economics of allocating scarce resources via queues is pretty well-established (and interesting). You might enjoy this read: http://www.jstor.org/stable/724744 http://www.jstor.org/stable/724744
- johnloeber 11y agoThanks, this is exactly what I was looking for.
- AnthonyMouse 11y ago> If instead of queues we had stacks (last in, first out), we would no doubt see people organize themselves into the stack in such ways that other time-wasting externalities would arise. The purpose of a line is that you have an inconsistent flow rate. If you always had less than one person arriving per minute and it took less than one minute to process one person then there would be no need for ordering the people waiting because there would be no people waiting. The trouble arises when that isn't what happens. At 10AM there is no line at the lunch counter but by 11AM or noon there are more people looking for food than there is serving capacity, so a line forms and remains until 1PM or 2PM when the rate of new customers has fallen back below serving capacity for long enough to process the backlog. A queue is inefficient because it causes everyone to wait e.g. 15 minutes during the busy period. If you use a stack instead of a queue then a person who arrived at 11AM and sees the number of people in line in front of them continue to increase will correctly deduce that continuing to wait is futile. They won't be served until ~1PM when the entire backlog is filled, so assuming they aren't allowed to reposition themselves in line immediately, they might as well just leave and come back later. And maybe resolve to get there by 10:45 next time, when demand is lower and everyone is still being served immediately. Which is where the efficiency comes from -- more people arrive either before or after the rush to avoid getting stuck at the bottom of the stack, so the wait time goes down. The trouble with it is that it lowers the average wait time but it makes the wait time for any particular individual completely unpredictable. You could end up being second to the top of the stack for several hours while everyone else is served immediately.
- csense 11y agoA FIFO queue is essentially like an auction where you use your wait time in order to bid for service -- the highest bidder (longest waiter) wins. LIFO service as proposed here is equivalent to the lowest bidder winning instead, meaning everyone will try to bid zero (or as low as they can). This changes if you have some uncertainty in the cutoff time -- in the flight example, attendants would close off the gate at some randomly determined time, and latecomers would be able to get great seats -- but they'd also have an excellent chance of missing the flight entirely! In this case, the thing you're bidding with is how much you're willing to risk missing the flight. If you know that the flight will close at a time uniformly distributed between 10:00 and 10:30 for example, those who arrive at 10:29 are willing to accept a 29/30 risk of missing the flight in exchange for being virtually guaranteed their choice of seats.
- bru_ 11y agoThis is really interesting
- dooptroop 11y agoThis seems to result in every plane leaving either empty or delayed. Realistically it would have to be done with an interval of boarding. Whether this interval is known to the passengers or not I don't think matter. So boarding is between 10:00 and 10:30. The first passenger to arrive after boarding starts will be the first to board, since they would be at the end of the line at that time. And so would the next one, and so on.
- omginternets 11y agoYeah, that'll go over well... More to the point, the people who come "too early" are usually trying to get their thing done before some impending deadline. Global optimizations sometimes don't go over well with individuals, i.e. it doesn't guarantee that a given individual will spend less time in a queue, and that's what ultimately matters to the individual. I could see this working in airports or other places with ushers, but not as a general principle.
- thanatosmin 11y agoThe research being discussed: http://static.sdu.dk/mediafiles/4/3/F/%7B43F80C9B-3533-4838-9E08-DE09931B9379%7Ddpbe12_2014.pdf http://static.sdu.dk/mediafiles/4/3/F/%7B43F80C9B-3533-4838-...
- JulianMorrison 11y agoWouldn't it be simpler just not to open the queue pool until immediately before the event? And shoo people off if they try to line up nearby. Then you get more or less exactly what this system would create, an unholy shoving scrum at t = 0, without the built in cruelty to safety conscious planners.
- slindz 11y agoHaving flown internationally in Europe recently, I can attest that prompting people back to the seated waiting area (over the intercom) ahead of boarding had zero impact on the forty-sixty people super keen to get on board. I suspect the airport would be interested in trying out the LIFO approach in this particular location.
- joosters 11y agoI don't understand some of the herd mentality at airports. For a long time, the budget airline Ryanair used to seat its planes first-come, first-served style. This meant everyone would stand and queue at the gate immediately, sometimes hours before the flight, just so they could get good seats. Fair enough, if that's what you want. But Ryanair switched to allocated seating over a year ago, and yet people still stand and queue long before the gate opens, even though there's little benefit. Can it be worth it just to get to your assigned seat slightly earlier?
- intelekshual 11y agoThe variable here is overhead bin space, not seats. People want to board first, regardless of their seating assignment, so that they're assured a space for their probably oversized carry-on luggage.
- joosters 11y agoAh yes, good point. Still seems excessive to me, in the past they have offered to check-in luggage at the gate (for free) if they are getting full.
- protomyth 11y agoPeople like low individual latency, they really don't care about the queue's throughput or the average latency. This also presupposes the venue doesn't want lines. That's a pretty bad assumption for a lot of service industries. Lines mean your venue is popular and serve as advertising.
- deleted 11y ago[deleted]
- sarciszewski 11y agoNo. If it was first in, last out it wouldn't be a queue, it would be a stack. Come on, author, this is literally computer science 101.
- swasheck 11y agounless they're using queue in a non-compsci parlance. i've never heard of being "last in the stack" while "stacking up" for my turn at the counter. this study seems aimed at addressing human systems, not with data structures.
- sarciszewski 11y agolooks at downvotes Wow, I didn't realize HN had such a massive stick up their ass with what was OBVIOUSLY A FUCKING JOKE.
- deleted 11y ago[deleted]
- Negative1 11y agoKeep in mind this article is from a British source and they tend to associate the word Queue to mean what Americans call a Line. So when he is saying a 'LIFO Queue' he means a 'LIFO Line'. And you're right, a Stack is a Comp Sci term. You're assuming this guy is Computer Scientist, which may not be true (most people are not).
- bru_ 11y ago"But the researchers experimented with different queuing systems, and when they told volunteer queuers that people would be selected from the queue and served at random, the average wait was reduced." This is all around a much better system than FIFO. Of course LIFO is the fastest on average, but you want there to be a reasonable, predictable bound on how much time an individual can expect to wait. An extension of this policy could be "partially random first come first served", where you just start at the first person in line and flip a coin with probability 0 <= p <= 1 of getting heads, and if you get heads they get served. If you get tails you move to the next person, with the only exception being the last person in line. In practice, for airports I would prefer to have the people sitting in the back board first. Then you wouldn't have so much congestion from people blocking the aisle while they stuff their bag into the overhead compartment. Also you shouldn't have to sit in your seat longer for the same flight if you bought a first class ticket.
- SilasX 11y ago>This is all around a much better system than FIFO. Of course LIFO is the fastest on average, but you want there to be a reasonable, predictable bound on how much time an individual can expect to wait. Right, this is generally handled by how we (implicitly) judge queues, not by the average wait, but by the average square of the wait, and penalize extreme wait times that are concentrated on one person. It's why it's better to have one line feed into multiple clerks rather than each clearly get their own line: because there's the risk of some transaction taking a long time and screwing everyone in that line. Single-queue avoids that by allowing people to be routed around that clerk. There's no change in the average, but you've avoided major quadratic penalties. It's also the problem with LIFO: even if you could somehow stop people from leaving their early-entrance spot (!!) to re-enter for a better one, you're still sticking a few people with horrible wait times, which good metrics penalize.
- zokier 11y agoIf the queuers have the opportunity to observe the queue before entering the queue then LIFO can't possibly work because why would anyone enter the queue voluntarely first knowing that you'd be served last? So people would end up hovering around the airport gate indefinitely because no one wants to go first.
- mschuster91 11y agoEasier solution: print out tickets with a vending machine (or link it with a smartphone web app to reduce paper waste) and allow people to SIT or MOVE AWAY without losing their place. Works wonders w/ children (who often enough get bored as fuck, and as result noisy or otherwise disruptive, when forced to wait for longer periods of time with no movement allowed) and old-ish or pregnant persons who simply are physically overwhelmed by having to stand still for longer times. Also works wonders against rich or pseudo-elite bastards thinking they're too important/rich to wait.
- moron4hire 11y agoWhen I can make more in 5 minutes than a teenager can make in an hour, then yes, I explicitly am too rich to wait.
- mschuster91 11y agoThe entire point of a waiting queue is to ensure equality. The plane is going to depart at the specified time and when you're early enough you can grab the best seat so where's the problem? Most airports and other venues with predictable queues offer free wifi and power outlets so where's the problem there?
- Dylan16807 11y ago>The entire point of a waiting queue is to ensure equality. Only in the absence of other methods of organization. If you pay for a better ticket you usually don't have to wait in the same line. And if you remove the social expectations of lines, there's no big deal about paying other people to do easy but boring tasks or whatnot. Sitting in line is still a waste of time.
- vegardx 11y agoAre you prepared to pay more because your time is supposedly worth more? If not, then no, you're not too rich to wait. How people spend their time and value it is subjective. Just because you can put a dollar tag to it, doesn't mean the rest of the world does.
- gpvos 11y ago> Abandoning the first-come-first-served principle would be easier in internet or phone queues though, Osterdal points out. Someone should implement this in TCP/IP routers and see what happens.
- EvilBanshee 11y agoAm I the only one who's noticed an uptick in the number of articles with clickbaity/contrarian/generalizing titles coming from the BBC lately? One look at the current BBC tech news feed[1] shows a few such disappointing titles. "VIDEO: Is this the end of ads on mobiles?" "Are we addicted to technology?" 1: http://feeds.bbci.co.uk/news/technology/rss.xml http://feeds.bbci.co.uk/news/technology/rss.xml
- jerf 11y agoI've been noticing a spate of NYT articles lately too that seem to be summed up by "Every Common Sense Thing You Know Is Wrong Because Some Academic Somewhere Ran A Study That Could Be Read That Way." Presumably to be followed up by "Now That Somebody Did Something Different We're Here To Tell You How That Went Wrong, Too". Maybe it's just that I'm 36 and old and crotchety but is anyone else getting tired of reading the "Every Last Thing Western Civilization Thinks Or Does Is Completely Wrong" article? And I don't just mean the "big issues", but, stuff like this article, too. How you queue up... WRONG. How you drink water... WRONG. How you play on the playground... WRONG. How speed limits work... WRONG.
- princeb 11y agothis particular headline seems fine though - there is a question for which most people have existing opinions about and some rationale for believing so. and then the article engages some of these notions. conversely if this article were to give the answer in the headline right away 'LIFO queues may be more optimal' one could possibly take the reasons presented at face value without understanding (or even seeing) why it is counter intuitive.
- SilasX 11y agoI just remembered that Steve Landsburg wrote about this a while ago for Slate, in the context of joggers waiting for water fountains. [1] It always Steck me as one of those "mathematically true but unphysical" results. Yes, if you could jog indefinitely, and if you could prevent "meta queueing", then you could make it so that there would never be a line at the fountain, but that's not a good model of joggers' needs. [1] http://www.slate.com/articles/arts/everyday_economics/2001/02/the_first_one_now_will_later_be_last.html http://www.slate.com/articles/arts/everyday_economics/2001/0...
- peteratt 11y agoThis one got me thinking — what would be the optimal way to face a flight boarding line? If there are no incentives (i.e. seats are already assigned), then you're paying with time for no reward. Many people are using a highly suboptimal approach by waiting in line even before the boarding has been announced. I'm glad I just sit with my computer until there is no one in line :)
- Joky 11y agoI do the same, but I believe many people want to be inside ASAP to get their "hand luggage" close. It happened to me once that there were no space anymore and my bag was quite far away with the crew luggages.
- Retra 11y agoThis reminds me of people driving all over the parking lot looking for a close spot, when it would have been quicker to park in the back and walk an extra 15 seconds...
- jackmaney 11y ago"Should the first in a queue be served last?" No. Queues are, by definition, FIFO. This article is one of the most idiotic pieces of drivel that I've read in a long time. I want my two minutes back.
- dantillberg 11y agoI assume this is intended to be sarcasm? I thought that the article was very interesting, especially in the context of software engineering, even if the word "queue" was used in the colloquial sense (and not the stricter technical meaning used in computing).
- jackmaney 11y ago> I assume this is intended to be sarcasm? Your assumption is incorrect.
- vacri 11y agoBy convention, not by definition.
- jackmaney 11y agoNo, by definition: https://en.wikipedia.org/wiki/Queue_(abstract_data_type) https://en.wikipedia.org/wiki/Queue_(abstract_data_type)
- vacri 11y agoHave you never queued up for something, only to have someone in the queue served out of order? A new cashier's register opens up? Or a special consideration for a member of the queue? I remember being served out of order in a queue for an airline ticket (due to my height). Do you have an alternate name for these structures of humans? Are you one of those people that considers technical jargon in a narrow field to supersede all broader meaning of a term? I mean, nothing in the article even suggests CS queues...
- 11y ago
- frobozz 11y ago> It could be open to manipulation, with people leaving the queue and rejoining from the back in order to get served more quickly. This isn't manipulation, this is pretty much the defined behaviour. In a queue that doesn't close, this is one of only two ways for the person at the front to ever get served. The other way being for that person to be the only person left in the vicinity who wants the thing being queued for.
- iofj 11y agoWhen working at a helpdesk company managing IVR services, one quicly learns : LIFO minimizes latency and resource usage FIFO maximizes latency and resource usage What you want to serve, as a queue manager, is the largest amount of requests in the shortest amount of time. Counterintuitively, this means that you absolutely don't want people who wait a long time in line to get served, because if they're willing to wait on hold for 30+ minutes they're willing to badger your agent (the guy answering the phone) for a long time into doing what they want. The result of this is that the queue quickly gets taken over by these long-waiters and everyone else gets delayed massively. What you want to maximize is requests served/agent time. Requests served is what brings in the money, agent time is money leaving. LIFO, combined with seriously incentivizing agents to make sure calls get resolved faster than $avg - 10% or so, ideally with a pay bonus (people, especially people in low-end jobs, respond very strongly to pay bonuses). The net result is that complex requests will result in waiting very long in the queue (because agents will throw you back to the queue as soon as they realize what you want is complex or impossible (people wanting things you can't provide are very bad in all respects, very common, and the people requesting them usually have way too much time). "I want to talk to manager" -> just throw him back in the queue). This means complex and impossible queries really, really start taxing the customer's willingness to sacrifice their time. Ideally this would result in the 2-hour-long "pay for me sending a slightly scratched product I bought last week in the US for 5$ less than I could have it in Antarctica, and let me ship it for replacement in < 1week, or I will #$)(!@#%)! 1@#)$&!@)#$ @$#)@& @)$&)#@& you and your entire family you !#@$ (@&@)(#& #)(&@)&@! #)(@#)(@" conversations to just not happen. Normally there's a lot of these, they wear out agents (people being treated badly by customers to the point of crying happened almost daily) Now you don't quite go for straight LIFO. Firstly a lot of people are offended by it, think it unfair, that sort of thing (and then the costs start mounting). You also don't want pure LIFO because there are customers that you actually want to serve with complex queries, so you start building a complex multi-queue system, but the entrypoint is usually a LIFO queue.
- zero_intp 11y agoI came to share a similar experience running the numbers for a tier 1 IP carrier customer service desk. Per call mixed FIFO/LIFO also gives you a good feel for how technical situations are progressing, and still depletes the older queue entries. Any given center can usually be dialed in, by changing the ratio off the top or the bottom of the stack for the next served. I would imagine dynamic heuristics based on volume and delta volume/period would greatly assist keeping the queues clean.