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 . Adding a cache takes half a second initially and raises the success probability to [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.
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 , giving .
In the cached variant, the expected number of requests is . Its half-second initialization cost brings the same upper bound of two seconds.
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 , its second moment measures the expected squared runtime. Together with the mean, it determines the variance:
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 .
Replacing reward 1 by this increment makes the accumulated reward equal on every terminating execution [Schröer and Katoen 2026, Appendix B.2].
Apply the transformation to every original reward, including initialization costs.
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 :
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.
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 , the number of requests up to and including the first success satisfies
Without caching, and . With caching, and , so .
At 1 second, half the uncached requests have finished, while cached requests take at least 1.5 seconds. At 2.5 seconds, of uncached requests are still waiting, compared with of cached requests.
| Design | Mean runtime | Second moment | Variance |
|---|---|---|---|
| Without a cache | s | s | s |
| With a cache | s | s | s |
The cache reduces the variance while preserving the mean.
See Also
- Geometric Loop compares upper and lower bounds for the number of unsuccessful coin flips.
- Programmatic Reward Transformations explains the general construction and further objectives.
References
-
Schröer and Katoen (2026). Highly Incremental: A Simple Programmatic Approach for Many Objectives. FM 2026.
Introduces the retry/cache comparison and gives the reward transformation, exact moment calculations, and HeyVL proofs.
(Appendix B.2)