{"id":"arxiv/2601.14612","url":"https://arxiv.org/abs/2601.14612","tags":["cs.DC","cs.NI","cs.PF","math.OC"],"score":0,"title":"Exploiting Spot Instances for Time-Critical Cloud Workloads Using Optimal Randomized Strategies","domain":"cs.DC","source":"arxiv","authors":["Neelkamal Bhuyan","Randeep Bhatia","Murali Kodialam","TV Lakshman"],"reviews":0,"subject":"cs.DC","summary":"This paper addresses the challenge of deadline-aware online scheduling for jobs in hybrid cloud environments, where jobs may run on either cost-effective but unreliable spot instances or more expensive on-demand instances, under hard deadlines. We first establish a fundamental limit for existing (predominantly-) deterministic policies, proving a worst-case competitive ratio of $Ω(K)$, where $K$ is the cost ratio between on-demand and spot instances. We then present a novel randomized scheduling algorithm, ROSS, that achieves a provably optimal competitive ratio of $\\sqrt{K}$ under reasonable…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-01-21","reactions":{}}