Add logging and backoff and simple retry logic

Fixes #1243 as described with a few more obvious cases as well.

/cc @philips @unihorn @xiangli-cmu
Not that the stack would overflow on 3. But fixed by not needing to do so anymore.