1 Search Results for "Young, Maxwell"

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-dev.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}
}
  • Refine by Author
  • 1 Calvert, Aiden
  • 1 Young, Maxwell
  • 1 Zhou, Qian M.

  • Refine by Classification
  • 1 Theory of computation → Distributed algorithms

  • Refine by Keyword
  • 1 Chernoff bounds
  • 1 algorithms
  • 1 backoff
  • 1 contention resolution

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2020

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact