Brief Announcement: Deterministic Contention Resolution on a Shared Channel

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

doi:10.4230/LIPIcs.DISC.2018.44

File

LIPIcs.DISC.2018.44.pdf

Filesize: 228 kB
3 pages

Document Identifiers

DOI: 10.4230/LIPIcs.DISC.2018.44
URN: urn:nbn:de:0030-drops-98331

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 AsGet 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

A. Fernández Anta, M. A. Mosteiro, and J. Ramon Mu noz. Unbounded contention resolution in multiple-access channels. Algorithmica, 67:295-314, 2013.
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.
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.
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.
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.
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.
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.
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.
Robert G. Gallager. A perspective on multiaccess channels. IEEE Trans. Information Theory, 31(2):124-142, 1985.
L. A. Goldberg, P. D. MacKenzie, M. Paterson, and A. Srinivasan. Contention resolution with constant expected delay. J. ACM, 47(6):1048-1096, 2000.
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.
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.
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.