2
$\begingroup$

I'm writing some software which performs activities using an exponential back-off delay e.g. performs an action at t = 1, 2, 4, 8, 16 etc, assuming a base of 2. I want the base to adjust dynamically depending upon available resources so the activities occur more or less frequently as required.

I have arrived at the following equation:

$a = \sum_{i=1}^n\lfloor\log_b{p+t_i}\rfloor - \lfloor\log_b{t_i}\rfloor $

$a$ is the available resources, $p$ is the period in which to use those resources and $t_i$ is the amount of time since the last action on $i$. It essentially expresses how many actions will be taken on $i$ in the period $p$, then sums all the actions for all items.

How can I solve the above equation for $b$?

  • 0
    Is the first term inside the sum supposed to be $\lfloor \log_b(p+t_i) \rfloor$ or $\lfloor (\log_b\,p)+t_i \rfloor$? I'd usually parse it as the latter, but the former seems to make more sense in context.2011-08-19

1 Answers 1

1

In general, you won't have a unique solution, or even a unique interval of solutions. For a simple example, consider the case where $a = 1$ and $p$ is very small; then (assuming for simplicity that no two actions occur withing any period of length $p$) the equation is satisfied whenever $0 \le b^k-t_i < p$, i.e. when $\sqrt[k]{t_i} \le b < \sqrt[k]{t_i+p}$ for some $k$ and $i$.

However, I'd suggest an alternative approach. If I understand your intention correctly, you want to adjust the exponential backoff rate so that all available resources are used. Why not, instead of counting time in seconds or in some other arbitrary units, count it in available resources instead?

That is, pick some fixed $b$ (e.g. $b = 2$). When task $i$ starts at "time" $t$, assign it a start time of $t_i = t$ and a delay of $\delta_i = 1$ and put it in a queue. Whenever a resource becomes available, increment $t$ by one, pick the task with lowest $t_i + \delta_i$ from the queue and execute it. If it succeeds, remove it from the queue; if it doesn't, multiply its $\delta_i$ by $b$ and put it back in the queue.

  • 0
    I ended up going with a variant of this. Many thanks.2011-08-21