Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

'First come, first served' is a very very common way of organizing access to a limited resource or service in the real world. It can be explained by saying that whenever the resource is available the person who has been waiting the longest is served, and visualized by thinking of people standing in a single-file line, where the person at the front is always served next and new arrivals join the back of the queue.

If you ask someone why this system is the best, they might instinctively say 'It is the most fair'. But can we express what this fairness means in terms of some property, which is maximized for this system and no other? It doesn't mean for instance that people all wait the same time, or even that people who arrive at nearly the same time don't get served a long time apart.

Or does it optimize some other property, such as the incentive to arrive as soon as possible or the incentive not to arrive at busy times?

Can we make formal why it should be preferred to other arrangements? Or is it just a human tendency to do something simple/something that most people feel is fair/something we all know?

share|improve this question
add comment

2 Answers 2

First-come-first-served ensures that provided that the time between served customers is bounded, any customer who enters the queue will within a worst-case wait time that can be determined based upon the number of preceding customers. Even if the time between customers is bounded only probabilistically, the wait time will still have a reasonable probabilistic bound. For example, if one flips a coin once per second, and each "heads" means someone enters the queue and each "tails" means someone is serviced (unless the queue is empty, in which case nothing happens), someone who enters when there are 39 people ahead of him will know that the time until he is serviced will be the amount of time required for a total of 40 tails to appear. That might or might not happen within 80 seconds, but will likely happen within 90. Although would be possible that the person might have to wait an hour or more, it would be exceptionally improbable. The probability of a person not having been served within a given length of time will rapidly approach zero as the time increases.

Suppose that the same parameters were applied with a LIFO stack. While someone who entered the stack would have a 50% of being served in one second, they'd have a 3/8 chance of not getting served within 3 seconds (as compared with a 1/8 chance if they'd been first in a queue), a 5/16 chance of not getting served in 5 (versus 1/32), and a 35/128 chance of not getting served in 7 (vs 1 in 128). The probability of not getting served within N seconds drops as N increases, but very slowly. One would have roughly a one in nine chance of having to wait a minute, a one in 75 chance of having to wait an hour, and a one in 251 chance of having to wait a week or more.

If one assigns priorities to different items, then other service orders become practical, but behavior modeling is much more apt to focus much more on heuristics than absolute probability calculations.

share|improve this answer
    
This makes sense is and pretty compelling (including from everyday experience of queues). –  jwg Dec 22 '13 at 20:19
    
@jwg: As I was writing the answer, I found myself trying to remember of the probability of taking longer than N seconds would in fact approach zero as N approaches infinity. I ran out of time to research that, but the probability of having to wait a week is so close to the probability of having to wait a day that I wonder if the probability of ever being served from the stack would approach something like 255/256, and how one would prove that? Of course, with a queue the probability of being served would approach unity. –  supercat Dec 23 '13 at 17:04
    
providing the rate of joining the queue is no greater than the rate of service, the probability of ever being served should tend to 1 as time goes to infinity. This can be worked out with an argument about random walks, and is the same as saying that with an unbiased gambling game (or one which is biased in the casino's favor), you will eventually go bankrupt, no matter how much money you start with. –  jwg Dec 26 '13 at 21:26
    
@jwg: The Wikipedia article on random walks makes clear that a player who has $1, going against a house which has $N, will have a N/(N+1) probability of going broke before breaking the house, but I didn't see any formulation of the probability of the player going broke within a specified number of rounds. If the player starts with $1, is there any closed-form calculation for the probability that the player will survive at least N coin flips? If the house has $3 or more, there will be an uncountable number of infinite coin-flip sequences will will never break the player nor the house... –  supercat Dec 26 '13 at 21:42
    
...and while it may be that the ratio of such coin flips sequences to total coin flip sequences is zero, I don't see any obvious reason that must be so. –  supercat Dec 26 '13 at 21:45
show 2 more comments

Queuing theory is primarily concerned with processes that have variability in arrival of jobs into the system. For example, jobs can be people needing service. The time taken to service these jobs is also generally variable. The result is congestion or waiting line. This can be measured by the average number of jobs in the queue and by the average waiting time of arrivals. There are costs associated with having jobs wait. There are also costs associated with adding more service capacity. Thus, challenge is to balance these costs. Queuing theory may be used to determine the optimum number of, say, serivce windows for a post office, Doctors available for clinic calls, number of clerks for a spare parts counter and so on. It may also be used to aid in decisions about the order in which customers should be processed to aid questions like "should there be an express lane". First in First Out, FIFO is a queuing discipline that is used in Queuing theory because of its modeling convenience. But there may be express or priority service for some jobs; an example is the express lane at many supermarkets for customers with 10 items or less in which case the service may be in random order. FIFO is a modeling convenience.

1) FIFO (First In First Out) also called FCFS (First Come First Serve) - orderly queue.

2) LIFO (Last In First Out) also called LCFS (Last Come First Serve) - stack.

3) SIRO (Serve In Random Order).

4) Priority Queue, that may be viewed as a number of queues for various priorities.

5) Many other more complex queuing methods that typically change the customer’s position in the queue according to the time spent already in the queue, expected service duration, and/or priority. These methods are typical for computer multi-access systems.

Most quantitative parameters (like average queue length, average time spent in the system) do not depend on the queuing discipline. That’s why most models either do not take the queuing discipline into account at all or assume the normal FIFO queue. In fact the only parameter that depends on the queuing discipline is the variance (or standard deviation) of the waiting time. There is this important rule (that may be used for example to verify results of a simulation experiment):

The two extreme values of the waiting time variance are for the FIFO queue (minimum) and the LIFO queue (maximum)

share|improve this answer
    
I appreciate that queueing theory is usually concerned with something other than the order in which waiting jobs get serviced. However it still seems like the closest reasonable tag and those knowledgeable in queuing theory might have thought about it. Notice that two of the metrics you quote, average number of jobs in the queue and average waiting time both don't depend on order of service. I agree with what you say about FIFO, however this only confirms the 'soft' advantages I have and doesn't suggest a 'hard' reason to favor it. –  jwg Dec 22 '13 at 19:50
    
Do you happen to know whether, in a scenario like I described, the stack approach would be guaranteed to serve everyone? It seemed like the probability of being served within a certain length of time was approaching something short of unity as the time increased, but I don't know if that was due to calculation error, a function whose approach to unity gets very slow, or what. Do you know how to figure the probability that a random walk will reach a certain distance to one side within a certain number of steps? –  supercat Dec 23 '13 at 17:14
    
Thanks for the augmented answer which I think I didn't see before. The last two pars seem to give a property like one I'm looking for - the minimized variance of waiting time variance. Do you have a reference for this result (or can you give an indication of the proof)? –  jwg Mar 21 at 16:07
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.