Tight Trade-off in Contention Resolution without Collision Detection

DOI10.1145/3465084.3467920MaRDI QIDQ6201941zbMATH OpenOpenAlexFDO

Authors Haimin Chen, Chaodong Zheng

Publication date 26 March 2024

Published in Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2102.09716

zbMATH Keywords

backoffcontention resolutionjammingthroughput

Mathematics Subject Classification ID

Distributed systems (68M14) Distributed algorithms (68W15)

Abstract: 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 nodes broadcast). 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. In a recent breakthrough paper [Bender et al., STOC '20], a crucial case is resolved: constant throughput is possible without collision detection, but only if there is no jamming. Nonetheless, the exact trade-off between the best possible throughput and the severity of jamming remains unknown. In this paper, we address this open question. Specifically, for any level of jamming ranging from none to constant fraction, we prove an upper bound on the best possible throughput, along with an algorithm attaining that bound. An immediate and interesting implication of our result is, when a constant fraction of all slots are jammed, which is the worst-case scenario, there still exists an algorithm achieving a decent throughput: $Theta(t/logt)$ messages could be successfully transmitted within $t$ slots.

Recommendations

• Contention resolution without collision detection
• Contention resolution on multiple channels with collision detection
• Contention resolution in a non-synchronized multiple access channel
• Simple contention resolution via multiplicative weight updates
• CONTENTION RESOLUTION IN MULTIPLE-ACCESS CHANNELS: k-SELECTION IN RADIO NETWORKS

Cited in

(5)

• Contention resolution with message deadlines
• Jamming-resistant backoff with polylogarithmic sending and listening cost
• Fully energy-efficient randomized backoff: slow feedback loops yield fast contention resolution
• Instability of backoff protocols with arbitrary arrival rates
• Softening the impact of collisions in contention resolution

This page was built for publication: Tight Trade-off in Contention Resolution without Collision Detection

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6201941)