If you do not see this message displayed properly, please click here


The Faculty of Informatics is pleased to announce a seminar given by Pamela Delgado



Kairos: Preemptive Data Center Scheduling Without Runtime Estimates
Speaker: Pamela Delgado
Swiss Data Science Center (SDSC), Switzerland
Date: Friday, November 30, 2018
Place: USI Lugano Campus, room A13, Red building (Via G. Buffi 13)
Time: 13:30-14:30



The vast majority of data center schedulers use task runtime estimates to improve the quality of their scheduling decisions. Knowledge about runtimes allows the schedulers, among other things, to achieve better load balance and to avoid head-of-line blocking. Obtaining accurate runtime estimates is, however, far from trivial, and erroneous estimates lead to sub-optimal scheduling decisions. Techniques to mitigate the effect of inaccurate estimates have shown some success, but the fundamental problem remains.


This paper presents Kairos, a novel data center scheduler that assumes no prior information on task runtimes. Kairos introduces a distributed approximation of the Least Attained Service (LAS) scheduling policy. Kairos consists of a centralized scheduler and per-node schedulers. The per-node schedulers implement LAS for tasks on their node, using preemption as necessary to avoid head-of-line blocking. The centralized scheduler distributes tasks among nodes in a manner that balances the load and imposes on each node a workload in which LAS provides favorable performance.


We have implemented Kairos in YARN. We compare its performance against the YARN FIFO scheduler and Big-C, an open-source state-of-the-art YARN-based scheduler that also uses preemption. Compared to YARN FIFO, Kairos reduces the median job completion time by 73% and the 99th percentile by 30%. Compared to Big-C, the improvements are 37% for the median and 57% for the 99th percentile. We evaluate Kairos at scale by implementing it in the Eagle simulator and comparing its performance against Eagle. Kairos improves the 99th percentile of short job completion times by up to 55% for the Google trace and 85% for the Yahoo trace.




Dr. Delgado is a Computer Scientist at the Swiss Data Science Center (SDSC). She got her PhD from EPFL Switzerland in November 2018. Her thesis, entitled "Hybrid, Job-Aware, and Preemptive Datacenter Scheduling", focused on providing better scheduling and resource management solutions for data centers. Her research interests include data center scheduling, cloud computing, distributed systems and systems support for data science.

Dr. Delgado's research was supported by Microsoft Research and made part of a project of the Swiss Joint Research Center at Microsoft. She was also recepient of the Google Anita Borg Memorial Scholarship on 2013 and the Swiss Government Excellence Scholarship for Foreign Students for her masters at EPFL. 


Host: Prof. Fernando Pedone


Faculty of Informatics

Faculty of Informatics
Università della Svizzera italiana
Via Giuseppe Buffi 13
CH-6904 Lugano
Tel.: +41 (0)58 666 46 90
Fax: +41 (0)58 666 45 36
Email: decanato.inf@usi.ch
Web: www.inf.usi.ch
Twitter: @USI_INF


Segui USI@EXPO2015 su Twitter Segui USI@EXPO2015 su Facebook Segui USI@EXPO2015 su Linkedin Segui USI@EXPO2015 su YouTube