Singletons for Simpletons: Revisiting Windowed Backoff using Chernoff Bounds

Qian M. Zhou, Alice Calvert, Maxwell Young

Backoff algorithms are used in many distributed systems where multiple devices contend for a shared resource. For the classic balls-into-bins problem, the number of singletons -- t…