Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$?

share|improve this question
    
I don't think you can do this analytically; I'd use a numerical rootfinding method like bisection instead (assuming I have some good guess for the value of $b$). –  J. M. Aug 19 '11 at 9:10
    
What are the characteristic time scale and range of $b$ is expected and what accuracy is needed? As the first approximation one can take the value from the equation without floors $ b= \left(\prod_{i=1}^n(1+p/t_i)\right)^{1/a}\;$, then fine tune somehow the obtained value. Say, substitute $b$ into the original equation take into account the sign of $lhs-rhs$. May be it is worth to check on real data to see how essential are floors here, if by some chance the accuracy of the first step is enough. –  Andrew Aug 19 '11 at 9:23
    
Thanks Andrew, I should have mentioned that I did solve for b without the floors, however it turns out they're quite important. Without them, if a is below a certain threshold, the resources can be allocated in such a way that each item is allocated less than zero. The total of all resources allocated is correct, but because the actions are discrete, they don't execute in the period. Hope that makes sense. Any other way to solve for b? –  pricj004 Aug 19 '11 at 10:35
    
Thanks J.M., I'm not familiar with rootfinding, but I'll do some research. I had hoped to find an algebraic solution. –  pricj004 Aug 19 '11 at 10:39
    
Edit to the above comment to Andrew: I meant each item is allocated less than one –  pricj004 Aug 19 '11 at 10:50
show 1 more comment

1 Answer

up vote 1 down vote accepted

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.

share|improve this answer
    
I ended up going with a variant of this. Many thanks. –  pricj004 Aug 21 '11 at 1:06
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.