2026-08-08T00:00:27Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12785 2024-03-06T10:49:10Z ddc:004 open_access

Singletons for Simpletons: Revisiting Windowed Backoff with Chernoff Bounds Zhou, Qian M. Calvert, Aiden Young, Maxwell Chernoff bounds backoff contention resolution 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 to obtain concentration bounds. Here, we show that standard Chernoff bounds can be used instead, and the simplicity of this approach is illustrated by re-analyzing some well-known backoff algorithms. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Qian M. Zhou and Aiden Calvert and Maxwell Young 2020 Is Part Of LIPIcs, Volume 157, 10th International Conference on Fun with Algorithms (FUN 2021) (2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FUN.2021.24 urn:nbn:de:0030-drops-127859 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.24 eng https://creativecommons.org/licenses/by/3.0/legalcode