# Exploiting Spot Instances for Time-Critical Cloud Workloads Using Optimal Randomized Strategies

arXiv: https://arxiv.org/abs/2601.14612 · HTML: https://mlsanity.com/paper/2601.14612/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Jan 2026.

## Built on by (most cited first, 1 of 1)

- [Intelligent Cloud Orchestration: A Hybrid Predictive and Heuristic Framework for Cost Optimization](https://mlsanity.com/paper/2604.02131/) (2026)

## Abstract (arXiv)

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 Omega(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 √K under reasonable deadlines, significantly improving upon existing approaches. Extensive evaluations on real-world trace data from Azure and AWS demonstrate that ROSS effectively balances cost optimization and deadline guarantees, consistently outperforming the state-of-the-art by up to 30% in cost savings, across diverse spot market conditions.