Model

Hedged requests

Hedging converts a latency distribution into the minimum of k draws, at a cost of k× work on the hedged fraction only.

P (slow) = p^{k} (k independent attempts), extra load \approx the hedged fraction

$p$: Slow probability; chance one attempt is slow
$k$: Attempts; independent attempts raced

Recurring principle: Independence is assumed

How it behaves

One input on the horizontal axis, the others held fixed.

p = 5% (hedge at p95)p = 1%

Data table

Chance a request is slow, by attempts raced
Attempts k	series	Slow requests
1	p = 5% (hedge at p95)	5%
1.04	p = 5% (hedge at p95)	4.47%
1.07	p = 5% (hedge at p95)	3.99%
1.11	p = 5% (hedge at p95)	3.57%
1.15	p = 5% (hedge at p95)	3.19%
1.19	p = 5% (hedge at p95)	2.85%
1.23	p = 5% (hedge at p95)	2.55%
1.26	p = 5% (hedge at p95)	2.28%
1.3	p = 5% (hedge at p95)	2.04%
1.34	p = 5% (hedge at p95)	1.82%
1.38	p = 5% (hedge at p95)	1.63%
1.41	p = 5% (hedge at p95)	1.45%
1.45	p = 5% (hedge at p95)	1.3%
1.49	p = 5% (hedge at p95)	1.16%
1.52	p = 5% (hedge at p95)	1.04%
1.56	p = 5% (hedge at p95)	0.927%
1.6	p = 5% (hedge at p95)	0.829%
1.64	p = 5% (hedge at p95)	0.741%
1.68	p = 5% (hedge at p95)	0.662%
1.71	p = 5% (hedge at p95)	0.592%
1.75	p = 5% (hedge at p95)	0.529%
1.79	p = 5% (hedge at p95)	0.473%
1.82	p = 5% (hedge at p95)	0.422%
1.86	p = 5% (hedge at p95)	0.377%
1.9	p = 5% (hedge at p95)	0.337%
1.94	p = 5% (hedge at p95)	0.301%
1.98	p = 5% (hedge at p95)	0.269%
2.01	p = 5% (hedge at p95)	0.241%
2.05	p = 5% (hedge at p95)	0.215%
2.09	p = 5% (hedge at p95)	0.192%
2.13	p = 5% (hedge at p95)	0.172%
2.16	p = 5% (hedge at p95)	0.154%
2.2	p = 5% (hedge at p95)	0.137%
2.24	p = 5% (hedge at p95)	0.123%
2.27	p = 5% (hedge at p95)	0.11%
2.31	p = 5% (hedge at p95)	0.098%
2.35	p = 5% (hedge at p95)	0.088%
2.39	p = 5% (hedge at p95)	0.078%
2.42	p = 5% (hedge at p95)	0.07%
2.46	p = 5% (hedge at p95)	0.063%
2.5	p = 5% (hedge at p95)	0.056%
2.54	p = 5% (hedge at p95)	0.05%
2.58	p = 5% (hedge at p95)	0.045%
2.61	p = 5% (hedge at p95)	0.04%
2.65	p = 5% (hedge at p95)	0.036%
2.69	p = 5% (hedge at p95)	0.032%
2.73	p = 5% (hedge at p95)	0.029%
2.76	p = 5% (hedge at p95)	0.026%
2.8	p = 5% (hedge at p95)	0.023%
2.84	p = 5% (hedge at p95)	0.02%
2.88	p = 5% (hedge at p95)	0.018%
2.91	p = 5% (hedge at p95)	0.016%
2.95	p = 5% (hedge at p95)	0.015%
2.99	p = 5% (hedge at p95)	0.013%
3.02	p = 5% (hedge at p95)	0.012%
3.06	p = 5% (hedge at p95)	0.01%
3.1	p = 5% (hedge at p95)	0.009%
3.14	p = 5% (hedge at p95)	0.008%
3.17	p = 5% (hedge at p95)	0.007%
3.21	p = 5% (hedge at p95)	0.007%
3.25	p = 5% (hedge at p95)	0.006%
3.29	p = 5% (hedge at p95)	0.005%
3.33	p = 5% (hedge at p95)	0.005%
3.36	p = 5% (hedge at p95)	0.004%
3.4	p = 5% (hedge at p95)	0.004%
3.44	p = 5% (hedge at p95)	0.003%
3.48	p = 5% (hedge at p95)	0.003%
3.51	p = 5% (hedge at p95)	0.003%
3.55	p = 5% (hedge at p95)	0.002%
3.59	p = 5% (hedge at p95)	0.002%
3.63	p = 5% (hedge at p95)	0.002%
3.66	p = 5% (hedge at p95)	0.002%
3.7	p = 5% (hedge at p95)	0.002%
3.74	p = 5% (hedge at p95)	0.001%
3.77	p = 5% (hedge at p95)	0.001%
3.81	p = 5% (hedge at p95)	0.001%
3.85	p = 5% (hedge at p95)	0.001%
3.89	p = 5% (hedge at p95)	0.001%
3.92	p = 5% (hedge at p95)	0.001%
3.96	p = 5% (hedge at p95)	0.001%
4	p = 5% (hedge at p95)	0.001%
1	p = 1%	1%
1.04	p = 1%	0.841%
1.07	p = 1%	0.708%
1.11	p = 1%	0.596%
1.15	p = 1%	0.501%
1.19	p = 1%	0.422%
1.23	p = 1%	0.355%
1.26	p = 1%	0.299%
1.3	p = 1%	0.251%
1.34	p = 1%	0.211%
1.38	p = 1%	0.178%
1.41	p = 1%	0.15%
1.45	p = 1%	0.126%
1.49	p = 1%	0.106%
1.52	p = 1%	0.089%
1.56	p = 1%	0.075%
1.6	p = 1%	0.063%
1.64	p = 1%	0.053%
1.68	p = 1%	0.045%
1.71	p = 1%	0.038%
1.75	p = 1%	0.032%
1.79	p = 1%	0.027%
1.82	p = 1%	0.022%
1.86	p = 1%	0.019%
1.9	p = 1%	0.016%
1.94	p = 1%	0.013%
1.98	p = 1%	0.011%
2.01	p = 1%	0.009%
2.05	p = 1%	0.008%
2.09	p = 1%	0.007%
2.13	p = 1%	0.006%
2.16	p = 1%	0.005%
2.2	p = 1%	0.004%
2.24	p = 1%	0.003%
2.27	p = 1%	0.003%
2.31	p = 1%	0.002%
2.35	p = 1%	0.002%
2.39	p = 1%	0.002%
2.42	p = 1%	0.001%
2.46	p = 1%	0.001%
2.5	p = 1%	0.001%
2.54	p = 1%	0.001%
2.58	p = 1%	0.001%
2.61	p = 1%	0.001%
2.65	p = 1%	0.001%
2.69	p = 1%	0%
2.73	p = 1%	0%
2.76	p = 1%	0%
2.8	p = 1%	0%
2.84	p = 1%	0%
2.88	p = 1%	0%
2.91	p = 1%	0%
2.95	p = 1%	0%
2.99	p = 1%	0%
3.02	p = 1%	0%
3.06	p = 1%	0%
3.1	p = 1%	0%
3.14	p = 1%	0%
3.17	p = 1%	0%
3.21	p = 1%	0%
3.25	p = 1%	0%
3.29	p = 1%	0%
3.33	p = 1%	0%
3.36	p = 1%	0%
3.4	p = 1%	0%
3.44	p = 1%	0%
3.48	p = 1%	0%
3.51	p = 1%	0%
3.55	p = 1%	0%
3.59	p = 1%	0%
3.63	p = 1%	0%
3.66	p = 1%	0%
3.7	p = 1%	0%
3.74	p = 1%	0%
3.77	p = 1%	0%
3.81	p = 1%	0%
3.85	p = 1%	0%
3.89	p = 1%	0%
3.92	p = 1%	0%
3.96	p = 1%	0%
4	p = 1%	0%

Worked examples, recomputed

Every number the mechanisms quote for this relationship is recomputed from it, so none of them disagrees with it.

Where it appears

Each mechanism states it in its own names. The general symbol each name stands for is shown with it.

Distributed Systems Coordination
Who is allowed to decide, and how does everyone else learn the decision without asking?
$p^{2}$
Read it in place →
Fault Tolerance & Delivery Semantics
What is the cheapest thing that can be safely done twice?
$ε^{n}$
ε (failure per attempt) = $p$ · n (attempts) = $k$
Read it in place →