Stable Co-Eviction Cohorts for Hedging Spot Instance Portfolios

Cloud providers rent out spare servers ("spot instances") at discounts of up to 90%, but they can reclaim those servers on short notice. Systems that run serious workloads on spot capacity protect themselves by spreading replicas across many "pools", meaning combinations of instance type, availability zone, region and provider. The assumption behind this is that pools rarely fail together. That assumption is rarely tested. If two pools tend to lose capacity at the same moments, as they would when they share underlying hardware, regional demand or a provider-wide drain, then a "diversified" deployment can lose every replica at once.

We propose to measure which pools fail together and, more importantly, which of those groupings stay stable over time. Our tool is consensus clustering, which repeatedly reclusters resampled data and records how often each pair of items lands in the same group. We run it over blocks of time in multi-vendor spot availability traces, after compressing each pool's availability history with principal component analysis (PCA), a linear method that keeps only the few directions along which the data varies most. The output is a pool-by-pool matrix of co-eviction stability. A provisioner then uses this matrix as a hard constraint: it never treats two pools as independent unless they have been reliably separate across time. The claim is concrete and can be falsified. Under sparse, drifting eviction data, this constraint should reduce the rate at which all replicas are lost simultaneously, at equal cost, compared with diversifying by provider and zone labels, ranking pools by predicted reliability, or estimating correlations directly.

Where this sits

