Exponential backoff generator

Question

Exponential backoff in the context of various networking protocols looks something like this:

1. When a collision first occurs, send a "Jamming signal" to prevent further data being sent.
2. Resend a frame after either 0 seconds or 51.2μs, chosen at random.
3. If that fails, resend the frame after either 0s, 51.2μs, 102.4μs, or 153.6μs.
4. If that still doesn't work, resend the frame after k · 51.2μs, where k is a random integer between 0 and 2³ − 1.
5. In general, after the cth failed attempt, resend the frame after k · 51.2μs, where k is a random integer between 0 and 2^c − 1.

I've written a generator that handles this:

def exponential_backoff(k):
 num_failed = 0
 while True:
 suceeded = yield k*random.randint(0, 2**num_failed-1)
 num_failed = (num_failed + 1) if not suceeded else 0

Usage:

backoff_generator = exponential_backoff(TIME_FRAME)
try:
 send_message("super cool message")
except MessageSendFailed:
 time.sleep(backoff_generator.send(False))
else:
 backoff_generator.send(True)

Does this seem like a reasonable way to handle things? The goal was to have a simple method of getting the amount of time to wait, without having to maintain too much state in the application itself, without adding an unreasonable amount of extra processing time, and without too much kruft.

Answer 1

A few suggestions:

• Possibly I’m using the given code incorrectly, but it doesn’t seem to work for me. I defined a send_message() function that would always fail:

  class MessageSendFailed(Exception):
   pass
  def send_message(msg):
   raise MessageSendFailed
  

  but when I run it, it immediately fails with the following error:

  $ python expofailed.py
  Traceback (most recent call last):
   File "expofailed.py", line 29, in <module>
   time.sleep(backoff_generator.send(False))
  TypeError: can't send non-None value to a just-started generator
  

  Alternatively, if I have a copy of send_message() that never throws an error, I get the same error.

• I’m not a big fan of the foo = bar if condition else baz style of Python ternary operator, because it tends towards unreadability by cramming everything onto a single line. I prefer splitting it into an explicit if block like so:

  if succeeded:
   num_failed = 0
  else:
   num_failed += 1
  

  And now you extend those branches more easily, and write a comment about why each branch behaves it does (because it’s not entirely obvious to me).

• Use a better variable name than k as the argument to your function – perhaps interval? Don’t skimp on variable names – characters are cheap.

• Your generator should have a docstring and a comment.

• You’ve misspelt "succeeded".

• Dan Oberlam: Huh, I never saw that error, but I know how to fix it now. Thanks for the feedback!