Research group on

Resource Contention in Shared Channels

We study conflict resolution problems in multiple access channels and radio networks. Our main objective is to develop time and energy efficient symmetry breaking protocols as well as showing complexity separation results: randomization vs. determinism, adaptiveness vs. non-adaptiveness, knowledge vs. ignorance of contention size or network parameters, with vs. without a collision detection mechanism. The activity of the group are funded by the University Basic Research Funding as well as international research projects.

Investigators

• Gianluca De Marco
• Bogdan S. Chlebus (Augusta University)
• Tomasz Jurdziński (University of Wroclaw)
• Dariusz R. Kowalski (Augusta University)
• Michal Różański (University of Wroclaw)
• Grzegorz Stachowiak (University of Wroclaw)

Some papers

• Gianluca De Marco, Dariusz R. Kowalski, Grzegorz Stachowiak: Deterministic Contention Resolution without Collision Detection: Throughput vs Energy. ICDCS 2021: to appear
• Gianluca De Marco, Tomasz Jurdziński, Dariusz R. Kowalski: Optimal channel utilization with limited feedback. J. Comput. Syst. Sci. 119: 21-33 (2021)
• Gianluca De Marco, Tomasz Jurdziński, Dariusz R. Kowalski, Michal Różański, Grzegorz Stachowiak: Subquadratic non-adaptive threshold group testing. J. Comput. Syst. Sci. 111: 42-56 (2020)
• Tomasz Jurdzinski, Dariusz R. Kowalski, Michal Różański, Grzegorz Stachowiak: Token traversal in ad hoc wireless networks via implicit carrier sensing. Theor. Comput. Sci. 811: 3-20 (2020)
• Gianluca De Marco, Dariusz R. Kowalski, Grzegorz Stachowiak: Deterministic Contention Resolution on a Shared Channel. ICDCS 2019: 472-482
• Tomasz Jurdzinski, Dariusz R. Kowalski, Michal Różański, Grzegorz Stachowiak: Deterministic Digital Clustering of Wireless Ad Hoc Networks. PODC 2018: 105-114
• Gianluca De Marco, Grzegorz Stachowiak: Asynchronous Shared Channel. PODC 2017: 391-400
• Gianluca De Marco, Dariusz R. Kowalski: Contention resolution in a non-synchronized multiple access channel. Theor. Comput. Sci. 689: 1-13 (2017)
• Bogdan S. Chlebus, Gianluca De Marco, Dariusz R. Kowalski: Scalable wake-up of multi-channel single-hop radio networks. Theor. Comput. Sci. 615: 23-44 (2016)
• Gianluca De Marco, Dariusz R. Kowalski: Fast Nonadaptive Deterministic Algorithm for Conflict Resolution in a Dynamic Multiple-Access Channel. SIAM J. Comput. 44(3): 868-888 (2015)