DROPS

Document

DOI: 10.4230/LIPIcs.FUN.2021.24

Singletons for Simpletons: Revisiting Windowed Backoff with Chernoff Bounds

Authors: Qian M. Zhou, Aiden Calvert, and Maxwell Young

Published in: LIPIcs, Volume 157, 10th International Conference on Fun with Algorithms (FUN 2021) (2020)

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.

Cite as

Qian M. Zhou, Aiden Calvert, and Maxwell Young. Singletons for Simpletons: Revisiting Windowed Backoff with Chernoff Bounds. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 24:1-24:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{zhou_et_al:LIPIcs.FUN.2021.24,
  author =	{Zhou, Qian M. and Calvert, Aiden and Young, Maxwell},
  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 =	{Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.24},
  URN =		{urn:nbn:de:0030-drops-127859},
  doi =		{10.4230/LIPIcs.FUN.2021.24},
  annote =	{Keywords: Chernoff bounds, backoff, contention resolution, algorithms}
}

Search Results

Documents authored by Zhou, Qian M.

Singletons for Simpletons: Revisiting Windowed Backoff with Chernoff Bounds

Abstract

Cite as

Thanks for your feedback!

Could not send message