Singletons for Simpletons Revisiting Windowed Backoff with Chernoff Bounds

• NCJ Number: 307706
• Journal: Theoretical Computer Science Volume: 909 Dated: Mar 2022 Pages: 39-53
• Author(s): Qian M. Zhou; Alice Calvert; Maxwell Young
• Date Published: March 2022
• Length: 15 pages
• Grant Number(s): 2018-75-CX-K002
• Agencies: NIJ-Sponsored
• Sponsoring Agency: National Institute of Justice (NIJ)
• Publication Format: Article
• Publication Type: Research (Applied/Empirical)
• Language: English
• Country: United States of America

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)