# Queuing theory
**Queuing theory** is the mathematical study of waiting lines: given how fast work arrives and how fast a server processes it, queuing theory predicts things like average wait time, queue length, and how those quantities blow up as a system approaches its capacity limit. It applies directly to parallel and distributed systems, where a queue shows up constantly, whether it's requests waiting for a thread pool, packets waiting on an [[interconnect]], or threads waiting on a [[lock]].

## The core quantities

A queue is described by an arrival rate $\lambda$ (work items arriving per unit time), a service rate $\mu$ (work items a single server can finish per unit time), and their ratio, the **utilization** $\rho = \lambda/\mu$. For a stable queue, $\rho$ must stay below 1: a server slower than the rate work arrives means the queue grows without bound.

For the simplest case (Poisson arrivals, exponential service time, one server, known as M/M/1), the expected number of items waiting in the system is:

$$L = \frac{\rho}{1 - \rho}$$

## Why this matters more than it looks

$L$ doesn't grow linearly with $\rho$. it diverges as $\rho \to 1$. A server running at 50% utilization has a small, well-behaved queue; the same server pushed to 90% utilization has a queue nearly ten times longer, and pushed to 99% it's roughly a hundred times longer, for the same shape of arrival pattern. This is the mathematical reason a system that looks fine under moderate load can suddenly develop enormous latency under a load increase that seems modest on paper, why "average utilization" alone is a misleading capacity metric, and why systems are typically provisioned with real headroom rather than sized to just barely keep up with expected average load.

```
utilization (rho):   0.5    0.7    0.9    0.95   0.99
avg queue length L:   1.0    2.3    9.0    19.0   99.0
```

## Where this shows up in parallel systems

A thread pool sized too small for its incoming task rate behaves exactly like an M/M/1 queue nearing $\rho = 1$: latency for an individual task climbs sharply well before the pool is fully "busy" by any naive measure. The same math explains why [[lock-contention]] gets disproportionately worse as more threads compete for one lock, and why network switches and [[interconnect]] links show latency cliffs as traffic approaches link capacity rather than degrading gracefully and proportionally.