Competitive Analysis of Task Scheduling Algorithms on a Fault-Prone Server and the Impact of Resource Augmentation
Antonio Fernández Anta, Research Professor at IMDEA Networks
Abstract: Reliable task execution in servers that are prone to unpredictable crashes and restarts is challenging and of high importance. However, not much work exists on the worst-case analysis of such systems. In this paper, we analyze the fault-tolerant properties of four popular task scheduling algorithms: Longest In System (LIS), Shortest In System (SIS), Largest Processing Time (LPT) and Shortest Processing Time (SPT), under worst-case scenarios on a fault-prone server. We use three metrics for the evaluation and comparison of their competitive performance, namely, completed load, pending load, and latency. We also investigate the effect of resource augmentation in their performance, by increasing the speed of the server. To do so, we compare the behavior of the algorithms for different speed intervals and show that between LIS, SIS and SPT there is no clear winner with respect to all the three considered metrics, while LPT is not better than SPT.
Biography: Dr. Antonio Fernández Anta is a Research Professor at IMDEA Networks. Previously he was a Full Professor at the Universidad Rey Juan Carlos (URJC) and was on the Faculty of the Universidad Politécnica de Madrid (UPM), where he received an award for his research productivity. He was a postdoc at MIT from 1995 to 1997. He has more than 20 years of research experience, with a productivity of more than 5 papers per year on average. He is Chair of the Steering Committee of DISC and has served in the TPC of numerous conferences and workshops. He received his M.Sc. and Ph.D. from the University of Louisiana in 1992 and 1994, respectively. He completed his undergraduate studies at the UPM, having received awards at the university and national level for his academic performance. He is Senior Member of ACM and IEEE.