Heavy-tailed workload distributions concentrate most work in a small fraction of jobs or tasks, producing many short tasks and a few extremely long ones. This shape profoundly changes what a scheduler must optimize. Heavy-tailed behavior raises the importance of tail outcomes rather than averages, because a small number of long tasks, often called stragglers, determine user-perceived performance and system efficiency. Jeffrey Dean at Google and Luiz André Barroso at Google describe how tail latency dominates service performance and recommend design patterns to mitigate it. Michael Mitzenmacher at Harvard has analyzed how heavy tails alter queueing behavior and resource contention in distributed systems.
Tail properties and root causes
Heavy tails arise from heterogeneous data sizes, opportunistic user behavior, iterative algorithms that sometimes explore expensive paths, and batch jobs whose runtimes vary with input characteristics. Workload mix and user culture matter: interactive web services in one territory can produce many small requests, while research clusters in another run few but very large analytic jobs. These socio-technical patterns change arrival processes and make conventional assumptions of light-tailed, exponential job sizes invalid.
Consequences for scheduler policies
Designers must prioritize tail latency, not just throughput. Schedulers that use average-based fairness or simple round-robin allocation frequently suffer resource fragmentation and long-running tails. Practical responses include speculative execution and redundancy to hedge against stragglers, size-aware admission control and preemption to protect short interactive tasks, and smart placement to avoid correlated failures. Dean and Barroso document redundancy and hedged retries as effective at reducing the tail in large production services. Mitzenmacher’s theoretical work explains why naive load balancing fails under heavy tails and why size-based and two-choice policies improve outcomes.
Schedulers also face trade-offs with cost and energy: redundancy reduces tail latency but increases CPU and energy use, which has environmental and budgetary consequences that vary by datacenter location and local energy prices. Human-operational complexity grows as operators must tune thresholds and policies for regional workload patterns and organizational priorities. No single policy fits all clusters; hybrid approaches that combine size-awareness, quick preemption for latency-sensitive tasks, and controlled redundancy produce practical gains.