NCJ Number
307706
Journal
Theoretical Computer Science Volume: 909 Dated: Mar 2022 Pages: 39-53
Date Published
March 2022
Length
15 pages
Annotation
This study examines the use of Chernoff bounds in the context of backoff algorithms.
Abstract
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: March 1, 2022