Document Open Access Logo

Singletons for Simpletons: Revisiting Windowed Backoff with Chernoff Bounds

Authors Qian M. Zhou, Aiden Calvert, Maxwell Young

PDF
Thumbnail PDF

File

LIPIcs.FUN.2021.24.pdf
  • Filesize: 0.54 MB
  • 19 pages

Document Identifiers

Author Details

Qian M. Zhou
  • Mississippi State University, Department of Mathematics and Statistics, MS, USA
Aiden Calvert
  • Mississippi School for Mathematics and Science, Columbus, MS, USA
Maxwell Young
  • Mississippi State University, Department of Computer Science and Engineering, MS, USA

Funding

  • Young, Maxwell: This research is supported by the National Science Foundation grant CNS 1816076, and by the U.S. National Institute of Justice (NIJ) Grant 2018-75-CX-K002.

Cite AsGet BibTex

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)
https://doi.org/10.4230/LIPIcs.FUN.2021.24

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
Keywords
  • Chernoff bounds
  • backoff
  • contention resolution
  • algorithms

Metrics

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

References

  1. Lakshmi Anantharamu, Bogdan S. Chlebus, Dariusz R. Kowalski, and Mariusz A. Rokicki. Medium access control for adversarial channels with jamming. In Proceedings of the 18^th International Colloquium on Structural Information and Communication Complexity (SIROCCO), pages 89-100, 2011. Google Scholar
  2. Antonio Fernández Anta, Miguel A. Mosteiro, and Jorge Ramón Muñoz. Unbounded contention resolution in multiple-access channels. Algorithmica, 67(3):295-314, 2013. Google Scholar
  3. Baruch Awerbuch, Andrea Richa, and Christian Scheideler. A jamming-resistant MAC protocol for single-hop wireless networks. In Proceedings of the 27th ACM Symposium on Principles of Distributed Computing (PODC), pages 45-54, 2008. Google Scholar
  4. Yossi Azar, Andrei Z. Broder, Anna R. Karlin, and Eli Upfal. Balanced allocations. SIAM J. Comput., 29(1):180-200, September 1999. Google Scholar
  5. Michael A. Bender, Martin Farach-Colton, Simai He, Bradley C. Kuszmaul, and Charles 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. Google Scholar
  6. Michael A. Bender, Jeremy T. Fineman, and Seth Gilbert. Contention Resolution with Heterogeneous Job Sizes. In Proceedings of the 14th Conference on Annual European Symposium (ESA), pages 112-123, 2006. Google Scholar
  7. Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, and Maxwell Young. How to scale exponential backoff: Constant throughput, polylog access attempts, and robustness. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2016. Google Scholar
  8. Michael A. Bender, Tsvi Kopelowitz, Seth Pettie, and Maxwell Young. Contention resolution with log-logstar channel accesses. In Proceedings of the Forty-eighth Annual ACM Symposium on Theory of Computing, STOC '16, pages 499-508, 2016. Google Scholar
  9. Petra Berenbrink, Artur Czumaj, Matthias Englert, Tom Friedetzky, and Lars Nagel. Multiple-choice balanced allocation in (almost) parallel. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX-RANDOM), pages 411-422, 2012. Google Scholar
  10. Petra Berenbrink, Artur Czumaj, Angelika Steger, and Berthold Vöcking. Balanced allocations: The heavily loaded case. SIAM J. Comput., 35(6):1350-1385, 2006. Google Scholar
  11. Petra Berenbrink, Kamyar Khodamoradi, Thomas Sauerwald, and Alexandre Stauffer. Balls-into-bins with nearly optimal load distribution. In Proceedings of the Twenty-fifth Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 326-335, 2013. Google Scholar
  12. Yi-Jun Chang, Varsha Dani, Thomas P. Hayes, Qizheng He, Wenzheng Li, and Seth Pettie. The energy complexity of broadcast. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC '18, pages 95-104, 2018. Google Scholar
  13. Yi-Jun Chang, Tsvi Kopelowitz, Seth Pettie, Ruosong Wang, and Wei Zhan. Exponential separations in the energy complexity of leader election. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 771-783, 2017. Google Scholar
  14. Bogdan S. Chlebus, Gianluca De Marco, and Dariusz R. Kowalski. Scalable wake-up of multi-channel single-hop radio networks. Theoretical Computer Science, 615(C):23-44, February 2016. Google Scholar
  15. Bogdan S. Chlebus, Leszek Gasieniec, Dariusz R. Kowalski, and Tomasz Radzik. On the wake-up problem in radio networks. In Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP), pages 347-359, 2005. Google Scholar
  16. Bogdan S. Chlebus and Dariusz R. Kowalski. A better wake-up in radio networks. In Proceedings of 23rd ACM Symposium on Principles of Distributed Computing (PODC), pages 266-274, 2004. Google Scholar
  17. Marek Chrobak, Leszek Gasieniec, and Dariusz R. Kowalski. The wake-up problem in multihop radio networks. SIAM Journal on Computing, 36(5):1453-1471, 2007. Google Scholar
  18. Richard Cole, Alan M. Frieze, Bruce M. Maggs, Michael Mitzenmacher, Andréa W. Richa, Ramesh K. Sitaraman, and Eli Upfal. On balls and bins with deletions. In Proceedings of the Second International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM), pages 145-158, 1998. Google Scholar
  19. A. Czumaj and V. Stemann. Randomized Allocation Processes. In Proceedings 38th Annual Symposium on Foundations of Computer Science, pages 194-203, 1997. Google Scholar
  20. Gianluca De Marco and Grzegorz Stachowiak. Asynchronous shared channel. In Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC '17, pages 391-400, 2017. Google Scholar
  21. Devdatt Dubhashi and Alessandro Panconesi. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, 1st edition, 2009. Google Scholar
  22. Devdatt Dubhashi and Desh Ranjan. Balls and Bins: A Study in Negative Dependence. Random Structures & Algorithms, 13(2):99-124, 1998. URL: https://doi.org/10.1002/(SICI)1098-2418(199809)13:2<99::AID-RSA1>3.0.CO;2-M.
  23. Jeremy T. Fineman, Seth Gilbert, Fabian Kuhn, and Calvin Newport. Contention resolution on a fading channel. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 155-164, 2016. Google Scholar
  24. Jeremy T. Fineman, Calvin Newport, and Tonghe Wang. Contention resolution on multiple channels with collision detection. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC 2016, Chicago, IL, USA, July 25-28, 2016, pages 175-184, 2016. Google Scholar
  25. Mihály Geréb-Graus and Thanasis Tsantilas. Efficient optical communication in parallel computers. In Proceedings 4th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pages 41-48, 1992. Google Scholar
  26. Leslie Ann Goldberg and Philip D. MacKenzie. Analysis of practical backoff protocols for contention resolution with multiple servers. Journal of Computer and System Sciences, 58(1):232-258, 1999. URL: https://doi.org/10.1006/jcss.1998.1590.
  27. Leslie Ann Goldberg, Philip D. Mackenzie, Mike Paterson, and Aravind Srinivasan. Contention resolution with constant expected delay. Journal of the ACM, 47(6):1048-1096, 2000. Google Scholar
  28. Jonathan Goodman, Albert G. Greenberg, Neal Madras, and Peter March. Stability of binary exponential backoff. Journal of the ACM, 35(3):579-602, July 1988. Google Scholar
  29. Ronald I. Greenberg and Charles E. Leiserson. Randomized routing on fat-trees. In Proceedings of the 26th Annual Symposium on Foundations of Computer Science (FOCS), pages 241-249, 1985. Google Scholar
  30. Johan Hastad, Tom Leighton, and Brian Rogoff. Analysis of backoff protocols for multiple access channels. SIAM Journal on Computing, 25(4):1996, 740-774. Google Scholar
  31. IEEE. IEEE standard for information technology-telecommunications and information exchange between systems local and metropolitan area networks - Specific requirements - Part 11: Wireless LAN medium access control (MAC) and physical layer (PHY) specifications. IEEE Std 802.11-2016 (Revision of IEEE Std 802.11-2012), pages 1-3534, 2016. Google Scholar
  32. Tomasz Jurdzinski and Grzegorz Stachowiak. The cost of synchronizing multiple-access channels. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 421-430, 2015. Google Scholar
  33. A R Karlin and E Upfal. Parallel Hashing - An Efficient Implementation of Shared Memory. In Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing (STOC), pages 160-168, 1986. Google Scholar
  34. James F. Kurose and Keith Ross. Computer Networking: A Top-Down Approach. Pearson, 6th edition, 2013. Google Scholar
  35. Christoph Lenzen and Roger Wattenhofer. Tight Bounds for Parallel Randomized Load Balancing: Extended Abstract. In Proceedings of the Forty-third Annual ACM Symposium on Theory of Computing, STOC '11, pages 11-20, 2011. Google Scholar
  36. Gianluca De Marco and Dariusz R. Kowalski. Fast nonadaptive deterministic algorithm for conflict resolution in a dynamic multiple-access channel. SIAM Journal on Computing, 44(3):868-888, 2015. Google Scholar
  37. Gianluca De Marco and Dariusz R. Kowalski. Contention resolution in a non-synchronized multiple access channel. Theoretical Computer Science, 689:1-13, 2017. Google Scholar
  38. Robert M. Metcalfe and David R. Boggs. Ethernet: Distributed packet switching for local computer networks. Communications of the ACM, 19(7):395-404, July 1976. Google Scholar
  39. Michael Mitzenmacher and Eli Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, New York, NY, USA, 2005. Google Scholar
  40. Michael David Mitzenmacher. The Power of Two Choices in Randomized Load Balancing. PhD thesis, University of California, Berkeley, 1996. Google Scholar
  41. K. Nakano and S. Olariu. Uniform leader election protocols for radio networks. IEEE Transactions on Parallel and Distributed Systems, 13(5):516-526, May 2002. URL: https://doi.org/10.1109/TPDS.2002.1003864.
  42. Adrian Ogierman, Andrea Richa, Christian Scheideler, Stefan Schmid, and Jin Zhang. Sade: competitive MAC under adversarial SINR. Distributed Computing, 31(3):241-254, June 2018. Google Scholar
  43. Prabhakar Raghavan and Eli Upfal. Stochastic contention resolution with short delays, April 1999. Google Scholar
  44. Andrea Richa, Christian Scheideler, Stefan Schmid, and Jin Zhang. A jamming-resistant MAC protocol for multi-hop wireless networks. In Proceedings of the International Symposium on Distributed Computing (DISC), pages 179-193, 2010. Google Scholar
  45. Andrea Richa, Christian Scheideler, Stefan Schmid, and Jin Zhang. Competitive and fair medium access despite reactive jamming. In Proceedings of the 31^st International Conference on Distributed Computing Systems (ICDCS), pages 507-516, 2011. Google Scholar
  46. Andrea Richa, Christian Scheideler, Stefan Schmid, and Jin Zhang. Competitive and Fair Throughput for Co-existing Networks Under Adversarial Interference. In Proceedings of the 2012 ACM Symposium on Principles of Distributed Computing (PODC), pages 291-300, 2012. Google Scholar
  47. Andrea W Richa, M Mitzenmacher, and R Sitaraman. The power of two random choices: A survey of techniques and results. Combinatorial Optimization, 9:255-304, 2001. Google Scholar
  48. X. Sun and L. Dai. Backoff Design for IEEE 802.11 DCF Networks: Fundamental Tradeoff and Design Criterion. IEEE/ACM Transactions on Networking, 23(1):300-316, 2015. Google Scholar
  49. Eli Upfal. Efficient Schemes for Parallel Communication. J. ACM, 31(3):507-517, June 1984. Google Scholar
  50. Berthold Vöcking. How asymmetry helps load balancing. Journal of the ACM, 50(4):568-589, 2003. Google Scholar
  51. Dan E. Willard. Log-logarithmic selection resolution protocols in a multiple access channel. SIAM J. Comput., 15(2):468-477, May 1986. Google Scholar
  52. D. Yin, K. Lee, R. Pedarsani, and K. Ramchandran. Fast and Robust Compressive Phase Retrieval with Sparse-Graph Codes. In 2015 IEEE International Symposium on Information Theory (ISIT), pages 2583-2587, June 2015. 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 Imprint Privacy Contact