📘

Spot vs On-Demand Expected-Cost Decision

MediumSystems & Infrastructure 📚 ML Systems & Infrastructure 1

Problem Statement

Decide whether to run a batch job on cheaper but interruptible spot instances or reliable on-demand, based on expected cost including restart overhead from interruptions.

Background

On-demand cost is on_demand_rate * hours. Spot is cheaper per hour (spot_rate) but with interruption probability p per hour, each interruption wastes restart_hours of recompute. Expected spot cost is spot_rate * (hours + expected_interruptions * restart_hours), where expected_interruptions = p * hours. Recommend "spot" if its expected cost is strictly less than on-demand, else "on_demand".

Your Task

def choose_instance(hours, on_demand_rate, spot_rate, p, restart_hours):

Return "spot" or "on_demand".

Input Format

hours (float), on_demand_rate, spot_rate (float), p (float in [0,1]), restart_hours (float).

Output Format

A string.

Sample

print(choose_instance(10, 1.0, 0.3, 0.1, 2.0))

Output:

spot

Example:

Input:

print(choose_instance(10, 1.0, 0.3, 0.1, 2.0))

Output:

spot

Reasoning:

Calculate the expected wasted time due to interruptions by multiplying the interruption probability, total hours, and restart duration: $0.1 \times 10 \times 2.0 = 2.0$ hours.
Determine the total effective time for the spot instance by adding the wasted time to the original job duration: $10 + 2.0 = 12.0$ hours.
Compute the total expected cost for the spot instance by multiplying the effective time by the spot rate: $0.3 \times 12.0 = 3.6$ .
Compute the total cost for the on-demand instance by multiplying the original job duration by the on-demand rate: $1.0 \times 10 = 10.0$ .
Compare the two costs to make the decision; since the spot cost ( $3.6$ ) is strictly less than the on-demand cost ( $10.0$ ), the spot instance is recommended.
The final output is spot

Constraints:

expected_interruptions = p * hours; wasted = expected_interruptions * restart_hours.
spot_cost = spot_rate * (hours + wasted); on_demand_cost = on_demand_rate * hours.
Choose spot iff spot_cost < on_demand_cost.

More from ML Systems & Infrastructure 1

Minimum-Cost Job Scheduling Across Priced WindowsHard Deduplicate Retried Pipeline Runs by Idempotency KeyMedium Retry with Capped Exponential Backoff and Jitter CapMedium Critical Path Length of a Pipeline DAGMedium Pipeline Stages Ready to RunEasy

1. Background Knowledge

This problem models a classic cloud cost-optimization trade-off: spot instances offer significant discounts (often 60–90% off on-demand) but can be reclaimed by the provider with little notice. In ML pipelines, an interruption means losing in-flight work and paying for restart overhead (reloading data, re-initializing models, re-running partial steps). The decision hinges on expected value under uncertainty.

The core probabilistic model treats interruptions as a Poisson-like process with a constant per-hour rate $p$ . Over a job of duration $T$ hours, the expected number of interruptions is simply $p \cdot T$ . Each interruption incurs a fixed penalty of restart_hours of wasted compute. This linear expectation holds because the expected value of a sum equals the sum of expected values, regardless of the underlying distribution details.

The expected cost framework combines deterministic and stochastic components:

\text{Cost}_{\text{spot}} = \text{spot\_rate} \times \left( T + \mathbb{E}[\text{interruptions}] \times \text{restart\_hours} \right)

where $\mathbb{E}[\text{interruptions}] = p \cdot T$ . The on-demand cost is purely deterministic: $\text{on\_demand\_rate} \times T$ . The recommendation is spot only if the expected spot cost is strictly less than the on-demand cost; otherwise, choose on-demand.

2. Algorithm Approach

This is a direct expected-value comparison problem. No search, sorting, or dynamic programming is needed. The approach is:

Compute the expected total compute time for the spot path: base hours plus expected restart overhead.
Multiply by the spot rate to get expected spot cost.
Compute the on-demand cost directly.
Compare the two values and return the appropriate string.

The pattern is: model the stochastic component via expectation, then reduce to a deterministic inequality.

3. Step-by-Step Strategy

👑

Continue the full explanation

You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.

🔒

Editor locked

The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.

solution.py

Python 3.13

Test Results

0/0

Run code to see test results.