Softening the Impact of Collisions in Contention Resolution
ORCID
Biswas: https://orcid.org/0009-0000-2842-5527; Chakraborty: https://orcid.org/0009-0002-8531-0667; Young: https://orcid.org/0000-0002-5251-8595; Zhou: https://orcid.org/0000-0002-7503-0445
MSU Affiliation
James Worth Bagley College of Engineering; Department of Computer Science and Engineering; College of Arts and Sciences; Department of Mathematics and Statistics
Creation Date
2026-04-29
Abstract
Contention resolution addresses the problem of coordinating access to a shared communication channel. Time is discretized into synchronized slots, and a packet can be sent in any slot. If no packet is sent, then the slot is empty; if a single packet is sent, then it is successful; and when multiple packets are sent at the same time, a collision occurs, resulting in the failure of the corresponding transmissions. In each slot, every packet receives ternary channel feedback indicating whether the current slot is empty, successful, or a collision. Much of the prior work on contention resolution has focused on optimizing the makespan, which is the number of slots required for all packets to succeed. However, in many modern systems, collisions are also costly in terms of the time they incur. In this paper, we design and analyze a randomized algorithm, Collision-Aversion Backoff (CAB), that addresses both the makespan and the total number of slots in which a collision occurs (i.e., total collision cost). We consider the static case where an unknown n ≥ 2 packets are initially present in the system, and each collision has a known cost , where for any constant κ ≥ 0. CAB guarantees that all packets succeed with expected makespan and an expected total collision cost of . We also give a complementary lower bound for the class of fair algorithms: where, in each slot, every packet sends with the same probability on a per-slot basis.
Publication Date
3-28-2026
Publication Title
Theoretical Computer Science
Publisher
Elsevier
Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.
Recommended Citation
Biswas, U., Chakraborty, T., Young, M., & Zhou, Q. M. (2026). Softening the impact of collisions in contention resolution. Theoretical Computer Science, 1074, 115907. https://doi.org/10.1016/j.tcs.2026.115907
