When is a fair queue the wrong queue?

First-in-first-out feels like the only decent way to run a queue β€” nobody jumps the line. Under light load that fairness is free. But give every job a deadline and push past capacity, and FIFO dutifully serves the oldest work first β€” work that's already too late β€” until almost nothing finishes on time. "Unfair" LIFO keeps shipping fresh work through the same overload, and a short queue that turns the excess away at the door does better still. Both race here on the exact same simulated arrivals.

Load
Work arrives atperand takesto serve.
It'sworthlessA deadline: a job that finishes later than this counts as late β€” a timed-out request, a stale price, an answer after the meeting ended. Serving it anyway still costs full service time.if not done withinof arriving.
100% on time1Γ— capacity25%50%75%
0.25Γ—0.5Γ—1Γ—2Γ—1.5Γ— you4Γ—
FIFO β€” oldest firstLIFO β€” newest first
Demand is 1.5Γ— capacityρ, arrivals Γ· what the server can do. Past 1Γ— the backlog grows without bound and no discipline can serve more than 1/ρ of what arrives β€” the race is over who gets that share, fresh work or stale.: FIFO delivers 3% of the work on time, LIFO 68%.
The collapse
DemandFIFOLIFO
0.5Γ—
100%
100%
0.75Γ—
100%
98%
0.9Γ—
100%
95%
1Γ—
23%
90%
1.5Γ—you
3%
68%
2Γ—
3%
52%
4Γ—
2%
26%

Below capacity FIFO holds its own β€” when everything can be served in time, fairness is free and serving the oldest first is exactly right. Past 1Γ— the disciplines split: FIFO shares the growing wait evenly, so soon everyone is late and the server burns all its capacity on work that's already worthless. LIFO concentrates the pain instead β€” a few jobs wait forever so that most are served fresh. The short queue is the honest version of the same idea: admit only what can still finish on time and turn the rest away at the door. That's why CoDel keeps router queues short, and why Facebook's servers switch to adaptive LIFO under load.

an M/M/1 simulation, inspired by β€œFIFO considered harmful”