Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH scholarly article en Zhou, Qian M.; Calvert, Aiden; Young, Maxwell https://www.dagstuhl.de/lipics License: Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-127859
URL:

; ;

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


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI