Document Open Access Logo

Brief Announcement: Deterministic Contention Resolution on a Shared Channel

Authors Gianluca De Marco, Dariusz R. Kowalski, Grzegorz Stachowiak

PDF
Thumbnail PDF

File

LIPIcs.DISC.2018.44.pdf
  • Filesize: 228 kB
  • 3 pages

Document Identifiers

Author Details

Gianluca De Marco
  • Dipartimento di Informatica, University of Salerno, Italy
Dariusz R. Kowalski
  • Department of Computer Science, University of Liverpool, UK
Grzegorz Stachowiak
  • Institute of Computer Science, University Wrocław, Poland

Cite As Get BibTex

Gianluca De Marco, Dariusz R. Kowalski, and Grzegorz Stachowiak. Brief Announcement: Deterministic Contention Resolution on a Shared Channel. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 44:1-44:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.DISC.2018.44

Abstract

A shared channel, also called multiple-access channel, is one of the fundamental communication models. Autonomous entities communicate over a shared medium, and one of the main challenges is how to efficiently resolve collisions occurring when more than one entity attempts to access the channel at the same time. In this work we explore the impact of asynchrony, knowledge (or linear estimate) of the number of contenders, and acknowledgments, on both latency and channel utilization for the Contention resolution problem with non-adaptive deterministic algorithms.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
Keywords
  • Shared channel
  • multiple-access channel
  • distributed algorithm

Metrics

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

References

  1. A. Fernández Anta, M. A. Mosteiro, and J. Ramon Mu noz. Unbounded contention resolution in multiple-access channels. Algorithmica, 67:295-314, 2013. Google Scholar
  2. M. A. Bender, M. Farach-Colton, S. He, B. C. Kuszmaul, and C. E. Leiserson. Adversarial contention resolution for simple channels. In Proceedings, 17th ACM Symp. on Parallel Algorithms (SPAA), pages 325-332, New York, NY, USA, 2005. ACM. Google Scholar
  3. M. A. Bender, T. Kopelowitz, S. Pettie, and M. Young. Contention resolution with log-logstar channel accesses. In Proceedings, 48th ACM Symp. on Theory of Computing (STOC), pages 499-508, Cambridge, MA, USA, 2016. ACM. Google Scholar
  4. B. S. Chlebus. Randomized communication in radio networks. In P. M. Pardalos, S. Rajasekaran, J. H. Reif, and J. D. P. Rolim, editors, Handbook on Randomized Computing, pages 401-456. Springer, New York, NY, USA, 2001. Google Scholar
  5. B. S. Chlebus, G. De Marco, and D. R. Kowalski. Scalable wake-up of multi-channel single-hop radio networks. Theor. Comput. Sci., 615:23-44, 2016. URL: http://dx.doi.org/10.1016/j.tcs.2015.11.046.
  6. B. S. Chlebus, D. R. Kowalski, and M. A. Rokicki. Adversarial queuing on the multiple access channel. ACM Trans. on Algorithms, 8:5:1-5:31, 2012. Google Scholar
  7. G. De Marco and D. R. Kowalski. Contention resolution in a non-synchronized multiple access channel. Theor. Comput. Sci., 689:1-13, 2017. URL: http://dx.doi.org/10.1016/j.tcs.2017.05.014.
  8. G. De Marco and G. Stachowiak. Asynchronous shared channel. In Proceedings, ACM Symp. on Principles of Distributed Computing, PODC 2017, Washington, DC, USA, July 25-27, 2017, pages 391-400, 2017. URL: http://dx.doi.org/10.1145/3087801.3087831.
  9. Robert G. Gallager. A perspective on multiaccess channels. IEEE Trans. Information Theory, 31(2):124-142, 1985. Google Scholar
  10. L. A. Goldberg, P. D. MacKenzie, M. Paterson, and A. Srinivasan. Contention resolution with constant expected delay. J. ACM, 47(6):1048-1096, 2000. Google Scholar
  11. A. G. Greenberg and A S. Winograd. Lower bound on the time needed in the worst case to resolve conflicts deterministically in multiple access channels. J. ACM, 32:589-596, 1985. Google Scholar
  12. J. Komlós and A. G. Greenberg. An asymptotically optimal nonadaptive algorithm for conflict resolution in multiple-access channels. IEEE Trans. on Information Theory, 31:302-306, 1985. Google Scholar
  13. D. Kowalski. On selection problem in radio networks. In Proceedings, 24th ACM Symp. on Principles of Distributed Computing (PODC), pages 158-166, Las Vegas, NV, USA, 2005. ACM. 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