Yi Lu

Associate Professor, Electrical and Computer Engineering, UIUC

Ph.D. Electrical Engineering, Stanford University, 2009photo_yilu
M. S. Electrical Engineering, Stanford University 2005
B.S. Electrical Engineering, Stanford University 2005


259 Coordinated Science Lab
Email: yilu4@illinois.edu



Aug       Our work received a new NSF grant!
May      Du’s GreenMap: MapReduce with Ultra High Efficiency Power Delivery                                            accepted to HotCloud 2015
Apr       Qiaomin presented Priority Algorithm for Near-data Scheduling: Throughput and                      Heavy-Traffic Optimality at Infocom 2015
Mar       Qiaomin won the Yi-Min Wang and Pi-Yu Chung Endowed Research Award for 2015!
Feb       Qiaomin’s Power of d Choices for Large-Scale Bin Packing: A Loss Model                                        accepted to Sigmetrics 2015
Feb       Qiaomin presented Near-data Scheduling at CSL student conference 2015


Our current focus is on performance, scalability and energy efficiency of data-intensive clouds. Other themes include compressed measurement, network algorithms and imaging.

You can check out our complete list of publications. Below is an overview of our projects.


Power-of-d choices, asymptotic independence and distributed scheduling

Stateless randomized load balancing is a natural fit for distributed schedulers and scalable high-performance. Power-of-two choices is a well-known randomized routing algorithm. However, we found that two choices are not enough for general service time distributions:

and we need power-of-d choices where d depends on the service time distribution. For a heavy-tailed distribution with parameter ß,  only d > ß / (ß-1) brings a qualitative change in performance.

To remove the dependence  on service time distribution, we proposed the Join-Idle-Queue (JIQ) algorithm, which uses reverse information balancing and outperforms power-of-d:

We proved the asymptotic independence property in order to study power-of-d choices with general service time distributions:

which we also used to study the problem of virtual machine assignment:


Data, Data, and Data

Data placement and data popularity induce a random load distribution on a system, which makes scheduling in data-intensive clouds a fundamentally different problem from other large-scale clusters: A scheduler needs to be robust with respect to load distributions.

We first studied the data placement problem with a given scheduler,

and then the scheduling problem with a given data placement. Our priority algorithm is the only known algorithm that is heavy-traffic optimal for all load distributions.


Workload and Meta-data

In order to understand the characteristics of data-processing applications, we analyzed workloads from production clusters:

We also studied efficient trace generation to enable fast and reliable evaluation of a large system in a small test bed:


Compressed Measurement (or Counter Braids)
Water-fat separation, MRI and a Jigsaw Puzzle


Our complete list of publications


Current: Qiaomin Xie, Ali Yekkehkhany, Du Su

Past (An Unofficial List):
David Stein (M.S.), LinkedIn
Mindi Yuan (M.S.)
Cristina Abad (Ph.D.) (Advisor: Roy Campbell), Escuela Superior Polit´ecnica del Litoral
Mayank Pundir (M.S.) (Advisor: Roy Campbell), Facebook
Victor Brakauskas (B.S.)
Caleb Qian (B.S.)

  • ECE598YL / CS598 — Cloud Computing: Systems and Algorithms
  • ECE 313 — Probability with Engineering Applications

 Honors and Awards
  • ACM SIGMETRICS Rising star award (2016)
  • Center of Advanced Study Fellow (2014)
  • NSF Career Award (2012)
  • Best Paper Award at IFIP Performance conference (2011)
  • Best Paper Award at ACM SIGMETRICS (2008)
  • Stanford Graduate Fellowship Award (2005)
  • Frederick Emmons Terman Engineering Scholastic Award, School of Engineering, Stanford University (2004)
  • Gold medal, Individual 4th, Singapore Mathematical Olympiad (1999)