Dispatching to Minimize Asymptotic Tail Latency

Maintaining low delay is an aim of virtually every computer system, but any system with limited resources inevitably runs into queueing delays when load is high. Queueing delays occur at every level of abstraction, e.g. packet flows wait at network switches, queries wait in databases, and large-scale simulations wait for supercomputer time. One of the main tools we have to combat delay is load balancing, i.e. dispatching jobs (e.g. packet flows, queries, simulations) across servers (e.g. network switches, databases, supercomputers) to reduce queueing. The main metrics one evaluates load balances with are tail delays, or P[T > x] for large x, where T is the response time. This formalizes the goal of having few jobs experience large delays, which is a realistic goal for many computer systems practitioners.