Hedged Requests Expected Completion Time

1. Background Knowledge

Request hedging is a latency-reduction technique used in distributed systems. Instead of waiting indefinitely for a single slow replica, the client issues a duplicate (or "hedge") request to a second replica after a timeout. The first response to arrive is accepted, and the others are cancelled. This trades a small amount of extra compute for a significant reduction in tail latency, because the worst-case wait is bounded by the faster of the two replicas rather than the slower one.

In this problem the hedging policy is staggered: replica $i$ is not launched at time $0$ but at time $i \cdot d$, where $d$ is the hedge interval. This models a system that adds one more backup per interval until all replicas have been tried. Each replica $i$ therefore completes at:

The overall result is delivered as soon as any replica finishes, so the completion time is $\min_i t_i$. Because the deadline is unbounded, every replica is eventually launched, and we must consider all $n$ candidates.

A useful mental model: think of each replica as a "race" that starts at a different time. The winner is the one whose start time plus its own latency is smallest.

2. Algorithm Approach

This is a brute-force minimization over $n$ candidates. There is no sorting, binary search, or dynamic programming required. For each index $i$ from $0$ to $n-1$, compute the completion time $i \cdot d + \text{lat}[i]$ and track the minimum. The problem reduces to a single linear scan.

The key insight is that the launch schedule is deterministic and independent of the latencies, so there is no need to simulate events in chronological order. You can evaluate every replica's finish time directly and take the minimum.

3. Step-by-Step Strategy

• Validate inputs: Ensure lat is a non-empty list and d is a non-negative float.
• Initialize a variable best to a large value (e.g., float('inf')).
• Loop over each index i in range(len(lat)):
• Compute finish = i * d + lat[i].
• If finish < best, update best = finish.
• Round the result to 4 decimal places using round(best, 4).
• Return the rounded float.

Pseudocode sketch:

def hedged_completion(lat, d):
 best = float('inf')
 for i in range(len(lat)):
 finish = i * d + lat[i]
 if finish < best:
 best = finish
 return round(best, 4)

4. Common Pitfalls

• Off-by-one in launch time: Replica $i$ launches at $i \cdot d$, not $(i+1) \cdot d$. Replica 0 launches at time 0.
• Forgetting to consider all replicas: Even if an early replica finishes quickly, a later replica with a very small latency could finish even earlier. You must scan all $n$ entries.
• Rounding errors: Use round(value, 4) at the very end, not during intermediate comparisons. Rounding mid-loop can cause incorrect minimum selection.
• Integer vs. float division: In Python 3, / always produces a float, but if d or lat[i] are integers, ensure the multiplication i * d is treated as float arithmetic. This is usually automatic, but be cautious if mixing types.
• Empty list: If lat is empty, the problem is undefined. Decide on a sensible default (e.g., return 0.0 or raise an error) and document it.
• Negative latencies: While physically meaningless, the formula still works mathematically. If the problem guarantees non-negative latencies, no extra check is needed.

5. Time & Space Complexity

• Time complexity: $O(n)$, where $n = \text{len}(\text{lat})$. A single pass computes $n$ finish times and tracks the minimum.
• Space complexity: $O(1)$ auxiliary space. Only a constant number of variables (best, loop index) are used regardless of input size. The input list itself is not modified.