Symptom

A batch job holds a database connection. Between queries it idles, sometimes for 20 milliseconds, sometimes for 20 minutes. Keeping the connection open costs a slot in a pool that other work wants. Closing it costs a reconnect — TLS handshake, authentication, maybe 200 milliseconds — if the job turns out to need it again.

So: how long do you wait before closing?

Someone suggests 30 seconds, because 30 seconds sounds reasonable. Someone else suggests 5 minutes for the same reason. There is no data that settles it, because the idle-gap distribution changes every time the workload changes, and the whole question feels like it can only be answered by guessing and watching.

It can be answered without guessing, and without knowing the distribution at all. The same question is spin-then-block in a mutex, keep-alive timeouts, autoscaling down after a traffic dip, and whether to cache a computed value. It has one answer, it is provable, and the answer is: wait exactly as long as the one-time cost.

Statement

Strip the problem to its skeleton. You are skiing for an unknown number of days. Renting skis costs $1 per day. Buying costs $B, once, and then skiing is free. Each morning you learn only that you are skiing again today. When do you buy?

The difficulty is that there is no “best” algorithm in the ordinary sense, because the input arrives over time and any fixed choice is wrong for some input. Competitive analysis handles this by changing what “best” means.

Competitive ratio. An online algorithm $A$ is $c$-competitive if for every input sequence $\sigma$,

$$\text{cost}_A(\sigma) \le c \cdot \text{cost}_{\text{OPT}}(\sigma) + \alpha$$

where OPT is an optimal offline algorithm that sees the entire sequence in advance and $\alpha$ is a constant independent of $\sigma$. When $\alpha = 0$ the algorithm is strictly $c$-competitive.

This is a worst-case guarantee against an omniscient competitor, which sounds impossibly demanding and turns out to be achievable with small constants.

Ski rental. The deterministic strategy “rent for $B-1$ days, buy on day $B$” is $2$-competitive, and no deterministic algorithm achieves a ratio better than $2 - 1/B$.

Randomizing improves this: there is a randomized strategy that is $\frac{e}{e-1} \approx 1.58$-competitive against an oblivious adversary, and that is optimal.

Argument

The upper bound: rent-then-buy is 2-competitive. Let the actual number of ski days be $d$, unknown to us, known to OPT. OPT’s cost is $\min(d, B)$: rent throughout if the trip is short, buy on day one if it is long.

Our algorithm rents through day $B-1$ and buys on day $B$.

Case $d < B$. We never buy, so we pay $d$. OPT pays $d$. Ratio 1.

Case $d \ge B$. We pay $B - 1$ in rentals plus $B$ to buy, so $2B - 1$. OPT pays $B$. The ratio is $(2B-1)/B = 2 - 1/B < 2$.

Those are all the cases, so the algorithm is $(2 - 1/B)$-competitive. We never pay more than twice what perfect foresight would have paid, for any input whatsoever, with no assumption about how long the trip is. That is a strong guarantee obtained from an argument that fits in a paragraph.

The lower bound: no deterministic algorithm does better. A deterministic algorithm is just a choice of day $k$ on which it buys, fixed in advance. The adversary knows $k$ because the algorithm is deterministic, and stops the season immediately after the purchase: $d = k$.

Then we pay $(k-1) + B$ and OPT pays $\min(k, B)$.

If $k \le B$, the ratio is $\frac{k - 1 + B}{k}$, which is minimised over integer $k \le B$ at $k = B$, giving $\frac{2B-1}{B} = 2 - 1/B$. If $k > B$, OPT pays $B$ and we pay $k - 1 + B > 2B - 1$, which is worse. So every deterministic algorithm has ratio at least $2 - 1/B$, and rent-then-buy attains it. The strategy is not merely good, it is optimal among deterministic strategies, which is the part that makes it a theorem rather than a heuristic.

Why the break-even rule is the right shape. Notice what the optimal $k$ is: buy when the money already spent renting equals the purchase price. The rule generalises far beyond skis, and it always reads the same way — spend on the speculative option until you have spent what the certain option costs, then take the certain option. That single sentence is the entire practical content, and it needs no distribution, no forecast, and no tuning.

Randomization beats it, which is not obvious. The deterministic lower bound came entirely from the adversary knowing $k$. Against an oblivious adversary — one that fixes $d$ before seeing our coin flips — we can hide $k$ in a distribution and the adversary can no longer target it.

The optimal distribution puts probability on buying on each day $i \le B$ with weight proportional to $\left(\frac{B-1}{B}\right)^{B-i}$. As $B$ grows this approaches a continuous distribution with density $\propto e^{x}$ on $x \in [0,1]$ where $x = k/B$, and the resulting expected ratio is

