Transition Waste Optimization for Coded Elastic Computing

Son Hoang Dau, Ryan Gabrys, Yu Chih Huang, Chen Feng, Quang Hung Luu, Eidah Alzahrani, Zahir Tari

Research output: Contribution to journalArticlepeer-review

Abstract

Distributed computing, in which a resource-intensive task is divided into subtasks and distributed among different machines, plays a key role in solving large-scale problems. <italic>Coded computing</italic> is a recently emerging paradigm where redundancy for distributed computing is introduced to alleviate the impact of slow machines (stragglers) on the completion time. We investigate coded computing solutions over elastic resources, where the set of available machines may change in the middle of the computation. This is motivated by recently available services in the cloud computing industry (e.g., EC2 Spot, Azure Batch) where low-priority virtual machines are offered at a fraction of the price of the on-demand instances but can be preempted on short notice. Our contributions are three-fold. We first introduce a new concept called <italic>transition waste</italic> that quantifies the number of tasks existing machines must abandon or take over when a machine joins/leaves. We then develop an efficient method to minimize the transition waste for the cyclic task allocation scheme recently proposed in the literature (Yang <italic>et al</italic>. ISIT&#x2019;19). Finally, we establish a novel solution based on finite geometry achieving <italic>zero</italic> transition wastes given that the number of active machines varies within a fixed range.

Original languageEnglish
Pages (from-to)1
Number of pages1
JournalIEEE Transactions on Information Theory
DOIs
StateAccepted/In press - 2023

Keywords

  • Costs
  • Industries
  • Optimization
  • Resource management
  • Task analysis
  • Toy manufacturing industry
  • Virtual machining

Fingerprint

Dive into the research topics of 'Transition Waste Optimization for Coded Elastic Computing'. Together they form a unique fingerprint.

Cite this