Tight Trade-off in Contention Resolution without Collision Detection
Haimin Chen, Yonggang Jiang, Chaodong Zheng · 2021
In this paper, we consider contention resolution on a multiple-access communication channel. In this problem, a set of nodes arrive over time, each with a message it intends to send. In each time slot, each node may attempt to broadcast its message or remain idle. If a single node broadcasts in a slot, the message is received by all nodes; otherwise, if multiple nodes broadcast simultaneously, a collision occurs and none succeeds. If collision detection is available, nodes can differentiate collision and silence (i.e., no node broadcasts). Performance of contention resolution algorithms is often measured by throughput---the number of successful transmissions within a period of time; whereas robustness is often measured by jamming resistance---a jammed slot always generates a collision. Previous work has shown, with collision detection, optimal constant throughput can be attained, even if a constant fraction of all slots are jammed. The situation when collision detection is not available, however, remains unclear.