License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.SOSA.2019.16
URN: urn:nbn:de:0030-drops-100426
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/10042/
Chang, Yi-Jun ;
Jin, Wenyu ;
Pettie, Seth
Simple Contention Resolution via Multiplicative Weight Updates
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.
BibTeX - Entry
@InProceedings{chang_et_al:OASIcs:2018:10042,
author = {Yi-Jun Chang and Wenyu Jin and Seth Pettie},
title = {{Simple Contention Resolution via Multiplicative Weight Updates}},
booktitle = {2nd Symposium on Simplicity in Algorithms (SOSA 2019)},
pages = {16:1--16:16},
series = {OpenAccess Series in Informatics (OASIcs)},
ISBN = {978-3-95977-099-6},
ISSN = {2190-6807},
year = {2018},
volume = {69},
editor = {Jeremy T. Fineman and Michael Mitzenmacher},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/10042},
URN = {urn:nbn:de:0030-drops-100426},
doi = {10.4230/OASIcs.SOSA.2019.16},
annote = {Keywords: Contention resolution, multiplicative weight update method}
}
|
Keywords: |
|
Contention resolution, multiplicative weight update method |
|
Collection: |
|
2nd Symposium on Simplicity in Algorithms (SOSA 2019) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
08.01.2019 |
