U.S. flag

An official website of the United States government, Department of Justice.

Singletons for simpletons revisiting windowed backoff with Chernoff bounds

NCJ Number
Date Published
15 pages

This study examines the use of Chernoff bounds in the context of backoff algorithms.


This study explores the use standard Chernoff bounds and illustrates simplicity of this approach by re-analyzing some well-known backoff algorithms. 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—those bins with a single ball—is important to the analysis of several backoff algorithms; however, existing analyses employ advanced probabilistic tools. (Published Abstract Provided)

Date Published: January 1, 2022