Exploiting Spot Instances for Time-Critical Cloud Workloads Using Optimal Randomized Strategies
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918298603487232 |
|---|---|
| author | Bhuyan, Neelkamal Bhatia, Randeep Kodialam, Murali Lakshman, TV |
| author_facet | Bhuyan, Neelkamal Bhatia, Randeep Kodialam, Murali Lakshman, TV |
| contents | 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 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_14612 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Exploiting Spot Instances for Time-Critical Cloud Workloads Using Optimal Randomized Strategies Bhuyan, Neelkamal Bhatia, Randeep Kodialam, Murali Lakshman, TV Distributed, Parallel, and Cluster Computing Networking and Internet Architecture Performance Optimization and Control C.4; C.2.4 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 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. |
| title | Exploiting Spot Instances for Time-Critical Cloud Workloads Using Optimal Randomized Strategies |
| topic | Distributed, Parallel, and Cluster Computing Networking and Internet Architecture Performance Optimization and Control C.4; C.2.4 |
| url | https://arxiv.org/abs/2601.14612 |