n-th percentile latency for fan-out requests

Reference: https://ai.google/research/pubs/pub40801

Problem: Say there is a server with 99th (n = 99) percentile latency ≥ 1 seconds, when a root server needs to serve requests consulting N such servers, what percentage of requests will have latency ≥ 1 second.

Solution: 1 - pow(99/100, N) 

Explanation: 

What we need to estimate is joint probability when at least one of the requests will have latency ≥ 1. Flipping the definition, subtracting joint probability of all the requests getting sub-second latency from 1 gives us the required value. 

Since fan-out requests can be assumed to be independent events, the joint probability of all the requests getting sub-second latency is (0.99 x 0.99 ... N times). 

Example: For N = 100, 1 - pow(0.99, 100) = ~0.63. It means, about 63% of requests will have latency ≥ 1 second, when a root server hits 100 servers with 99th percentile latency of ≥ 1 second.