The spot literature motivates the problem but does not solve it. Making Cloud Spot Instance Interruption Events Visible collected nearly a year of AWS Spot Placement Scores (SPS, AWS's short-term availability signal), pricing data, and stress tests over 875 instance types on AWS, Azure and GCP. It shows that interruptions are far from random: P90 survival is 0.02 h on AWS versus 5.0 h on Azure, and price no longer tracks eviction risk. Its XGBoost predictor scores each pool separately. It does not ask which pools move together. Parcae forecasts only the total number of available instances with a univariate model. SpotServe reacts to individual preemption warnings. FogROS2-FT races redundant replicas across clouds and treats pools as interchangeable black boxes. Each of these systems would benefit from knowing which replicas share a fate, and none of them estimates it.

Statistical Guarantees for Consensus Clustering supplies the aggregation method. It averages same-cluster indicator matrices across many clusterings, which avoids having to match cluster labels between runs, and it adds spectral aggregation and local refinement. That paper also constrains our design. Its guarantees assume the input clusterings are independent and identically distributed, and it flags correlated resamples as an open problem. Time-block resamples of an availability trace are exactly such correlated inputs, so we treat that paper's theory as a reference point to test against, not as a guarantee we inherit. The PCA step follows the evidence in Simple and Effective Unsupervised Redundancy Elimination: on high-dimensional signals with low intrinsic dimension, unsupervised PCA beat supervised projection. Its finding that projections fitted on one distribution degrade on shifted data is the same drift risk we must measure. Provider-side work on temporal patterns, such as Coach, groups VMs by usage complementarity using fixed time windows. We use the same idea of temporal co-movement, but apply it to tenant-side eviction risk and ask whether the groups are stable.

Core claim and mechanism

Let $A$ be a pools-by-time matrix of hourly availability signals. These are SPS values on AWS, and interruption indicators from the stress-test traces on all three vendors. We center $A$ and keep its top $r$ principal components. Each pool then becomes a short vector describing how strongly it responds to shared "capacity drain" factors. We then draw $B$ contiguous time-block resamples, cluster pools in factor space for each resample, and form

$$M_{ij} = \frac{\#\{b : \text{pools } i, j \text{ co-clustered in block resample } b\}}{\#\{b : i, j \text{ both observed in } b\}}.$$

$M_{ij}$ near 1 means pools $i$ and $j$ reliably fail together. Near 0 means they are reliably separate. Near 0.5 means the evidence is ambiguous.

The provisioner chooses a set $S$ of pools to minimize total hourly price $\sum_{i \in S} c_i$, where $c_i$ is pool $i$'s price. It must meet a predicted availability floor and satisfy $\sum_{i<j \in S} \min(1, 2M_{ij}) \le \tau$, where $\tau$ is a correlation budget. The $\min(1, 2M_{ij})$ term charges ambiguous pairs almost as heavily as stably correlated ones. This conservative treatment of uncertain pairs is the main difference from estimating a correlation matrix and plugging in the point estimate.

Research Program

The first stage is pure measurement. We ask how much variance the top few components of $A$ explain, and whether the leading component is provider-wide, regional or tied to an instance family. We also examine the empirical cumulative distribution of $M$: does it split cleanly toward 0 and 1 (stable cohorts), or pile up around 0.5? This stage has value on its own, because it tests the independence assumption that existing portfolio hedging relies on.

The second stage builds the provisioner above. It runs in trace-driven simulation and is fitted only on the past, with weekly roll-forward refits.

The third stage tests whether the independence-based theory of consensus clustering still describes behavior when inputs are correlated. We compare block resamples against independent-hour resamples, and measure how co-clustering error decays as $B$ grows. This addresses the open question raised by the consensus-clustering paper.

Baselines

The naive reference point is label diversification: spread $k$ replicas across distinct providers, then regions, then zones, choosing the cheapest pool within each. This is the uncorrelated-pools assumption in practice. It is the default we must beat.

The strongest published per-pool method is SPS-based selection from Making Cloud Spot Instance Interruption Events Visible. Its XGBoost model reaches F1 0.97–0.99 at predicting SPS, and selecting pools by its predictions improved median running time by 63.2% for high-score pools and 168% for SPS-1 pools. We retrain it on the same rolling windows and pick the top-$k$ predicted pools under the same cost cap. It is the strongest competitor because it already captures most of the per-pool signal. Any gain we show must therefore come from the joint failure structure, not from better individual forecasts.

The strongest correlation-aware alternative is a portfolio that uses a shrinkage-regularized empirical covariance of eviction indicators, in the style of mean–variance optimization. For ExoSphere-style correlation portfolios on these traces, no reported result was found on Lacuna, so we implement it ourselves.

All methods see identical training windows and cost caps. Every method, ours included, gets the same hyperparameter search budget, covering shrinkage strength, $r$, $B$ and $\tau$, tuned on a held-out validation month.

Ablations isolate each ingredient: a single clustering instead of consensus; consensus on the raw $A$ without PCA; independent resampling of hours instead of time blocks; and the point-estimate $M_{ij}$ in place of the conservative penalty.

Beating the baselines means a statistically significant reduction in total-wipeout events, meaning all $k$ replicas lost within the same 30-minute window. This must hold on the held-out final two months at equal or lower cost, with confidence intervals obtained by bootstrapping over weeks.

Why not just…?

Why not just diversify across providers and zones? The traces already show provider-level structure strong enough that labels carry real information. A 250-fold gap in P90 survival between AWS and Azure is a provider-level effect. But labels say nothing about correlation within a provider or across providers, for example when regional demand surges hit several clouds at once. The label baseline is in the experiment. If it matches our method, we will report that labels are sufficient.

Why not just pick the pools with the highest predicted reliability? Per-pool ranking tends to pick pools that are reliable for the same reason, such as one large, quiet region, so it concentrates risk. The comparison against XGBoost selection on wipeout rate, rather than median running time, is designed to show exactly this effect. If the top-ranked pools turn out to have low $M_{ij}$ with each other, this objection wins.

Why not use the correlation matrix directly, or a PCA factor model, without clustering? This is the real threat. Shrinkage covariance and factor exposure constraints are mature and simpler. Our bet is that evictions are rare, so pairwise correlations computed from them are noisy and drift over time, while stability across time blocks is a better guide to out-of-sample co-failure. The PCA-only factor-model baseline and the shrinkage baseline decide this directly. If either matches our method on held-out wipeout rate, we drop the consensus step from the method. The contribution would then shrink to the measurement study and the block-resampling analysis.

Proposed Experiments

We run everything on the multi-vendor spot interruption traces from Nov 2022 to Aug 2023, training on the first seven months and testing on the last two. As a second regime, we replay the AWS preemption traces used by Parcae and SpotServe to check transfer to the training and serving settings those systems target.

The workload is a $k$-replica service with $k \in \{2, 3, 5\}$, simulated two ways. The first is FogROS2-FT-style racing, where FogROS2-FT reports 2.2x cost reduction and 5.53x lower P99 latency in motion planning. The second is a quorum service that fails when a majority of replicas is lost. Metrics are wipeout rate, majority-loss rate, cost per available replica-hour, and the fraction of $M$ entries in the ambiguous band from 0.3 to 0.7.

Two outcomes would be decisive. First, if $M$ is mostly ambiguous on held-out data, stable co-eviction cohorts do not exist, and the hedging method has no basis. Second, if our method beats the shrinkage-covariance baseline on wipeout rate across both trace sources, conservative stability-based hedging is shown to beat direct correlation estimates. A known limitation is coverage: Azure and GCP expose coarser availability signals than AWS SPS, so the non-AWS pools will have sparser rows in $A$. We report results per vendor separately for this reason.