A Caltech Library Service

Scheduling for the tail: Robustness versus optimality

Nair, Jayakrishnan and Wierman, Adam and Zwart, Bert (2010) Scheduling for the tail: Robustness versus optimality. In: 48th Annual Allerton Conference on Communication, Control, and Computing (Allerton). IEEE , Piscataway, NJ, pp. 969-976. ISBN 978-1-4244-8215-3.

[img] PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


When scheduling to minimize the sojourn time tail, the goals of optimality and robustness are seemingly at odds. Over the last decade, results have emerged which show that scheduling disciplines that are near-optimal under light (exponential) tailed workload distributions do not perform well under heavy (power) tailed workload distributions, and vice-versa. Very recently, it has been shown that this conflict between optimality and robustness is fundamental, i.e., no policy that does not learn information about the workload can be optimal across both light-tailed and heavy-tailed workloads. In this paper we show that one can exploit very limited workload information (the system load) in order to design a scheduler that provides robust performance across heavy-tailed and light-tailed workloads.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Additional Information:© 2010 IEEE.
Subject Keywords:Robustness, Indexes, Random variables, Queueing analysis, Size measurement, Servers, Scheduling
Record Number:CaltechAUTHORS:20170810-133904497
Persistent URL:
Official Citation:J. Nair, A. Wierman and B. Zwart, "Scheduling for the tail: Robustness versus optimality," 2010 48th Annual Allerton Conference on Communication, Control, and Computing (Allerton), Allerton, IL, 2010, pp. 969-976. doi: 10.1109/ALLERTON.2010.5707014 URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:80209
Deposited By: Linqi Guo
Deposited On:11 Aug 2017 19:12
Last Modified:03 Oct 2019 18:28

Repository Staff Only: item control page