Document Open Access Logo

Simple Contention Resolution via Multiplicative Weight Updates

Authors Yi-Jun Chang, Wenyu Jin, Seth Pettie

PDF
Thumbnail PDF

File

OASIcs.SOSA.2019.16.pdf
  • Filesize: 0.56 MB
  • 16 pages

Document Identifiers

Author Details

Yi-Jun Chang
Wenyu Jin
Seth Pettie

Cite As Get BibTex

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) https://doi.org/10.4230/OASIcs.SOSA.2019.16

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.

Subject Classification

Keywords
  • Contention resolution
  • multiplicative weight update method

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. D. J. Aldous. Ultimate instability of exponential back-off protocol for acknowledgment-based transmission control of random access communication channels. IEEE Trans. Information Theory, 33(2):219-223, 1987. URL: http://dx.doi.org/10.1109/TIT.1987.1057295.
  2. S. Arora, E. Hazan, and S. Kale. The Multiplicative Weights Update Method: a Meta-Algorithm and Applications. Theory of Computing, 8(1):121-164, 2012. URL: http://dx.doi.org/10.4086/toc.2012.v008a006.
  3. B. Awerbuch, A. W. Richa, and C. Scheideler. A jamming-resistant MAC protocol for single-hop wireless networks. In Proceedings of the Twenty-Seventh Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 45-54, 2008. URL: http://dx.doi.org/10.1145/1400751.1400759.
  4. M. A. Bender, M. Farach-Colton, S. He, B. C. Kuszmaul, and C. E. Leiserson. Adversarial contention resolution for simple channels. In Proceedings of the 17th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 325-332, 2005. URL: http://dx.doi.org/10.1145/1073970.1074023.
  5. M. A. Bender, J. T. Fineman, and S. Gilbert. Contention Resolution with Heterogeneous Job Sizes. In Proceedings 14th Annual European Symposium on Algorithms (ESA), pages 112-123, 2006. URL: http://dx.doi.org/10.1007/11841036_13.
  6. M. A. Bender, J. T. Fineman, S. Gilbert, and M. Young. How to Scale Exponential Backoff: Constant Throughput, Polylog Access Attempts, and Robustness. In Proceedings 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 636-654, 2016. URL: http://dx.doi.org/10.1137/1.9781611974331.ch47.
  7. M. A. Bender, T. Kopelowitz, S. Pettie, and M. Young. Contention resolution with log-logstar channel accesses. In Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC), pages 499-508, 2016. URL: http://dx.doi.org/10.1145/2897518.2897655.
  8. V. Bharghavan, A. J. Demers, S. Shenker, and L. Zhang. MACAW: A media access protocol for wireless LAN’s. In Proceedings of the ACM SIGCOMM Conference on Communications Architectures, Protocols and Applications, pages 212-225, 1994. URL: http://dx.doi.org/10.1145/190314.190334.
  9. J. Capetanakis. Tree algorithms for packet broadcast channels. IEEE Trans. Information Theory, 25(5):505-515, 1979. URL: http://dx.doi.org/10.1109/TIT.1979.1056093.
  10. Y.-J. Chang, T. Kopelowitz, S. Pettie, R. Wang, and W. Zhan. Exponential separations in the energy complexity of leader election. In Proceedings 49th Annual ACM Symposium on Theory of Computing (STOC), pages 771-783, 2017. URL: http://dx.doi.org/10.1145/3055399.3055481.
  11. J. Deng, P. K. Varshney, and Z. Haas. A New Backoff Algorithm for the IEEE 802.11 Distributed Coordination Function. In In Communication Networks and Distributed Systems Modeling and Simulation, pages 215-225, 2004. Google Scholar
  12. R. G. Gallager. Conflict resolution in random access broadcast networks. In Proceedings AFOSR Workshop on Communications Theory Applications, Provincetown, MA, Sept 17-20, pages 74-76, 1978. Google Scholar
  13. L. A. Goldberg, M. Jerrum, S. Kannan, and M. Paterson. A bound on the capacity of backoff and acknowledgment-based protocols. SIAM J. Comput., 33(2):313-331, 2004. URL: http://dx.doi.org/10.1137/S0097539700381851.
  14. L. A. Goldberg, P. D. MacKenzie, M. Paterson, and A. Srinivasan. Contention resolution with constant expected delay. J. ACM, 47(6):1048-1096, 2000. URL: http://dx.doi.org/10.1145/355541.355567.
  15. J. Goodman, A. G. Greenberg, N. Madras, and P. March. Stability of binary exponential backoff. J. ACM, 35(3):579-602, 1988. URL: http://dx.doi.org/10.1145/44483.44488.
  16. Z. J. Haas and J. Deng. On optimizing the backoff interval for random access schemes. IEEE Trans. Communications, 51(12):2081-2090, 2003. URL: http://dx.doi.org/10.1109/TCOMM.2003.820754.
  17. J. Håstad, F. Thomson Leighton, and B. Rogoff. Analysis of Backoff Protocols for Multiple Access Channels. SIAM J. Comput., 25(4):740-774, 1996. URL: http://dx.doi.org/10.1137/S0097539792233828.
  18. M. Herlihy and J. E. B. Moss. Transactional Memory: Architectural Support for Lock-Free Data Structures. In Proceedings of the 20th Annual International Symposium on Computer Architecture (ISCA), pages 289-300, 1993. URL: http://dx.doi.org/10.1145/165123.165164.
  19. V. Jacobson. Congestion avoidance and control. In Proceedings of the ACM Symposium on Communications Architectures and Protocols (SIGCOMM), pages 314-329, 1988. URL: http://dx.doi.org/10.1145/52324.52356.
  20. J. F. Kurose and K. W. Ross. Computer networking: a top-down approach, volume 4. Addison-Wesley, Boston, 2009. Google Scholar
  21. K. Li, I. Nikolaidis, and J. J. Harms. The analysis of the additive-increase multiplicative-decrease MAC protocol. In Proceedings 10th Annual Conference on Wireless On-demand Network Systems and Services (WONS), pages 122-124, 2013. URL: http://dx.doi.org/10.1109/WONS.2013.6578335.
  22. R. M. Metcalfe and D. R. Boggs. Ethernet: Distributed packet switching for local computer networks. Communications of the ACM, 19(7):395-404, 1976. Google Scholar
  23. V. A. Mikhailov and B. S. Tsybakov. Upper bound for the capacity of a random multiple access system. Problemy Peredachi Informatsii, 17(1):90-95, 1981. Google Scholar
  24. A. Mondal and A. Kuzmanovic. Removing exponential backoff from TCP. Computer Communication Review, 38(5):17-28, 2008. URL: http://dx.doi.org/10.1145/1452335.1452338.
  25. J. Mosely and P. A. Humblet. A Class of Efficient Contention Resolution Algorithms for Multiple Access Channels. IEEE Trans. Communications, 33(2):145-151, 1985. URL: http://dx.doi.org/10.1109/TCOM.1985.1096261.
  26. N. Pippenger. Bounds on the performance of protocols for a multiple-access broadcast channel. IEEE Trans. Information Theory, 27(2):145-151, 1981. URL: http://dx.doi.org/10.1109/TIT.1981.1056332.
  27. R. Rajwar and J. R. Goodman. Speculative lock elision: enabling highly concurrent multithreaded execution. In Proceedings of the 34th Annual International Symposium on Microarchitecture (MICRO), pages 294-305, 2001. URL: http://dx.doi.org/10.1109/MICRO.2001.991127.
  28. N.-O. Song, B.-J. Kwak, and L. E. Miller. Analysis of EIED backoff algorithm for the IEEE 802.11 DCF. In Proceedings 62nd IEEE Vehicular Technology Conference (VTC), volume 4, pages 2182-2186, 2005. Google Scholar
  29. B. S. Tsybakov and V. A. Mikhailov. Slotted multiaccess packet broadcasting feedback channel. Problemy Peredachi Informatsii, 14(4):32-59, 1978. Google Scholar
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 About DROPS Imprint Privacy Contact