Hedged Requests Expected Completion Time

Problem Statement

To cut tail latency, an agent can hedge: send a backup request if the first has not returned by a delay d. Given each replica's response time, compute when the overall result arrives under a hedging policy.

Background

There are n replicas with known latencies lat[i]. The policy: launch replica 0 at time 0. If it has not completed by time d, launch replica 1 at time d; if neither has completed by 2d, launch replica 2 at 2d; and so on (one new hedge every d until all launched). Replica i (0-indexed) is launched at time i*d and completes at i*d + lat[i]. The overall result is the minimum completion time across all launched replicas. All replicas end up launched eventually (over an unbounded deadline), so consider every replica's i*d + lat[i].

Your Task

def hedged_completion(lat, d):

Return the earliest overall completion time (float), rounded to 4 decimals.

Input Format

• lat (list of floats), d (float).

Output Format

• A float rounded to 4 decimals.

Sample

print(hedged_completion([10.0, 2.0], 1.0))

Output:

3.0