Technical Program

Paper Detail

Paper IDD.1.4
Paper Title Optimizing the Transition Waste in Coded Elastic Computing
Authors Son Hoang Dau, RMIT University, Australia; Ryan Gabrys, University of California, San Diego, United States; Yu-Chih Huang, National Chiao Tung University, Taiwan; Chen Feng, British Columbia University (Okanagan Campus), Canada; Quang-Hung Luu, Swinburne University of Technology, Australia; Eidah Alzahrani, Zahir Tari, RMIT University, Australia
Session D.1: Coded Computation
Presentation Lecture
Track Coded and Distributed Computation
Manuscript  Click here to download the manuscript
Virtual Presentation  Click here to watch in the Virtual Symposium
Abstract Motivated by recently available services in the cloud computing industry, e.g., EC2 Spot or Azure Batch, where spare/low-priority virtual machines are offered at a fraction of the price of the on-demand instances but can be preempted on short notice, we investigate coded computing solutions over elastic resources, where the set of available machines may change in the middle of the computation. Our contributions are two-fold: We first propose an efficient method to minimize the transition waste, a newly introduced concept quantifying the total number of tasks that existing machines have to abandon or take on anew when a machine joins or leaves, for the cyclic elastic task allocation scheme recently proposed in the literature (Yang et al. ISIT'19). We then proceed to generalize such a scheme and introduce new task allocation schemes based on finite geometry that achieve zero transition wastes as long as the number of active machines varies within a fixed range. The proposed solutions can be applied on top of existing coded computing schemes tolerating stragglers.

Plan Ahead


2021 IEEE International Symposium on Information Theory

11-16 July 2021 | Melbourne, Victoria, Australia

Visit Website!