How to implement exponential backoff/delay calculation with fixed timeout and number of attempts?

Question

Most backoff/delay algorithms I've seen have fixed number of attempts OR fixed timeout, but not both.

I want to make exactly M attempts within T seconds, with exponential spacing between them, so that "T = delay(0) + delay(1) + ... + delay(M-1)", where "delay(N) = (e^N - 1) / e" (where N - retry number).

How to calculate "e" value in the description above, so that exactly M attempts will be made within overall timeout T (with M and T specified in advance)?

Answer 1

Since "T" is a monotonous function of "e", you can perform a binary search to find the best value that fits.

Here's an example Python program to find such "e" given "T" and "M":

def total_time(e, M):
    current = 1
    total = 0
    for i in range(M):
        total += current-1
        current *= e
    return total

def find_best_e(T, M):
    a, b = 0, T
    while abs(a-b) > 1e-6:
        m = (a+b)/2.0
        if total_time(m, M) > T:
            b = m
        else:
            a = m
    return (a+b)/2


e = find_best_e(10, 3)
print([e**n-1 for n in range(3)])