[arghbleargh]

> It’s worth noting that none of these approaches fundamentally change the N^2 nature of the work to be done, but do substantially reduce work at reasonable levels of contention.

I don't think that statement from the article is true if I understood correctly... the performance gains are precisely because you're reducing from N^2 to N log N.

An interesting theoretical question would be to identify the optimal backoff policy. I think FullJitter should be close to optimal, but maybe you can squeeze out a little more with something more sophisticated.

Edit: I just realized the DecorrelatedJitter (not sure why it's called that?) makes a lot of sense as a minor optimization because if you already waited a long time and still failed, that suggests there is a lot of contention, and you should wait even longer.