1 Search Results for "Jin, Wenyu"

Document
DOI: 10.4230/OASIcs.SOSA.2019.16
Simple Contention Resolution via Multiplicative Weight Updates

Authors: Yi-Jun Chang, Wenyu Jin, and Seth Pettie

Published in: OASIcs, Volume 69, 2nd Symposium on Simplicity in Algorithms (SOSA 2019)

Abstract
We consider the classic contention resolution problem, in which devices conspire to share some common resource, for which they each need temporary and exclusive access. To ground the discussion, suppose (identical) devices wake up at various times, and must send a single packet over a shared multiple-access channel. In each time step they may attempt to send their packet; they receive ternary feedback {0,1,2^+} from the channel, 0 indicating silence (no one attempted transmission), 1 indicating success (one device successfully transmitted), and 2^+ indicating noise. We prove that a simple strategy suffices to achieve a channel utilization rate of 1/e-O(epsilon), for any epsilon>0. In each step, device i attempts to send its packet with probability p_i, then applies a rudimentary multiplicative weight-type update to p_i. p_i <- { p_i * e^{epsilon} upon hearing silence (0), p_i upon hearing success (1), p_i * e^{-epsilon/(e-2)} upon hearing noise (2^+) }. This scheme works well even if the introduction of devices/packets is adversarial, and even if the adversary can jam time slots (make noise) at will. We prove that if the adversary jams J time slots, then this scheme will achieve channel utilization 1/e-epsilon, excluding O(J) wasted slots. Results similar to these (Bender, Fineman, Gilbert, Young, SODA 2016) were already achieved, but with a lower constant efficiency (less than 0.05) and a more complex algorithm.
Cite as

Yi-Jun Chang, Wenyu Jin, and Seth Pettie. Simple Contention Resolution via Multiplicative Weight Updates. In 2nd Symposium on Simplicity in Algorithms (SOSA 2019). Open Access Series in Informatics (OASIcs), Volume 69, pp. 16:1-16:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{chang_et_al:OASIcs.SOSA.2019.16,
  author =	{Chang, Yi-Jun and Jin, Wenyu and Pettie, Seth},
  title =	{{Simple Contention Resolution via Multiplicative Weight Updates}},
  booktitle =	{2nd Symposium on Simplicity in Algorithms (SOSA 2019)},
  pages =	{16:1--16:16},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-099-6},
  ISSN =	{2190-6807},
  year =	{2019},
  volume =	{69},
  editor =	{Fineman, Jeremy T. and Mitzenmacher, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2019.16},
  URN =		{urn:nbn:de:0030-drops-100426},
  doi =		{10.4230/OASIcs.SOSA.2019.16},
  annote =	{Keywords: Contention resolution, multiplicative weight update method}
}
  • Refine by Author
  • 1 Chang, Yi-Jun
  • 1 Jin, Wenyu
  • 1 Pettie, Seth

  • Refine by Classification

  • Refine by Keyword
  • 1 Contention resolution
  • 1 multiplicative weight update method

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2019

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