counter stats

The Fundamentals of Heavy-Tails:
Properties, Emergence, and Identification

Heavy-tails are a continual source of excitement and confusion across disciplines as they are repeatedly "discovered" in new contexts. This is especially true within computer systems, where heavy-tails seemingly pop up everywhere -- from degree distributions in the internet and social networks to file sizes and interarrival times of workloads. However, despite nearly a decade of work on heavy-tails they are still treated as mysterious, surprising, and even controversial.

The goal of our forthcoming book is to show that heavy-tailed distributions need not be mysterious and should not be surprising or controversial. In particular, we demystify heavy-tailed distributions by showing how to reason formally about their counter-intuitive properties; we highlight that their emergence should be expected (not surprising) by showing that a wide variety of general processes lead to heavy-tailed distributions; and we illustrate that most of the controversy surrounding heavy-tails is the result of bad statistics, and can be avoided by using the proper tools.

The book covers mathematically deep concepts such as the generalized central limit theorem, extreme value theory, and regular variation; but does so using only elementary mathematical tools in order to make these topics accessible to anyone who has had an introductory probability course.

A more detailed overview of the topics to be included in the book is below. Additionally, the slides from recent tutorials we have given on heavy-tails provide a high-level glimpse into the topics and perspective of the book.

You can download pre-publication versions of completed chapters here.

Table of contents

  1. Introduction
    • Defining heavy-tailed distributions
    • Examples of heavy-tailed distributions
    • How to use this book

Part I: Properties

  1. Scale invariance, power laws, and regular variation

  2. Catastrophes, conspiracies, and subexponential distributions

  3. Residual lives, hazard rates, and long tails

Part II: Emergence

  1. Additive processes

  2. Multiplicative processes

  3. Extremal processes

Part III: Estimation

  1. Estimating power-law distributions: Listen to the body

  2. Estimating power-law tails: Let the tail do the talking

  3. Estimating multivariate power-law tails: Cautionary tales of tails


Jayakrishnan Nair received his PhD from California Institute of Technology (Caltech) in 2012. His PhD thesis focused on scheduling for heavy-tailed and light-tailed workloads in queueing systems. He is currently a post-doctoral scholar at CWI in the Netherlands. His research interests include modeling, performance evaluation, and design issues in queueing systems and communication networks. Jayakrishnan was a recipient of the best paper award at IFIP Performance, 2010.

Adam Wierman is a Professor in the Department of Computing and Mathematical Sciences at the California Institute of Technology. He received his Ph.D., M.Sc. and B.Sc. in Computer Science from Carnegie Mellon University in 2007, 2004, and 2001, respectively. His research interests center around resource allocation and scheduling decisions in computer systems and services. More specifically, his work focuses both on developing analytic techniques in stochastic modeling, queueing theory, scheduling theory, and game theory, and applying these techniques to application domains such as energy-efficient computing, data centers, social networks, and electricity markets.

He received the 2011 ACM SIGMETRICS Rising Star award, the 2014 IEEE Communications Society William R. Bennett Prize, and has been coauthor on papers that received of best paper awards at ACM SIGMETRICS, IEEE INFOCOM, IFIP Performance, IEEE Green Computing Conference, IEEE Power & Energy Society General Meeting, and ACM GREENMETRICS. He was named a Seibel Scholar, received an Okawa Foundation grant, and received an NSF CAREER grant. Additionally, his dissertation received the CMU School of Computer Science Distinguished Dissertation Award, his work with HP on designing net-zero data centers was named a Computerworld Honors Laureate, and he has received multiple teaching awards. He has served on the board of directors of ACM Sigmetrics and on the editorial boards of IEEE Transactions on Networking (ToN), Operations Research (OR), ACM Transactions on Modeling and Performance Evaluation of Computing Systems (TOMPECS), Performance Evaluation (PEVA), Queueing Systems (QUESTA), the IEEE Transactions on Cloud Computing (TCC), the IEEE Transactions on Network Science and Engineering (TNSE), and Sustainable Energy, Grids, and Networks (SEGAN).

Bert Zwart is currently a senior researcher at CWI, where he leads the Probability and Stochastic Networks group. He also holds a full professor position at VU University Amsterdam, is senior fellow at Eurandom, and holds an adjunct professor position at the H. Milton Stewart School of Industrial and Systems Engineering at Georgia Institute of Technology, where he was holding a Coca-Cola Chair until 2008. Bert Zwart is the 2008 recipient of the Erlang prize for outstanding contributions to applied probability by a researcher not older than 35 years old, and an IBM faculty award. His research is concerned with the application of analytic and probabilistic asymptotic methods to applied probability models in computer systems, communication networks, customer contact centers, and manufacturing systems. Dr. Zwart has published more than 70 refereed publications and is council member of the Applied Probability Society of INFORMS. Dr. Zwart has been area editor of Stochastic Models for Operations Research, the flagship journal of his profession, from 2009-2011. In addition, dr. Zwart is editor-in-chief (with J.K. Lenstra and M. Trick) of the journal Surveys in Operations Research and Management Science, and serves on the editorial board of Mathematics of Operations Research, Mathematical Methods of Operations Research, Operations Research, Queueing Systems and Stochastic Systems. He is a recipient of Veni and Vidi research grants from NWO.