Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FUN.2021.24
URN: urn:nbn:de:0030-drops-127859
URL: https://drops.dagstuhl.de/opus/volltexte/2020/12785/
Zhou, Qian M. ; Calvert, Aiden ; Young, Maxwell
Singletons for Simpletons: Revisiting Windowed Backoff with Chernoff Bounds
| pdf-format: |
|
Abstract
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.
BibTeX - Entry
@InProceedings{zhou_et_al:LIPIcs:2020:12785,
author = {Qian M. Zhou and Aiden Calvert and Maxwell Young},
title = {{Singletons for Simpletons: Revisiting Windowed Backoff with Chernoff Bounds}},
booktitle = {10th International Conference on Fun with Algorithms (FUN 2021)},
pages = {24:1--24:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-145-0},
ISSN = {1868-8969},
year = {2020},
volume = {157},
editor = {Martin Farach-Colton and Giuseppe Prencipe and Ryuhei Uehara},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12785},
URN = {urn:nbn:de:0030-drops-127859},
doi = {10.4230/LIPIcs.FUN.2021.24},
annote = {Keywords: Chernoff bounds, backoff, contention resolution, algorithms}
}
| Keywords: | Chernoff bounds, backoff, contention resolution, algorithms | |
| Seminar: | 10th International Conference on Fun with Algorithms (FUN 2021) | |
| Issue date: | 2020 | |
| Date of publication: | 16.09.2020 |