$$\frac{e}{e-1} \approx 1.58$$

The intuition: an exponentially-weighted schedule makes the algorithm’s expected cost equal for every choice of $d$ the adversary might pick, so the adversary has no best response and the ratio cannot be pushed above $e/(e-1)$. Equalising the adversary’s payoff across all its options is the standard way these optimal randomized bounds are found, and it is LP duality wearing a disguise. A 25% improvement in the worst-case guarantee, purchased with a random number, is the cheapest use of randomness in this book.

Translating to the connection. Reconnecting costs 200 ms of work. Holding an idle connection costs, say, the pool slot, which we price per millisecond of idleness. Then $B$ = the idle duration whose holding cost equals 200 ms of reconnect work, and the rule says: hold the connection idle for exactly that long, then close it. For spin-then-block the same rule is famous and the units are cleaner still: spin for exactly as long as a context switch costs, then block. That is $2$-competitive against an oracle that knows how long the lock will be held, and it is why “spin for about a microsecond” appears in mutex implementations that never mention competitive analysis.

Autoscaling is the same problem with the sign flipped. Scaling down releases an instance you are paying for; scaling back up costs a cold start. Keep the instance until the accumulated idle spend equals one cold start, then release. The usual industrial default — a fixed cooldown chosen because it “felt right” — is the same rule with $B$ guessed instead of measured.

Forbids

Claiming that any online policy can match offline optimal. For ski rental, $2 - 1/B$ is a floor for deterministic algorithms. No cleverness, no heuristic, no machine-learned timeout beats it in the worst case. Improvement must come from assumptions about the input, and then the guarantee is about those assumptions rather than about the algorithm.

Tuning a timeout without reference to the switching cost. The optimal threshold is determined by $B$ alone. A timeout that is not approximately the one-time cost is leaving a provable factor on the table, in one direction or the other.

Treating the choice as unanswerable without workload data. The whole point of the ratio is that it holds for every input. You do not need the distribution to get within 2x of optimal, and the people arguing about whether 30 seconds or 5 minutes is right are arguing about a question the theory already closed.

Does not forbid

It does not say the 2-competitive rule is the best thing to run. This is the misreading that matters, and it is common among people who have just learned the framework. Competitive analysis bounds the worst case. If you actually know your idle gaps are bimodal — a millisecond or an hour, nothing between — then a distribution-aware policy beats the break-even rule on your traffic by a wide margin, and the 2-competitive guarantee is a floor to fall back on rather than a target to hit. Real systems should use the rule as a default and specialise where they have data.

It does not make LRU a bad cache policy, which is the field’s own most famous false alarm. Competitive analysis assigns LRU a ratio of $k$ on a cache of size $k$, which sounds terrible and led to a decade of people quoting it as evidence that LRU is weak. It is not; the bound is tight only against adversarial sequences no real workload produces. This is famous enough to have prompted its own repair, and the post on Belady’s algorithm and LRU competitiveness is about that repair.

It does not require the adversary to be real. No one is choosing your idle gaps to hurt you. The adversary is a proof device that produces a guarantee holding for all inputs, including the ones your monitoring has never seen. The guarantee is worth having precisely for those.

It does not forbid learning. Algorithms with predictions — the learning-augmented model — takes a possibly-wrong prediction of $d$ and gets a ratio that degrades gracefully with prediction error: near-1 when the prediction is good, still bounded when it is garbage. A machine-learned timeout with a competitive fallback is not a contradiction of this post, it is the current research frontier of it.

Boundary

  • Worst case only. The ratio says nothing about typical performance. An algorithm with a worse ratio can beat a better one on every input you will actually see.
  • The additive constant hides a lot. A $2$-competitive-plus-$\alpha$ algorithm with huge $\alpha$ is useless at small scale, and papers are not always loud about $\alpha$.
  • Adversary model matters for randomized bounds. The $e/(e-1)$ result needs an oblivious adversary. Against an adaptive one that sees your coin flips, randomization buys nothing and you are back to 2.
  • Costs must be known. The rule needs $B$. When the switching cost itself varies — a reconnect that is sometimes 20 ms and sometimes 2 s — you are in a harder problem, and the usual repair is to use a pessimistic $B$ and accept a looser constant.
  • Resource augmentation is the standard escape. Giving the online algorithm slightly more resource than OPT collapses many hopeless-looking ratios to small constants. That is the trick the LRU analysis needs, and it is what rescues the ratio above.

The rule to carry: wait until you have spent what committing would cost, then commit. It is optimal, it is one line, and it applies every time you are choosing between paying repeatedly and paying once.