Skip to main content

Retry Latency and Higher Moments

A web server retries a database request until it succeeds. Each request takes one second and succeeds independently with probability 1/21/2. Adding a cache takes half a second initially and raises the success probability to 2/32/3 [Schröer and Katoen 2026]. Both designs take two seconds on average, but does the cache make the response time more predictable?

Expected Runtime​

The reward statement collects the modeled runtime: one second for every request, including the successful one. Other program statements add no time in this model. With postexpectation 0, the @wp specification bounds the expected accumulated reward.

Expected runtime without a cache
Expected: Verified
@wp
coproc retry_mean() -> (done: Bool)
pre 2
post 0
{
done = false
@invariant([!done] * 2)
while !done {
reward 1
done = flip(0.5)
}
}

The invariant 2 * [!done] bounds the expected remaining runtime by two seconds while requests are still needed. One iteration incurs one second and leaves another two seconds to be paid with probability 1/21/2, giving 1+12⋅2=21+\tfrac12\cdot2=2.

In the cached variant, the expected number of requests is 3/23/2. Its half-second initialization cost brings the same upper bound of two seconds.

Expected runtime with a cache
Expected: Verified
@wp
coproc cached_retry_mean() -> (done: Bool)
pre 2
post 0
{
done = false
reward 0.5
@invariant([!done] * 1.5)
while !done {
reward 1
done = flip(2/3)
}
}

Second Moments​

For runtime TT, its second moment E[T2]\mathbb{E}[T^2] measures the expected squared runtime. Together with the mean, it determines the variance:

Var⁡(T)=E[T2]−E[T]2.\operatorname{Var}(T)=\mathbb{E}[T^2]-\mathbb{E}[T]^2.

To collect the square incrementally, introduce a fresh ghost variable tau that records elapsed time. The original guards, probabilities, and assignments do not read tau. An additional second increases the square by (tau+1)2−tau2=2⋅tau+1(\mathtt{tau}+1)^2-\mathtt{tau}^2=2\cdot\mathtt{tau}+1. Replacing reward 1 by this increment makes the accumulated reward equal T2T^2 on every terminating execution [Schröer and Katoen 2026, Appendix B.2].

Apply the transformation to every original reward, including initialization costs.

Second moment without a cache
Expected: Verified
@wp
coproc retry_second_moment() -> (done: Bool)
pre 6
post 0
{
done = false
var tau: UInt = 0
@invariant([!done] * (6 + 4 * tau))
while !done {
reward 2 * tau + 1
tau = tau + 1
done = flip(0.5)
}
}

For an unfinished request sequence, the invariant 6 + 4 * tau bounds the squared-time increments still to come. One iteration collects 2 * tau + 1 and continues with probability 1/21/2:

(2⋅tau+1)+12⋅(6+4⋅(tau+1))=6+4⋅tau.\begin{aligned} &(2\cdot\mathtt{tau}+1)\\ &\quad+\tfrac12\cdot\bigl(6+4\cdot(\mathtt{tau}+1)\bigr)\\ &=6+4\cdot\mathtt{tau}. \end{aligned}

Starting at tau = 0 gives the verified upper bound of six squared seconds. On a nonterminating execution, these incremental rewards also grow without bound. A single reward tau * tau after the loop would never be reached on that execution and would collect no reward.

For the cached design, tau starts at 0.5 and reward 0.25 accounts for the square of the initialization time. The loop uses the same increments, with an invariant adapted to the larger success probability.

Second moment with a cache
Expected: Verified
@wp
coproc cached_retry_second_moment() -> (done: Bool)
pre 4.75
post 0
{
done = false
var tau: UReal = 0.5
reward 0.25
@invariant([!done] * (4.5 + 3 * (tau - 0.5)))
while !done {
reward 2 * tau + 1
tau = tau + 1
done = flip(2/3)
}
}

Comparing the Designs​

The procedures above prove upper bounds on the first two moments. To determine the variance, we also need matching lower bounds. We omit those proofs here and use the exact moment values calculated below [Schröer and Katoen 2026, Appendix B.2].

If each request succeeds independently with probability 0<p≤10<p\le1, the number KK of requests up to and including the first success satisfies

E[K]=1p,E[K2]=2−pp2.\mathbb{E}[K]=\frac1p, \qquad \mathbb{E}[K^2]=\frac{2-p}{p^2}.

Without caching, T=KT=K and p=1/2p=1/2. With caching, T=1/2+KT=1/2+K and p=2/3p=2/3, so E[T2]=1/4+E[K]+E[K2]\mathbb{E}[T^2]=1/4+\mathbb{E}[K]+\mathbb{E}[K^2].

At 1 second, half the uncached requests have finished, while cached requests take at least 1.5 seconds. At 2.5 seconds, 1/41/4 of uncached requests are still waiting, compared with 1/91/9 of cached requests.

Probability of still waiting with and without a cacheThe uncached probability drops by a factor of two after each whole second. The cached probability drops by a factor of three at 1.5 seconds and once per second thereafter. At one second the uncached probability is one half and the cached probability is one. At 2.5 seconds the probabilities are one quarter without a cache and one ninth with a cache.Chance of still waiting0%50%100%01234Elapsed time (s)Without cacheWith cache
DesignMean runtimeSecond momentVariance
Without a cache22 s66 s2^222 s2^2
With a cache22 s4.754.75 s2^20.750.75 s2^2

The cache reduces the variance while preserving the mean.

See Also​

References​